图论专题A (网络流)

需要跑多遍的网络流，一个是注意bfs的时候deep不能用memset赋值，一个是每一次网络流的过程都会带来wei和cur的改变

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MAX=1e6+5;
 5 LL n,m,s,t,ans;
 6 LL tot,head[MAX],adj[MAX*6],wei[MAX*6],nxt[MAX*6];
 7 LL deep[MAX],cur[MAX];
 8 inline LL read(){
 9     LL an=0,x=1;char c=getchar();
10     while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
11     while (c>='0' && c<='9') {an=(an<<3)+(an<<1)+c-'0';c=getchar();}
12     return an*x;
13 }
14 void addedge(LL u,LL v,LL w){
15     tot++;adj[tot]=v,wei[tot]=w,nxt[tot]=head[u],head[u]=tot;
16 }
17 bool bfs(){
18     LL i,j,u;
19     for (i=1;i<=n;i++) deep[i]=1e9+10;
20     deep[s]=0;
21     queue  q;
22     while (!q.empty()) q.pop();
23     q.push(s);
24     while (!q.empty()){
25         u=q.front();q.pop();
26         for (i=head[u];i;i=nxt[i]){
27             if (deep[adj[i]]>1e9 && wei[i]>0)
28                 deep[adj[i]]=deep[u]+1,q.push(adj[i]);
29         }
30     }
31     return deep[t]<1e9;
32 }
33 LL dfs(LL x,LL flo){
34     if (x==t || flo==0) return flo;
35     LL j;
36     for (LL &i=cur[x];i;i=nxt[i])
37         if (deep[adj[i]]==deep[x]+1 && wei[i]>0){
38             j=dfs(adj[i],min(flo,wei[i]));
39             if (j) return wei[i]-=j,wei[i^1]+=j,j;
40         }
41     return 0;
42 }
43 int main(){
44     freopen ("a.in","r",stdin);freopen ("a.out","w",stdout);
45     LL i,j,u,v,w;
46     n=read();m=read();
47     LL flow=0,dd;ans=1e9;
48     tot=1;
49     for (i=1;i<=m;i++){
50         u=read();v=read();
51         addedge(u,v,1);
52         addedge(v,u,1);
53     }
54     for (i=1;i<=n;i++) cur[i]=head[i];
55     for (t=2;t<=n;t++){
56         s=1;
57         for (i=1;i<=tot;i++) wei[i]=1;
58         flow=0;
59         while (bfs()){
60             for (i=1;i<=n;i++) cur[i]=head[i];
61             while (dd=dfs(s,1e9)) flow+=dd;
62         }
63         ans=min(ans,flow);
64     }
65     printf("%lld",ans);
66     return 0;
67 }