1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <map> 5 #include <algorithm> 6 #include <queue> 7 using namespace std; 8  9 const int N = 210;10 const int M=1001000;11 const int INF = 1001001010;12 struct edge{13     int u,v,cap,flow;14     int next;15 16     //////17 }e[M];18 int head[N],num;19 int cur[N],d[N];20 bool vis[N];21 int s,t;22 void _add(int u,int v,int cap){23     e[num].u = u;e[num].v = v;24     e[num].cap = cap;e[num].flow = 0;25     e[num].next = head[u];26 27     //////28     head[u] = num++;29 }30 31 void add(int u,int v,int cap){32     _add(u,v,cap); _add(v,u,0);33 }34 35 bool BFS(){36     memset(vis,0,sizeof(vis));37     queue<int> Q;38     Q.push(s);39     d[s] = 0;40     vis[s]=1;41     while(!Q.empty()){42         int x = Q.front(); Q.pop();43         for(int i = head[x]; i != -1;i = e[i].next){44             if(!vis[e[i].v] && e[i].cap > e[i].flow ){45                 vis[e[i].v] = 1;46                 d[e[i].v] = d[x] + 1;47                 Q.push(e[i].v);48             }49         }50     }51     return vis[t];52 }53 54 int DFS(int x, int a){55     if(x == t || a == 0) return a;56     int flow=0,f;57 58     for(int &i = cur[x]; i != -1; i = e[i].next){59         if(d[x] + 1 == d[e[i].v] && (f = DFS(e[i].v, min(a, e[i].cap - e[i].flow))) > 0){60             e[i].flow += f;61             e[i ^ 1].flow -= f;62             flow += f;63             a -= f;64             if(a == 0)break;65         }66     }67     return flow;68 }69 int Dinic(){70     int flow = 0;71     while(BFS()){72         memcpy(cur,head,sizeof(head));73         flow += DFS(s,INF);74     }75     return flow;76 }77 void init(int n){78     memset(head,-1,sizeof(head));79     num=0;80 }