网络流SAP--模板
1 #include<stdio.h>2 #include<iostream>
3 #include<algorithm>
4 using namespace std;
5 typedefstruct {int v,next,val;} edge;
6 const int MAXN=20010;
7 const int MAXM=500010;
8 edge e;
9 int p,eid;
10 inline void init(){memset(p,-1,sizeof(p));eid=0;}
11 //有向
12 inline void insert1(int from,int to,int val)
13 {
14 e.v=to;
15 e.val=val;
16 e.next=p;
17 p=eid++;
18 swap(from,to);
19 e.v=to;
20 e.val=0;
21 e.next=p;
22 p=eid++;
23 }
24 //无向
25 inline void insert2(int from,int to,int val)
26 {
27 e.v=to;
28 e.val=val;
29 e.next=p;
30 p=eid++;
31 swap(from,to);
32 e.v=to;
33 e.val=val;
34 e.next=p;
35 p=eid++;
36 }
37 int n,m;//n为点数 m为边数
38 int h;
39 int gap;
40 int source,sink;
41 inline int dfs(int pos,int cost)
42 {
43 if (pos==sink)
44 {
45 return cost;
46 }
47 int j,minh=n-1,lv=cost,d;
48 for (j=p;j!=-1;j=e.next)
49 {
50 int v=e.v,val=e.val;
51 if(val>0)
52 {
53 if (h+1==h)
54 {
55 if (lv<e.val) d=lv;
56 else d=e.val;
57
58 d=dfs(v,d);
59 e.val-=d;
60 e.val+=d;
61 lv-=d;
62 if (h>=n) return cost-lv;
63 if (lv==0) break;
64 }
65 if (h<minh) minh=h;
66 }
67 }
68 if (lv==cost)
69 {
70 --gap];
71 if (gap]==0) h=n;
72 h=minh+1;
73 ++gap];
74 }
75 return cost-lv;
76 }
77 int sap(int st,int ed)
78 {
79 source=st;
80 sink=ed;
81 int ret=0;
82 memset(gap,0,sizeof(gap));
83 memset(h,0,sizeof(h));
84 gap=n;
85 while (h<n)
86 {
87 ret+=dfs(st,INT_MAX);
88 }
89 return ret;
90 }
91 int main()
92 {
93 int t,add=1;
94 scanf("%d",&t);
95 while(t--)
96 {
97 printf("Case %d: ",add++);
98 scanf("%d%d",&n,&m);
99 init();
100 int i;
101 int ll,rr,cap;
102 for(i=0;i<m;i++)
103 {
104 scanf("%d%d%d",&ll,&rr,&cap);
105 insert1(ll,rr,cap);
106 }
107 printf("%d\n",sap(1,n));
108 }
109 return 0;
110 }
页:
[1]