先最大流跑一遍
在残存网络上把满流边容量+1
非满流边容量设为无穷大
在进行一次最大流即可
（这里的边都不包括建图时用于反悔的反向边）
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<iostream>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
const int MAXN=;
int tmp,m,n,S,T,Ans;
int tot=,ans=,Maxflow=;
int h[MAXN];
int pointer[MAXN];
int a[MAXN],path[MAXN];
const int INF=~0U>>;
struct Edge{
int next,to;
int cap,op; //op指向反向边 cap为容量 f为流量
int f;
Edge() {};
Edge(int b,int c,int nxt,int num,int flow) {to=b,cap=c,next=nxt,op=num^,f=flow;}
}edge[MAXN*];
void addedge(int a,int b,int c) //a到b容量为c
{
edge[tot]=Edge(b,c,pointer[a],tot,);
pointer[a]=tot++;
edge[tot]=Edge(a,,pointer[b],tot,); //建立b到a的反向边
pointer[b]=tot++;
}
void Input()
{
memset(pointer,-,sizeof(pointer));
Maxflow=,tot=;
scanf("%d%d",&n,&m);
scanf("%d%d",&S,&T);
int u,v,w;
rep(i,,m)
{
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
}
}
bool Dinic_restruct() //bfs建立层次图
{
queue <int>q;
memset(h,-,sizeof(h));
h[S]=;q.push(S);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=pointer[u];i!=-;i=edge[i].next)
{
int v=edge[i].to;
if(h[v]==-&&edge[i].cap-edge[i].f)
{
h[v]=h[u]+;
q.push(v);
// printf("v=%d T=%d u=%d\n",v,T,u);
if(v==T) return true;
}
}
}
return false;
}
void Dinic_augment() //dfs找最短增光路
{
int i,j,f,Stop=;
a[Stop]=S;
while(Stop)
{
i=a[Stop];
// printf("augment i=%d\n",i);
if(i!=T) //没到T就走一步,dfs
{
int v;
for(j=pointer[i];j!=-;j=edge[j].next)
{
v=edge[j].to;
if(h[v]==h[i]+&&edge[j].cap-edge[j].f) break;
}
if(j!=-)
{
a[++Stop]=v;
path[Stop]=j;
}
else //回退
{ Stop--;
h[i]=-;
// printf("-1 augment i=%d\n",i);
}
}
else //找到了一条完整的路径
{
f=INF;
for(i=Stop;i>=;i--)
{
int &t=path[i];
if(edge[t].cap-edge[t].f<f)
f=edge[t].cap-edge[t].f;
}
Maxflow+=f;
for(int i=Stop;i>=;i--)
{
int &t=path[i];
edge[t].f+=f;
edge[t^].f-=f; //反向边
if(edge[t].cap-edge[t].f==) Stop=i-;
}
}
}
}
void Dinic()
{
while(Dinic_restruct())
Dinic_augment(); }
int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
rep(t1,,T)
{
Input();
Dinic();
// printf("ok? Maxflow=%d\n",Maxflow);
for(int i=;i<tot;i+=)
{
// printf("i=%d to=%d w=%d\n",i,edge[i].to,edge[i].cap-edge[i].f);
if((edge[i].cap-edge[i].f)==)
{
edge[i].cap+=;
}
else
{
edge[i].cap=INF;
}
}
Maxflow=;
Dinic();
printf("%d\n",Maxflow);
}
return ;
}