zoj2532:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1532
题意：有n个发射点，m个中继站，然后发射点会发射一些信息给汇点0，这些信息可能会经过中继站，然后给出l条边，每一条都有一个信息容量，现在问你改变哪些边中的任意一条都可以改变这n个点发射信息到0点的总和。
题解：首先，分析一下，要改变的这一条边具有一下性质：
1 这一条边一定是满流的，
2边的起点应该属于残余网络的源点部分，
3边的终点应该是属于残余网络的汇点部分。
所以建图的时候，设置超级源点ss，然后与每个发射点连接，容量是INF，然后跑网络流，从源点深搜，再从汇点神搜，最后遍历每一边，看是否满足以上3条性质。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define INF 100000000
using namespace std;
const int N=;
const int M=;
struct Node{
int v;
int f;
int next;
}edge[M];
int n,m,u,v,l,w,cnt,sx,ex;
int head[N],pre[N];
int ans[N],top;
int from[N],to[N];
bool vis1[N],vis2[N];
void init(){
cnt=;
memset(head,-,sizeof(head));
memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
}
void add(int u,int v,int w,int id){
edge[cnt].v=v;
edge[cnt].f=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool BFS(){
memset(pre,,sizeof(pre));
pre[sx]=;
queue<int>Q;
Q.push(sx);
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=head[d];i!=-;i=edge[i].next ){
if(edge[i].f&&!pre[edge[i].v]){
pre[edge[i].v]=pre[d]+;
Q.push(edge[i].v);
}
}
}
return pre[ex]>;
}
int dinic(int flow,int ps){
int f=flow;
if(ps==ex)return f;
for(int i=head[ps];i!=-;i=edge[i].next){
if(edge[i].f&&pre[edge[i].v]==pre[ps]+){
int a=edge[i].f;
int t=dinic(min(a,flow),edge[i].v);
edge[i].f-=t;
edge[i^].f+=t;
flow-=t;
if(flow<=)break;
} }
if(f-flow<=)pre[ps]=-;
return f-flow;
}
void solve(){
int sum=;
while(BFS())
sum+=dinic(INF,sx);
}
void DFS1(int u,int fa){
if(vis1[u])return;
vis1[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
if(edge[i].f>){
DFS1(edge[i].v,u);
}
}
}
void DFS2(int u,int fa){
if(vis2[u])return;
vis2[u]=;
for(int i=head[u];i!=-;i=edge[i].next){
if(edge[i^].f>){
DFS2(edge[i].v,u);
}
}
}
int main() {
while(~scanf("%d%d%d",&n,&m,&l)&&n) {
init();
for(int i=;i<=l;i++){
scanf("%d%d%d",&from[i],&to[i],&w);
add(from[i],to[i],w,i);
}
for(int i=;i<=n;i++){
add(m+n+,i,INF,);
}
sx=n+m+,ex=;
solve();
DFS1(sx,sx);
DFS2(ex,ex);
top=;
for(int i=;i<=l;i++){
int u=from[i],v=to[i];
if(vis1[u]&&vis2[v])
ans[++top]=i;
}
if(top==)puts("");
else{
sort(ans+,ans+top+);
for(int i=;i<top;i++)
printf("%d ",ans[i]);
printf("%d\n",ans[top]);
}
}
return ;
}