walk_alone @ 2018-08-07 17:39:36
发现一个很神奇的现象: 在dfs函数中如果加入参数t(终点),那么就可以过第三个点,但是其他的都死循环里过不了。打印出来看,发现这个t一直都在变(难道可以变吗?)。但如果不加参数就一直七十分。求助。
#include <cstdio>
#include <algorithm>
using namespace std;
const int inf=999999999;
struct node
{
int from;
int to;
int v;
int next;
};
struct node que[300001];
int head=1,tail=2,headers[100001],book[100001],place[100001],depth[100001],s,t,n,m;
bool bfs()
{
for(int i=1;i<tail;i++)
place[i]=depth[i]=book[i]=0;
head=1;
tail=2;
place[head]=s;
depth[s]=1;
book[place[head]]=1;
while(head<tail)
{
for(int t=headers[place[head]];t;t=que[t].next)
if(que[t].v>0 && book[que[t].to]==0)
{
place[tail]=que[t].to;
depth[que[t].to]=depth[place[head]]+1;
book[que[t].to]=1;
tail++;
}
head++;
}
if(depth[t]==0)
return 0;
return 1;
}
int dfs(int u,int dis)
{
if(u==t)
return dis;
for(int t=headers[u];t;t=que[t].next)
if(depth[que[t].to]==depth[u]+1 && que[t].v>0)
{
int d=dfs(que[t].to,min(dis,que[t].v));
if(d>0)
{
que[t].v-=d;
que[t^1].v+=d;
return d;
}
}
return 0;
}
int dinic(int s,int t)
{
int ans=0;
while(bfs())
while(int d=dfs(s,inf))
ans+=d;
return ans;
}
int main()
{
int count=1,a,b,c;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
que[count].from=a;
que[count].to=b;
que[count].v=c;
que[count].next=headers[a];
headers[a]=count;
count++;
que[count].from=b;
que[count].to=a;
que[count].next=headers[b];
headers[b]=count;
count++;
}
printf("%d",dinic(s,t));
return 0;
}
by Soulist @ 2018-08-07 17:48:27
您的t当然一直在变啊,变量名推荐写的大众一点 此处: for(int t=headers[u]; t ; t = que[t].next) t的值固然会改变啊
by Soulist @ 2018-08-07 17:48:44
您写出i之类的应该就没事了
by Soulist @ 2018-08-07 17:50:20
特别好奇您是怎么拿70分的%%%
by walk_alone @ 2018-08-07 20:39:46
@Hakuryu_CYZ 突然发现我智障了。还是感谢神仙。
by Soulist @ 2018-08-07 20:52:13
@walk_alone 我是蒟蒻QWQ
by walk_alone @ 2018-08-07 21:00:26
@Hakuryu_CYZ 好了也不扯这个事,但问题是现在改过来还是70,但是没那个加不加参数的问题了。重边的问题也考虑了,但为什么又只有60?
by Soulist @ 2018-08-07 21:43:46
@walk_alone 洛谷的消息延时好大QWQ
(一直泡在小号上写题233)
推荐您把手写的队列改成STL,之前我写网络流的时候反正手写的队列就是过不了233
以及,网络因为cnt是从0开始计数的,所以在对边进行访问的时候不能写:
for(int i = head[x]; i; i = e[i].next)
这样的QWQ,主要是i = 0有两种情况,1是第一条边,2是终止条件
所以我一般都是用-1或者讲cnt初始化为2
以及,您是把所有循环中的t都改过来了吗? bfs里面也有t
by Soulist @ 2018-08-07 21:44:38
对了,这道题数据超级水,这段代码有70分:
#include<bits/stdc++.h>
using namespace std;
int ans,n,m,u,v,w,s,t,minn;
int main()
{
cin>>n>>m>>s>>t;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>w;
if(u == s) minn += w;
if(v==t)
ans+=w;
}
cout<<min(minn, ans);
return 0;
}
by Soulist @ 2018-08-07 21:48:50
@walk_alone 对了,您的cnt好像是从1开始的QWQ? 1^1 = 0且0^1 = 1来着如果我没记错 反正好像是如果要用x^1表示它的反向边,要从0开始计数,反正从偶数开始,抱歉,没注意到
by walk_alone @ 2018-08-07 22:21:49
@Hakuryu_CYZ 问题正是这里,感谢神仙,%%%。