首页 > 代码库 > 【不可能的任务8/200】hdu1532网络流
【不可能的任务8/200】hdu1532网络流
(双倍经验题)
第二次写dinic模板,居然一遍写对了,而且短了不少O(∩_∩)O~
1 #include <cstdio> 2 #define INF 2147483647 3 int n,m,ans,x,y,z,M,h,t;long long zl; 4 int d[201],l[300],fir[201],nex[500],to[500],wei[500]; 5 inline int min(int a,int b){if(a<b) return a;else return b;} 6 inline void add(int x,int y,int z){to[++M]=y;wei[M]=z;nex[M]=fir[x];fir[x]=M;} 7 long long dfs(int now,long long flow,long long sum) 8 { 9 if(now==n) return flow;10 for(int i=fir[now];i && flow;i=nex[i])11 if(d[to[i]]==d[now]+1 && wei[i])12 zl=dfs(to[i],min(flow,wei[i]),0),sum+=zl,flow-=zl,wei[i]-=zl,wei[i^1]+=zl;13 return sum;14 }15 bool bfs()16 {17 for(int i=1;i<=n;i++) d[i]=0;18 for(h=1,t=1,l[1]=1,d[1]=1;h<=t;h++)19 for(int i=fir[l[h]];i;i=nex[i])20 if(!d[to[i]] && wei[i])21 l[++t]=to[i],d[l[t]]=d[l[h]]+1;22 return d[n];23 }24 int main()25 {26 while(~scanf("%d%d",&m,&n))27 {28 for(int i=1;i<=n;i++) fir[i]=0;29 for(ans=0,M=1;m;m--)30 scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,0);31 while(bfs()) ans+=dfs(1,INF,0);32 printf("%d\n",ans);33 }34 return 0;35 }
不要管long long,纯属发神经写上去的
【不可能的任务8/200】hdu1532网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。