这里是Ford-Fulkerson写的最大流模板
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <list> #include <iterator> #include <cmath> using namespace std; #define lson (l , mid , rt << 1) #define rson (mid + 1 , r , rt << 1 | 1) #define debug(x) cerr << #x << " = " << x << " "; #define pb push_back #define pq priority_queue #define Pll pair<ll,ll> #define Pii pair<int,int> #define fi first #define se second #define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) typedef long long ll; typedef unsigned long long ull; const int inf = 0x3f3f3f3f; /*-----------------show time----------------*/ const int maxn = 1e3+9; struct node { int to,cap,rev; }; vector<node>mp[maxn]; bool used[maxn]; void add_edge(int from,int to,int cap) { mp[from].pb((node){to,cap,(int)mp[to].size()}); mp[to].pb((node){from,0,(int)mp[from].size()-1}); } int dfs(int v,int t,int f) { if(v==t)return f; used[v] = true; for(int i=0; i<mp[v].size(); i++) { node &e = mp[v][i]; if(!used[e.to] && e.cap>0) { int d = dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap -= d; mp[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t) { int flow = 0; for(;;) { memset(used,0,sizeof(used)); int f = dfs(s,t,inf); if(f==0)return flow; flow += f; } } int main(){ int t,n,m; scanf("%d", &t); for(int T=1; T<=t;T++) { scanf("%d%d", &n, &m); for(int i=0;i<=n;i++)mp[i].clear(); for(int i=1; i<=m; i++) { int u,v,c; scanf("%d%d%d", &u, &v, &c); add_edge(u,v,c); } printf("Case %d: %d ",T,max_flow(1,n)); } return 0; }