最大流 Dinic

 1 struct Dinic
 2 {
 3       struct node
 4       {
 5              int x,y,c,next;
 6       }line[MAXM];
 7       int Lnum,_next[MAXN],dis[MAXN],dp[MAXN];
 8       bool inqueue[MAXN];
 9       void initial(int n)
10       {
11              for (int i=0;i<=n;i++) _next[i]=-1;
12              Lnum=-1;
13       }
14       void addline(int x,int y,int c)
15       {
16              line[++Lnum].next=_next[x],_next[x]=Lnum;
17              line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c;
18              line[++Lnum].next=_next[y],_next[y]=Lnum;
19              line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0;
20       }
21       bool BFS(int s,int e)
22       {
23              queue<int> Q;
24              while (!Q.empty()) Q.pop();
25              memset(dis,0,sizeof(dis));
26              dis[s]=1,Q.push(s);
27              while (!Q.empty())
28              {
29                    int h,k;
30                    h=Q.front(),Q.pop();
31                    if (h==e) return dis[e];
32                    for (k=_next[h];k!=-1;k=line[k].next)
33                       if (line[k].c && !dis[line[k].y])
34                          dis[line[k].y]=dis[h]+1,Q.push(line[k].y);
35              }
36              return false;
37       }
38       int dfs(int x,int flow,int e)
39       {
40              if (x==e) return flow;
41              int temp,cost=0;
42              for (int k=_next[x];k!=-1;k=line[k].next)
43              if (line[k].c && dis[line[k].y]==dis[x]+1)
44              {
45                     temp=dfs(line[k].y,min(flow-cost,line[k].c),e);
46                     if (temp)
47                     {
48                            line[k].c-=temp,line[k^1].c+=temp;
49                            cost+=temp;
50                            if (flow==cost) return cost;
51                     }else dis[line[k].y]=-1;
52              }
53              return cost;
54       }
55       int MaxFlow(int s,int e)
56       {
57              int MaxFlow=0;
58              while (BFS(s,e)) MaxFlow+=dfs(s,oo,e);
59              return MaxFlow;
60       }
61 }T;
每次调用之前都要初始化 T.initial(最多节点);