为依相逢 @ 2019-01-31 21:34:27
Dinic算法,初打,好像问题是死循环,请问哪里错了?
格式不对不要吐槽我,我尽力了,大括号都改成不换行的了
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Maxn=20000;
const int Maxm=1000000;
struct Edge{
int next,en,maxl;
}a[Maxm*2+9];
int q[Maxn+9];
int b[Maxn+9],c[Maxn+9],s,t,max_sum_l,n,m,x,y,tmp;
bool j[Maxn+9];
int t1(int num){
return (num<<1)-1;
}
int t2(int num){
return (num<<1)-2;
}
void jr(int num,int bn,int en,int maxl){
int tmp1=t1(num);
int tmp2=t2(num);
a[tmp1].en=en;
a[tmp1].next=b[bn];
a[tmp1].maxl=maxl;
b[bn]=tmp1;
a[tmp2].en=bn;
a[tmp2].next=b[en];
a[tmp2].maxl=0;
b[en]=tmp2;
return;
}
int bfs(){
memset(c,0,sizeof(c));
memset(q,0,sizeof(q));
memset(j,false,sizeof(j));
int l=1;
int r=1;
q[r]=s;
c[q[r]]=1;
j[s]=true;
while (l<=r){
for (int i=b[q[l]];i!=0;i=a[i].next)
if (!j[a[i].en] && a[i].maxl!=0){
q[++r]=a[i].en;
c[q[r]]=c[q[l]]+1;
j[a[i].en]=true;
}
l++;
}
return c[t];
}
int dfs(int nownum,int now_max_l){
if (now_max_l==0) return 0;
int ans=0,res;
for (int i=b[nownum];i!=0;i=a[i].next)
if (c[a[i].en]==c[nownum]+1)
if (res=dfs(a[i].en,min(a[i].maxl,now_max_l))>0){
a[i].maxl-=res;
a[i^1].maxl+=res;
ans+=res;
}
return ans;
}
int dinic_work(){
int ans=0;
while (bfs())
ans+=dfs(s,1<<30);
return ans;
}
int main(){
memset(b,-1,sizeof(b));
scanf("%d%d%d%d",&n,&m,&s,&t);
max_sum_l=1<<30;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&tmp);
jr(i,x,y,tmp);
}
cout<<min(dinic_work(),max_sum_l);
return 0;
}
by lyh0313 @ 2019-01-31 21:46:03
@zlym:
你的边集数组
没崩溃是因为下标没有溢出太多
by lyh0313 @ 2019-01-31 21:47:17
@ zlym
by 为依相逢 @ 2019-01-31 21:53:33
@lyh0313 ok谢谢
我就知道是沙雕错误
by 为依相逢 @ 2019-01-31 21:54:43
@lyh0313 等下,还是死循环
by lyh0313 @ 2019-01-31 22:08:36
在
if (now_max_l==0) return 0;
这句后面加上
if(nownum==t) return now_max_l;
就可以了
by 为依相逢 @ 2019-01-31 22:13:18
@lyh0313 emmm...5WA3TLE
by 为依相逢 @ 2019-01-31 22:13:40
我觉得剩下的还是沙雕错误。。。
by lyh0313 @ 2019-01-31 22:45:11
你把
int dfs(int nownum,int now_max_l){
if(nownum==t) return now_max_l;
int ans=0,res;
for (int i=b[nownum];i!=0;i=a[i].next)
if (c[a[i].en]==c[nownum]+1&&a[i].maxl>0)
{
res=dfs(a[i].en,min(a[i].maxl,now_max_l));
a[i].maxl-=res;
a[i^1].maxl+=res;
ans+=res;
now_max_l-=res;
if(now_max_l==0) return ans;
}
return ans;
}
by 为依相逢 @ 2019-02-01 08:27:30
@lyh0313 emmm好吧。。。
by 为依相逢 @ 2019-03-02 10:38:47
@lyh0313 我看怎么是等价的。。。