网络流（关键边&判定）
关键边
我们把增加一条路径的流量，可以增大最大流的流量，那么我们就可以把这条边称为关键边，在做完一次dinic之后如何在残留网络中去判定是否是关键边呢？首先一条关键边的流量肯定是流满的，不然就不需要增加流量了，其次可能存在路径有2条以上流满的情况，因此也要排除这种可能，第三种是判定在不同的最大可行流中保证关键边是一致的，我们可以用割去证明，如果存在那么肯定存在增广路径，所以关键边是确定的。我们可以先求一次dinic，判断边如果流满了，同时S可以到边左端点，T可到右端点，那么就是一条关键边。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=510,M=1e4+10;
int n,m,S,T;
int head[N],idx,q[N],d[N],cur[N];
bool vis_s[N],vis_t[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1;
edge[i].f-=t; edge[i^1].f+=t; flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
void dfs(int u,bool st[],int t)
{
st[u]=true;
for(int i=head[u];~i;i=edge[i].next)
{
int j=i^t,ver=edge[i].to;
if(edge[j].f&&!st[ver])
dfs(ver,st,t);
}
}
int main()
{
memset(head,-1,sizeof head);
memset(vis_s,false,sizeof vis_s);
memset(vis_t,false,sizeof vis_t);
scanf("%d%d",&n,&m);
S=0,T=n-1;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dinic();
dfs(S,vis_s,0);
dfs(T,vis_t,1);
int res=0;
for(int i=0;i<idx;i+=2)
if(!edge[i].f&&vis_s[edge[i^1].to]&&vis_t[edge[i].to])
res++;
printf("%d\n",res);
return 0;
}最大流判定
最大流判定一般和二分枚举倍增结合起来，根据增加残留网络或者重改网络情况来进行最大流的判定。比如在一个有权图中选择若干的边，同时每条边可以用一次，选择边权最小的边使得图可以从S走N次到T。思路是进行边权的二分，根据边权进行二分，然后建图，做一个lower_bound。
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=210,M=1e5;
int n,m,k,S,T;
int head[N],idx;
int q[N],d[N],cur[N];
struct Edge{
int next,to,len,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c,0},head[a]=idx++;
edge[idx]=(Edge){head[b],a,c,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,cur[S]=head[S],d[S]=0;
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
cur[ver]=head[ver];
d[ver]=d[t]+1;
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(limit-flow,edge[i].f));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int flow,res=0;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
bool check(int mid)
{
for(int i=0;i<idx;i++)
if(edge[i].len<=mid) edge[i].f=1;
else edge[i].f=0;
return dinic()>=k;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d%d",&n,&m,&k);
S=1,T=n;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
int L=1,R=1e6;
while(L<R)
{
int mid=L+R>>1;
if(check(mid)) R=mid;
else L=mid+1;
}
printf("%d\n",L);
return 0;
}
