[POJ 3204] 求网络流的有效边**

【题目大意】给定一个流网络，让你求其中有多少条有效边。其中有效边的定义是：修改这条边的容量，可以使最大流增大。（只允许修改一条边）

【算法分析】如果你平常写网络流不都是写预留推进的话，这题应该难不倒你。。。
实际上呢，如果你把某一条边的容量增加了的话，如果最大流增大，那么必然是在当前流网络中能找到一条新的增广路（并且该增广路要经过你修改过的那条边）。而最大流的标志则是不能再找到增广路了。
于是我们得到这样一个算法：
选求最大流。
然后在残余网络中找满流边[X,Y]（如果是非满流边你增加它容量也没用。。。因为它的容量本来就过多了）
如果在残余网络中存在路径[S,X]和[Y,T]，那么这条边为有效边。

为什么？
因为如果你增加[X,Y]的容量，那么在存在增广路径[S,X]->[X,Y]->[Y,T]

这样我们就得到一个求有效边的算法。

但是如果你要Floyed的话。。。我不阻止你。。。
而我们其实存在更高效的方法，那就是先以S为起点DFS，然后将所有边反向，然后以T为起点dfs。
这样总复杂度就是O(maxflow)

【其它】1A
6393657 edward2 3204 Accepted 1752K 79MS G++ 2225B 2010-01-31 20:39:36
【CODE】
#include #include #include #define N 500
#define E 10001
struct gtp{int x,y,next,op,c;}g[E];
int n,m,e,ls[N],fa[N],cur[N],num[N],d[N],a[N][N],vs[N],vt[N],v[N];

void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

void init(){
scanf("%d%d",&n,&m);
for (int i=0;i int x,y,c;
scanf("%d%d%d",&x,&y,&c);
addedge(x,y,c);
}
}

void relabel(int k){
int mm=n;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && d[g[t].y] d[k]=mm+1;
}

void change(){
int nf=0x7FFFFFFF;
for (int i=n-1;i;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=n-1;i;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}

void sap(){
for (int i=0;i num[0]=n;
int i=0;
while (d[0] for (;cur[i];cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
if (!–num[d[i]]) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n-1){
change();
i=0;
}
}
}
}

void dfs(int k){
v[k]=1;
for (int i=0;i if (!v[i] && a[k][i]) dfs(i);
}

void work(){
memset(a,0,sizeof(a));
for (int i=1;i if (g[i].c) a[g[i].x][g[i].y]=1;
memset(v,0,sizeof(v));
dfs(0);
memcpy(vs,v,sizeof(v));

memset(a,0,sizeof(a));
for (int i=1;i if (g[i].c) a[g[i].y][g[i].x]=1;
memset(v,0,sizeof(v));
dfs(n-1);
memcpy(vt,v,sizeof(v));

int ans=0;
for (int i=1;i if (vs[g[i].x] && vt[g[i].y] && !g[i].c)
ans++;
printf("%dn",ans);
}

int main(){
init();
sap();
work();
}