最大流/最小割模板(isap) POJ1273

isap模板核心代码:

 1 //d[]为距离标号数组,d[i]表示节点i到汇点的距离 
 2 //gap[]为GAP优化数组,gap[i]表示到汇点距离为i的节点个数 
 3 int dfs(int k,int flow){//flow为当前剩余流量 
 4     int i;
 5     if(k==t)return flow;
 6     int sum=0;
 7     for(i=head[k];i;i=e[i].nxt){
 8         int v=e[i].to;
 9         if(e[i].f&&d[k]==d[v]+1){//判断能否通过流量以及走的是否为最短路 
10             int f=dfs(v,min(flow-sum,e[i].f));//注意是flow-sum,要将已用过的流量减去 
11             sum+=f;head[k]=i;//当前弧优化 
12             e[i].f-=f;e[i^1].f+=f;
13             if(sum==flow||d[s]==cnt)return sum;//流量全部流完或者达到退出条件则返回 
14         }
15     }
16     if((--gap[d[k]])==0)d[s]=cnt;//若gap[]出现断层,则无法增广 
17     gap[++d[k]]++;//
18     head[k]=h[k];//
19     return sum;
20 }
21 
22 int sap(){
23     memcpy(h,head,sizeof(head));
24     memset(d,0,sizeof(d));
25     memset(gap,0,sizeof(gap));
26     gap[0]=cnt;
27     int flow=0;
28     while(d[s]<cnt)
29         flow+=dfs(s,inf);
30     return flow;
31 }

一道水题:poj1273

题意:现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的点和所能流过的最大流量,求从源点到汇点能流过的最大流量。

有多组数据!网上查的中文题意没说,样例只给了一组,WA。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define repu(i,x,y) for(int i=x;i<=y;i++)
 6 using namespace std;
 7 
 8 struct edge{int to,nxt,f;}e[1000];
 9 const int inf=1e9;
10 int head[500],h[500],d[500],gap[500],n,m,ne=1,s,t,cnt;
11 
12 void add(int u,int v,int f){
13     e[++ne]=(edge){v,head[u],f};head[u]=ne;
14 }
15 
16 //d[]为距离标号数组,d[i]表示节点i到汇点的距离 
17 //gap[]为GAP优化数组,gap[i]表示到汇点距离为i的节点个数 
18 int dfs(int k,int flow){//flow为当前剩余流量 
19     int i;
20     if(k==t)return flow;
21     int sum=0;
22     for(i=head[k];i;i=e[i].nxt){
23         int v=e[i].to;
24         if(e[i].f&&d[k]==d[v]+1){//判断能否通过流量以及走的是否为最短路 
25             int f=dfs(v,min(flow-sum,e[i].f));//注意是flow-sum,要将已用过的流量减去 
26             sum+=f;head[k]=i;//当前弧优化 
27             e[i].f-=f;e[i^1].f+=f;
28             if(sum==flow||d[s]==cnt)return sum;//流量全部流完或者达到退出条件则返回 
29         }
30     }
31     if((--gap[d[k]])==0)d[s]=cnt;//若gap[]出现断层,则无法增广 
32     gap[++d[k]]++;//
33     head[k]=h[k];//
34     return sum;
35 }
36 
37 int sap(){
38     memcpy(h,head,sizeof(head));
39     memset(d,0,sizeof(d));
40     memset(gap,0,sizeof(gap));
41     gap[0]=cnt;
42     int flow=0;
43     while(d[s]<cnt)
44         flow+=dfs(s,inf);
45     return flow;
46 }
47 
48 int main(){
49     int u,v,f;
50     while(scanf("%d%d",&n,&m)!=EOF){
51         ne=1;
52         memset(e,0,sizeof(e));
53         memset(head,0,sizeof(head));
54         repu(i,1,n){
55             scanf("%d%d%d",&u,&v,&f);
56             add(u,v,f);add(v,u,0);
57         }
58         cnt=m;s=1;t=m;
59         int ans=sap();
60         printf("%d
",ans);
61     }
62     return 0; 
63 }
【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/y-m-y/p/6370112.html