网络流SAP--模板

古城堡

1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 using namespace std;
  5 typedef  struct {int v,next,val;} edge;
  6 const int MAXN=20010;
  7 const int MAXM=500010;
  8 edge e[MAXM];
  9 int p[MAXN],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[eid].v=to;
15     e[eid].val=val;
16     e[eid].next=p[from];
17     p[from]=eid++;
18     swap(from,to);
19     e[eid].v=to;
20     e[eid].val=0;
21     e[eid].next=p[from];
22     p[from]=eid++;
23 }
24 //无向
25 inline void insert2(int from,int to,int val)
26 {
27     e[eid].v=to;
28     e[eid].val=val;
29     e[eid].next=p[from];
30     p[from]=eid++;
31     swap(from,to);
32     e[eid].v=to;
33     e[eid].val=val;
34     e[eid].next=p[from];
35     p[from]=eid++;
36 }
37 int n,m;//n为点数 m为边数
38 int h[MAXN];
39 int gap[MAXN];
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[pos];j!=-1;j=e[j].next)
49     {
50         int v=e[j].v,val=e[j].val;
51         if(val>0)
52         {
53             if (h[v]+1==h[pos])
54             {
55                 if (lv<e[j].val) d=lv;
56                 else d=e[j].val;
57                 
58                 d=dfs(v,d);
59                 e[j].val-=d;
60                 e[j^1].val+=d;
61                 lv-=d;
62                 if (h[source]>=n) return cost-lv;
63                 if (lv==0) break;
64             }
65             if (h[v]<minh)    minh=h[v];
66         }
67     }
68     if (lv==cost)
69     {
70         --gap[h[pos]];
71         if (gap[h[pos]]==0) h[source]=n;
72         h[pos]=minh+1;
73         ++gap[h[pos]];
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[st]=n;
85     while (h[st]<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 }