1 #include<vector> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define INF 0x7fffffff 6 #define MAX_V 210 7 8 using namespace std; 9 10 //用于表示边的结构体 11 struct edge 12 { 13 int to; //终点 14 int cap; //容量 15 int rev; //反向边 16 }; 17 18 int m,n; 19 int iter[MAX_V]; //顶点到源咪的距离标号 20 int level[MAX_V]; //当前弧，在其之前的边已经没有用了 21 vector<edge> G[MAX_V]; //图的邻接表表示，多组测试数据时注意初始化（清空） 22 23 //向图中增加一条从from到to的容量为cap的边 24 void add_edge(int _from,int _to,int _cap) 25 { 26 edge temp; 27 temp.to=_to; 28 temp.cap=_cap; 29 temp.rev=G[_to].size(); 30 G[_from].push_back(temp); 31 temp.to=_from; 32 temp.cap=0; 33 temp.rev=G[_from].size()-1; 34 G[_to].push_back(temp); 35 } 36 37 //通过BFS计算从源点出发的距离标号 38 void bfs(int s) 39 { 40 memset(level,-1,sizeof(level)); 41 queue<int> que; 42 level[s]=0; 43 que.push(s); 44 while(!que.empty()) 45 { 46 int v=que.front(); 47 que.pop(); 48 for(int i=0;i<G[v].size();i++) 49 { 50 edge &e=G[v][i]; 51 if(e.cap>0&&level[e.to]<0) 52 { 53 level[e.to]=level[v]+1; 54 que.push(e.to); 55 } 56 } 57 } 58 } 59 60 //通过DFS寻找增广路 61 int dfs(int v,int t,int f) 62 { 63 if(v==t) 64 return f; 65 66 for(int &i=iter[v];i<G[v].size();i++) 67 { 68 edge &e=G[v][i]; 69 if(e.cap>0&&level[v]<level[e.to]) 70 { 71 int d=dfs(e.to,t,min(f,e.cap)); 72 if(d>0) 73 { 74 e.cap-=d; 75 G[e.to][e.rev].cap+=d; 76 return d; 77 } 78 } 79 } 80 81 return 0; 82 } 83 84 //求解从s到t的最大流 85 int max_flow(int s,int t) 86 { 87 int flow=0; 88 89 while(true) 90 { 91 bfs(s); 92 if(level[t]<0) 93 return flow; 94 memset(iter,0,sizeof(iter)); 95 int f; 96 while((f=dfs(s,t,INF))>0) 97 flow+=f; 98 } 99 }