首页 > 代码库 > 【网络流#3】hdu 1532 - Dinic模板题

【网络流#3】hdu 1532 - Dinic模板题

2024-07-27 23:56:27   221人阅读

输入为m,n表示m条边，n个结点

记下来m行，每行三个数，x,y,c表示x到y的边流量最大为c

这道题的模板来自于网络

http://blog.csdn.net/sprintfwater/article/details/7913061

建议大家去这个页面看看，博主也很良心地添加了很多注释

 

关于这个模板：
Edge为前向星的边数，所以需要初始化Edge和head数组
n表示有n个点，这个版无所谓点从0开始还是从1开始，s表示源点，t表示汇点
很好的一个是，这个版的DFS使用的是模拟栈，防止爆栈

  1 #include<cstdio>  2 #include<cstring>  3 #include<cmath>  4 #include<iostream>  5 #include<algorithm>  6 #include<set>  7 #include<map>  8 #include<stack>  9 #include<vector> 10 #include<queue> 11 #include<string> 12 #include<sstream> 13 #define MAXN 200 14 #define MAXM 400 15 #define INF (1<<30) 16 #define eps 0.000001 17 #define ALL(x) x.begin(),x.end() 18 #define INS(x) inserter(x,x.begin()) 19 using namespace std; 20 int i,j,k,n,m,x,y,T,num,w; 21  22 const int inf = 0x3f3f3f3f; 23 struct edgenode 24 { 25     int from,to,next; 26     int cap; 27 }edge[MAXM]; 28 int Edge,head[MAXN],ps[MAXN],dep[MAXN]; 29  30 void addedge(int x,int y,int c) 31 { 32     edge[Edge].from=x; 33     edge[Edge].to=y; 34     edge[Edge].cap=c; 35     edge[Edge].next=head[x]; 36     head[x]=Edge++; 37      38     edge[Edge].from=y; 39     edge[Edge].to=x; 40     edge[Edge].cap=0; 41     edge[Edge].next=head[y]; 42     head[y]=Edge++; 43 } 44  45 int dinic(int n,int s,int t) 46 { 47     int tr,flow=0; 48     int i,j,k,l,r,top; 49     while(1){ 50         memset(dep,-1,(n+1)*sizeof(int)); 51         for(l=dep[ps[0]=s]=0,r=1;l!=r;)//BFS部分，将给定图分层  52         { 53             for(i=ps[l++],j=head[i];j!=-1;j=edge[j].next) 54             { 55                 if (edge[j].cap&&-1==dep[k=edge[j].to]) 56                 { 57                     dep[k]=dep[i]+1;ps[r++]=k; 58                     if(k==t) 59                     { 60                         l=r; 61                         break; 62                     } 63                 } 64             } 65         } 66         if(dep[t]==-1)break; 67          68         for(i=s,top=0;;)//DFS部分  69         { 70             if(i==t)//当前点就是汇点时  71             { 72                 for(k=0,tr=inf;k<top;++k) 73                     if(edge[ps[k]].cap<tr)tr=edge[ps[l=k]].cap; 74                      75                 for(k=0;k<top;++k) 76                     edge[ps[k]].cap-=tr,edge[ps[k]^1].cap+=tr; 77                      78                 flow+=tr; 79                 i=edge[ps[top=l]].from; 80             } 81              82             for(j=head[i];j!=-1;j=edge[j].next)//找当前点所指向的点  83                 if(edge[j].cap&&dep[i]+1==dep[edge[j].to]) break; 84                  85             if(j!=-1) 86             { 87                 ps[top++]=j;//当前点有所指向的点，把这个点加入栈中  88                 i=edge[j].to; 89             } 90             else 91             {  92                 if (!top) break;//当前点没有指向的点，回溯  93                 dep[i]=-1; 94                 i=edge[ps[--top]].from; 95             } 96         } 97     } 98     return flow; 99 }100 101 int main()102 {103     int T,cas,m,s,t,n,maxflow,i;104     int x,y,c;105     double ans;106     while(~scanf("%d%d",&m,&n))107     {   108         memset(head,-1,sizeof(head));109         Edge=0;110         for(i=0;i<m;i++)111         {112             scanf("%d%d%d",&x,&y,&c);113             addedge(x,y,c);114         }115         printf("%d\n",dinic(n,1,n));116     }117     return 0;118 }
View Code

 

【网络流#3】hdu 1532 - Dinic模板题


联系
我们