Dinic 邻接表
（抄袭神牛的板子 传送门：https://blog.csdn.net/u013480600/article/details/38796521）
代码：
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <algorithm> #define zero(a) fabs(a)<eps #define lowbit(x) (x&(-x)) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define MOD 1000000007 int max(int x,int y){return x>y?x:y;}; int min(int x,int y){return x<y?x:y;}; int max(int x,int y,int z){return max(x,max(y,z));}; int min(int x,int y,int z){return min(x,min(y,z));}; typedef long long LL; const double PI=acos(-1.0); const double eps=1e-8; const int inf=0x3f3f3f3f; const LL linf=0x3f3f3f3f3f3f3f3fLL; using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } using namespace std; const int maxn=15+5; const int maxm=2000+10; struct Edge { Edge(){} Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){} int from,to,cap,flow; }; struct Dinic { int n,m,s,t; //结点数,边数(包括反向弧),源点与汇点编号 Edge edges[maxm]; //边表 edges[e]和edges[e^1]互为反向弧 int head[maxn],next[maxm]; //邻接表表头和next数组 bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过 int d[maxn]; //从起点到i点的距离 int cur[maxn]; //当前弧下标 void init(int n,int s,int t) { this->n=n,this->s=s,this->t=t; memset(head,-1,sizeof(head)); m=0; } void AddEdge(int from,int to,int cap) { edges[m]= Edge(from,to,cap,0) ; next[m]=head[from]; head[from]=m++; edges[m]= Edge(to,from,0,0) ; next[m]=head[to]; head[to]=m++; } bool BFS() { memset(vis,0,sizeof(vis)); queue<int> Q;//用来保存节点编号的 Q.push(s); d[s]=0; vis[s]=true; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=head[x]; i!=-1; i=next[i]) { Edge& e=edges[i]; if(!vis[e.to] && e.cap>e.flow) { vis[e.to]=true; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { if(x==t || a==0)return a; int flow=0,f;//flow用来记录从x到t的最小残量 for(int& i=cur[x]; i!=-1; i=next[i]) { Edge& e=edges[i]; if(d[x]+1==d[e.to] && (f=DFS( e.to,min(a,e.cap-e.flow) ) )>0 ) { e.flow +=f; edges[i^1].flow -=f; flow += f; a -= f; if(a==0) break; } } return flow; } int Maxflow() { int flow=0; while(BFS()) { for(int i=1;i<=n;i++) cur[i]=head[i]; flow += DFS(s,inf); } return flow; } }DC; int main() { int T; scanf("%d",&T); for(int kase=1; kase<=T; ++kase) { int n,m; scanf("%d%d",&n,&m); DC.init(n,1,n); while(m--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); DC.AddEdge(u,v,w); } printf("Case %d: %d ",kase,DC.Maxflow()); } return 0; }