网络流模板

 1 struct MF {
 2     static const int N=1e5+10,M=1e5+10;
 3     int hd[N],ne,cur[N],n;
 4     int d[N];
 5     struct E {int v,cp,nxt;} e[M];
 6     void init(int _n) {ne=0,n=_n; for(int i=1; i<=n; ++i)hd[i]=-1;}
 7     void link(int u,int v,int cp) {
 8         e[ne]= {v,cp,hd[u]},hd[u]=ne++;
 9         e[ne]= {u,0,hd[v]},hd[v]=ne++;
10     }
11     int bfs(int s,int t) {
12         queue<int> q;
13         for(int i=1; i<=n; ++i)d[i]=-1;
14         d[s]=0,q.push(s);
15         while(q.size()) {
16             int u=q.front();
17             q.pop();
18             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i].cp) {
19                     int v=e[i].v;
20                     if(!~d[v])d[v]=d[u]+1,q.push(v);
21                 }
22         }
23         return ~d[t];
24     }
25     int dfs(int u,int t,int f) {
26         if(u==t||!f)return f;
27         int ret=0;
28         for(int& i=cur[u]; ~i; i=e[i].nxt) {
29             int v=e[i].v;
30             if(d[v]==d[u]+1) {
31                 int df=dfs(v,t,min(f,e[i].cp));
32                 e[i].cp-=df,e[i^1].cp+=df,f-=df,ret+=df;
33                 if(!f)return ret;
34             }
35         }
36         return ret;
37     }
38     int dinic(int s,int t) {
39         int ret=0;
40         while(bfs(s,t)) {
41             for(int i=1; i<=n; ++i)cur[i]=hd[i];
42             ret+=dfs(s,t,inf);
43         }
44         return ret;
45     }
46 } mf;

 1 struct MCMF {
 2     static const int N=1e5+10,M=1e5+10;
 3     int hd[N],ne,n,d[N],h[N],vis[N],cur[N],C,F,S,T;
 4     struct E {int v,c,cp,nxt;} e[M];
 5     void init(int _n,int _S,int _T) {
 6         n=_n,S=_S,T=_T,ne=0;
 7         for(int i=1; i<=n; ++i)hd[i]=-1,vis[i]=0;
 8     }
 9     void link(int u,int v,int c,int cp) {
10         e[ne]= {v,c,cp,hd[u]},hd[u]=ne++;
11         e[ne]= {u,-c,0,hd[v]},hd[v]=ne++;
12     }
13     struct D {
14         int u,g;
15         bool operator<(const D& b)const {return g>b.g;}
16     };
17     priority_queue<D> q;
18     void upd(int u,int c) {if(d[u]>c)d[u]=c,q.push({u,d[u]});}
19     int Dij() {
20         while(q.size())q.pop();
21         for(int i=1; i<=n; ++i)d[i]=inf;
22         upd(T,0);
23         while(q.size()) {
24             int u=q.top().u,g=q.top().g;
25             q.pop();
26             if(g>d[u])continue;
27             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i^1].cp) {
28                     int v=e[i].v,c=e[i^1].c+h[u]-h[v];
29                     upd(v,g+c);
30                 }
31         }
32         return d[S]<inf;
33     }
34     int dfs(int u,int f) {
35         if(u==T) {F+=f,C+=h[S]*f; return f;}
36         vis[u]=1;
37         int ret=0;
38         for(int& i=cur[u]; ~i; i=e[i].nxt)if(e[i].cp) {
39                 int v=e[i].v,c=e[i].c;
40                 if(!vis[v]&&h[u]==h[v]+c) {
41                     int df=dfs(v,min(f,e[i].cp));
42                     e[i].cp-=df,e[i^1].cp+=df,f-=df,ret+=df;
43                     if(!f)break;
44                 }
45             }
46         vis[u]=0;
47         return ret;
48     }
49     void work() {
50         C=F=0;
51         while(Dij()) {
52             for(int i=1; i<=n; ++i)h[i]+=d[i],cur[i]=hd[i];
53             while(dfs(S,inf));
54         }
55     }
56 } mcmf;

 1 struct MCMF {
 2     static const int N=1e5+10,M=1e5+10;
 3     int hd[N],ne,n,d[N],h[N],cur[N],g[N],C,F,S,T;
 4     struct E {int v,c,cp,nxt;} e[M];
 5     void init(int _n,int _S,int _T) {
 6         n=_n,S=_S,T=_T,ne=0;
 7         for(int i=1; i<=n; ++i)hd[i]=-1;
 8     }
 9     void link(int u,int v,int c,int cp) {
10         e[ne]= {v,c,cp,hd[u]},hd[u]=ne++;
11         e[ne]= {u,-c,0,hd[v]},hd[v]=ne++;
12     }
13     struct D {
14         int u,g;
15         bool operator<(const D& b)const {return g>b.g;}
16     };
17     priority_queue<D> q;
18     queue<int> qq;
19     void upd(int u,int c) {if(d[u]>c)d[u]=c,q.push({u,d[u]});}
20     int Dij() {
21         while(q.size())q.pop();
22         for(int i=1; i<=n; ++i)d[i]=inf;
23         upd(T,0);
24         while(q.size()) {
25             int u=q.top().u,g=q.top().g;
26             q.pop();
27             if(g>d[u])continue;
28             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i^1].cp) {
29                     int v=e[i].v,c=e[i^1].c+h[u]-h[v];
30                     upd(v,g+c);
31                 }
32         }
33         return d[S]<inf;
34     }
35     int bfs() {
36         for(int i=1; i<=n; ++i)g[i]=-1;
37         g[S]=0,qq.push(S);
38         while(qq.size()) {
39             int u=qq.front();
40             qq.pop();
41             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i].cp) {
42                     int v=e[i].v,c=e[i].c;
43                     if(!~g[v]&&h[u]==h[v]+c)g[v]=g[u]+1,qq.push(v);
44                 }
45         }
46         return ~g[T];
47     }
48     int dfs(int u,int f) {
49         if(u==T) {F+=f,C+=h[S]*f; return f;}
50         int ret=0;
51         for(int& i=cur[u]; ~i; i=e[i].nxt)if(e[i].cp) {
52                 int v=e[i].v,c=e[i].c;
53                 if(h[u]==h[v]+c&&g[v]==g[u]+1) {
54                     int df=dfs(v,min(f,e[i].cp));
55                     e[i].cp-=df,e[i^1].cp+=df,f-=df,ret+=df;
56                     if(!f)break;
57                 }
58             }
59         return ret;
60     }
61     void work() {
62         C=F=0;
63         while(Dij()) {
64             for(int i=1; i<=n; ++i)h[i]+=d[i];
65             while(bfs()) {
66                 for(int i=1; i<=n; ++i)cur[i]=hd[i];
67                 dfs(S,inf);
68             }
69         }
70     }
71 } mcmf;

  1 template<class D>
  2 class Heap {
  3     static const int N=1e5+10;
  4     int n;
  5     D a[N];
  6     int l(int u) {return u<<1;}
  7     int r(int u) {return u<<1|1;}
  8     int fa(int u) {return u>>1;}
  9 public:
 10     Heap() {n=0;}
 11     int size() {return n;}
 12     D top() {return a[1];}
 13     void push(D x) {
 14         a[++n]=x;
 15         for(int u=n; u!=1&&a[fa(u)]<a[u]; u=fa(u))swap(a[u],a[fa(u)]);
 16     }
 17     void pop() {
 18         a[1]=a[n--];
 19         for(int u=1;;) {
 20             int t=u;
 21             if(l(u)<=n&&a[t]<a[l(u)])t=l(u);
 22             if(r(u)<=n&&a[t]<a[r(u)])t=r(u);
 23             if(t==u)break;
 24             swap(a[u],a[t]),u=t;
 25         }
 26     }
 27 };
 28 template<class D>
 29 class Queue {
 30     static const int N=1e5+10;
 31     int hd,tl;
 32     D a[N];
 33 public:
 34     Queue() {hd=tl=0;}
 35     int size() {return tl>=hd?tl-hd:tl-hd+N;}
 36     D front() {return a[hd];}
 37     void push(D x) {a[tl++]=x; if(tl==N)tl-=N;}
 38     void pop() {hd++; if(hd==N)hd-=N;}
 39 };
 40 struct MCMF {
 41     static const int N=1e5+10,M=1e5+10;
 42     int hd[N],ne,n,d[N],h[N],cur[N],g[N],C,F,S,T;
 43     struct E {int v,c,cp,nxt;} e[M];
 44     void init(int _n,int _S,int _T) {
 45         n=_n,S=_S,T=_T,ne=0;
 46         for(int i=1; i<=n; ++i)hd[i]=-1;
 47     }
 48     void link(int u,int v,int c,int cp) {
 49         e[ne]= {v,c,cp,hd[u]},hd[u]=ne++;
 50         e[ne]= {u,-c,0,hd[v]},hd[v]=ne++;
 51     }
 52     struct D {
 53         int u,g;
 54         bool operator<(const D& b)const {return g>b.g;}
 55     };
 56     Heap<D> q;
 57     Queue<int> qq;
 58     void upd(int u,int c) {if(d[u]>c)d[u]=c,q.push({u,d[u]});}
 59     int Dij() {
 60         while(q.size())q.pop();
 61         for(int i=1; i<=n; ++i)d[i]=inf;
 62         upd(T,0);
 63         while(q.size()) {
 64             int u=q.top().u,g=q.top().g;
 65             q.pop();
 66             if(g>d[u])continue;
 67             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i^1].cp) {
 68                     int v=e[i].v,c=e[i^1].c+h[u]-h[v];
 69                     upd(v,g+c);
 70                 }
 71         }
 72         return d[S]<inf;
 73     }
 74     int bfs() {
 75         for(int i=1; i<=n; ++i)g[i]=-1;
 76         g[S]=0,qq.push(S);
 77         while(qq.size()) {
 78             int u=qq.front();
 79             qq.pop();
 80             for(int i=hd[u]; ~i; i=e[i].nxt)if(e[i].cp) {
 81                     int v=e[i].v,c=e[i].c;
 82                     if(!~g[v]&&h[u]==h[v]+c)g[v]=g[u]+1,qq.push(v);
 83                 }
 84         }
 85         return ~g[T];
 86     }
 87     int dfs(int u,int f) {
 88         if(u==T) {F+=f,C+=h[S]*f; return f;}
 89         int ret=0;
 90         for(int& i=cur[u]; ~i; i=e[i].nxt)if(e[i].cp) {
 91                 int v=e[i].v,c=e[i].c;
 92                 if(h[u]==h[v]+c&&g[v]==g[u]+1) {
 93                     int df=dfs(v,min(f,e[i].cp));
 94                     e[i].cp-=df,e[i^1].cp+=df,f-=df,ret+=df;
 95                     if(!f)break;
 96                 }
 97             }
 98         return ret;
 99     }
100     void work() {
101         C=F=0;
102         while(Dij()) {
103             for(int i=1; i<=n; ++i)h[i]+=d[i];
104             while(bfs()) {
105                 for(int i=1; i<=n; ++i)cur[i]=hd[i];
106                 dfs(S,inf);
107             }
108         }
109     }
110 } mcmf;