题意分析

给定一个有向图 $G=(V, E)$，其中：

• 源点为 $0$，汇点为 $N-1$。
• 每条边 $e \in E$ 有一个容量 $c(e)$。
• 关键边：如果仅增加某条边 $e$ 的容量，整个网络的最大流 $f$ 能够增大，则称 $e$ 为关键边。

要求计算关键边的数量。

解题思路

1. 计算初始最大流
   使用 Dinic 算法 或 Edmonds-Karp 算法 计算初始最大流 $f$。

2. 残余网络分析

   • 在残余网络中，源点 $s$ 和汇点 $t$ 之间不存在增广路径（即 $s$ 和 $t$ 在残余网络中不连通）。
   • 关键边必须满足：
     • 该边在某个最小割中（即该边满流，且残余网络中无法绕过它）。
     • 增加该边的容量后，残余网络中可能产生新的增广路径。

3. 关键边的判定条件
   对于边 $(u, v)$，若满足：

   • 满流：$f(u, v) = c(u, v)$。
   • 在残余网络中 $u$ 可达 $s$，且 $t$ 可达 $v$（即 $u$ 在 $s$ 的连通分量，$v$ 在 $t$ 的连通分量）。
     则该边是关键边。

算法步骤

1. 计算初始最大流，并构建残余网络。
2. BFS/DFS 标记可达性：
   • 从 $s$ 出发，标记所有可达的节点（$s$ 的连通分量）。
   • 从 $t$ 出发，沿反向边标记所有可达的节点（$t$ 的连通分量）。
3. 遍历所有边，检查是否满足关键边条件：
   • 满流（$f(u, v) = c(u, v)$）。
   • $u$ 在 $s$ 的连通分量，$v$ 在 $t$ 的连通分量。

时间复杂度

• 最大流计算：Dinic 算法 $O(N^2 M)$（最坏情况），但实际运行较快。
• 残余网络分析：两次 BFS/DFS，$O(M)$。
• 总复杂度：$O(N^2 M)$，适用于 $N \leq 500$，$M \leq 5000$。

标程

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>

#define inf 0x3f3f3f3f
using namespace std;


const int maxn=500+5,maxm=5000*2+5;

int n,m,ans,cnt,S,T,hd[maxn],to[maxm],fl[maxm],nxt[maxm],pos[maxn],vis[maxn];

inline void add(int s,int x,int y){
	fl[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;
	fl[cnt]=0;to[cnt]=x;nxt[cnt]=hd[y];hd[y]=cnt++;
}

inline bool bfs(void){
	memset(pos,-1,sizeof(pos));
	int head=0,tail=0,q[maxn];
	q[0]=S;pos[S]=0;
	while(head<=tail){
		int top=q[head++];
		for(int i=hd[top];i!=-1;i=nxt[i])
			if(pos[to[i]]==-1&&fl[i])
				pos[to[i]]=pos[top]+1,q[++tail]=to[i];
	}
	return pos[T]!=-1;
}

inline int find(int v,int f){
	if(v==T)
		return f;
	int res=0,t;
	for(int i=hd[v];i!=-1&&f>res;i=nxt[i])
		if(pos[to[i]]==pos[v]+1&&fl[i])
			t=find(to[i],min(fl[i],f-res)),fl[i]-=t,fl[i^1]+=t,res+=t;
	if(!res)
		pos[v]=-1;
	return res;
}

inline void dinic(void){
	while(bfs())
		while(find(S,inf));
}

inline void BFS(void){
	memset(vis,0,sizeof(vis));
	queue<int> q;q.push(S);vis[S]=1;
	while(!q.empty()){
		int top=q.front();q.pop();
		for(int i=hd[top];i!=-1;i=nxt[i])
			if(fl[i]&&!vis[to[i]])
				vis[to[i]]=1,q.push(to[i]);
	}
	q.push(T),vis[T]=2;
	while(!q.empty()){
		int top=q.front();q.pop();
		for(int i=hd[top];i!=-1;i=nxt[i])
			if(fl[i^1]&&!vis[to[i]])
				vis[to[i]]=2,q.push(to[i]);
	}
}

signed main(void){
	memset(hd,-1,sizeof(hd));
	memset(pos,-1,sizeof(pos));
	scanf("%d%d",&n,&m);ans=cnt=0;
	for(int i=1,s,x,y;i<=m;i++)
		scanf("%d%d%d",&x,&y,&s),x++,y++,add(s,x,y);
	S=1,T=n;dinic();BFS();
	for(int i=1;i<=n;i++)
		for(int j=hd[i];j!=-1;j=nxt[j])
			if((j&1)==0&&!fl[j])
				ans+=((vis[i]==vis[S]&&vis[to[j]]==vis[T])?1:0);
	printf("%d\n",ans);
	return 0;
}