本文纯粹保存Dinic的代码
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; struct edge{int to,cap,rev;}; #define N 210 #define inf 0x3fffffff vector<edge> g[N]; int cur[N],level[N]; int n,m; void add_edge(int from,int to,int cap) { g[from].push_back((edge){to,cap,g[to].size()}); g[to].push_back((edge){from,0,g[from].size()-1}); } int bfs(int s) { memset(level,-1,sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while(!q.empty()) { int v = q.front();q.pop(); for(int i = 0;i < g[v].size();i++) { edge &e = g[v][i]; if(e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } int dfs(int v,int t,int f) { if(v == t) return f; for(int &i = cur[v];i < g[v].size();i++) { edge &e = g[v][i]; if(e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to,t,min(f,e.cap)); if(d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } int Dinic(int s,int t) { int flow = 0; for(;;) { bfs(s); if(level[t] < 0) return flow; memset(cur,0,sizeof(cur)); int f; while((f = dfs(s,t,inf)) > 0) flow += f; } } int main() { int u,v,w; scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) { scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); add_edge(v,u,0); } printf("%d\n",Dinic(1,m) ); return 0; }