城市宽带网络，由于不够用，所以需要扩大某些线路的容量，这样就可以增大网络的流量，你的任务就是寻找到这些边使得这些边容量一扩充就能增大流量。
每个城市都是源点，所以建立超级源点S，然后求S到T的最大流，从S开始dfs把点染色为1，再从T开始dfs把点染色成2，如果我们能找到一条边u，v一边是1，一边是2的话，这条边就是关键割边。注意割边不一定是关键的，因为对它扩容之后，与他临接的可能还是满流。。
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
const int INF = 2100000000;
using namespace std;
//基本头文件
/*
NEED-TO-DO：添加最小割方法,
NEED-TO-KNOW:模板参数有两个，Vsize表示点的规模，Esize表示边的规模
（不用考虑反向边，已经*2了）
HOW-TO-USE：
1.首先实例化一个对象如Net
Network<110,20010> Net;
//我一般都在main函数外声明好，main里面反复用
2.初始化
Net.init( N );
//N表示所需要用到的点的个数，不用考虑他们下表开始时0还是1
3.加边
Net.add( from, to, w );//添加弧，这个不用说了吧
4.求最大流
Net.MaxFlowDinic( S, T );
Net.MaxFlowSap( S, T );
//内置两种算法可以用，dinic基本可以过所有题目了，sap用来刷版OvO
*/
class Arc{
public:
int from, to,w;
Arc *next,*anti;
Arc *ass(int ff, int tt,int ww,Arc* &b ){
from=ff;to = tt;w = ww;next = b;b = this;return this;
}
};
template< int Vsize, int Esize >
class Network{
private:
Arc A[ 2*Esize+10 ],*biao[ Vsize ];
int countt,d[ Vsize ],S,T,N;
int bfs( void ){
queue<int> q;
fill( d,d+Vsize,-1 );
d[ S ] = 0;
q.push( S );
while( !q.empty() ){
int u = q.front();q.pop();
for(Arc *p=biao[u];p!=NULL;p=p->next)
if( d[p->to] == -1 && p->w > 0 )
d[p->to] = d[u]+1,q.push(p->to);
}
return d[T] != -1;
}
int dinic( int u,int sum ){
int f,o;
if( u == T ) return sum;
o = sum;
for(Arc*p=biao[u];p!=NULL&∑p=p->next)
if( d[p->to] == d[u]+1 && p->w > 0 ){
f = dinic(p->to,min(p->w,sum));
p->w -= f;p->anti->w += f;
sum -= f;
}
return o-sum;
}
public:
Network( void ) {}
Network( int n ) { init(n) ;}
void init( int n ){
countt = 0;N = n;
for( int i = 0; i <= n; i++ )
biao[i] = NULL;
}
void add( int from,int to,int w ){
Arc *p1 = A[countt++].ass( from,to,w ,biao[from]);
Arc *p2 = A[countt++].ass( to,from,0,biao[ to] );
p1->anti = p2; p2->anti = p1;
}
int MaxFlowDinic( int s, int t ){
S = s;T = t;
int total = 0;
while( bfs() )
total += dinic( S,INF );
return total;
}
int MaxFlowSap( int s, int t){
S = s;T = t;
int i,now,total,md;
Arc *p,*locate,*ge[ Vsize ],*di[ Vsize ],*path[ Vsize ];
int dist[ Vsize ], cd[ Vsize ];
int his[ Vsize ], pre[ Vsize ];;
bool flag;
memset( dist,0, sizeof(dist) );
memset( cd, 0, sizeof(cd) );
cd[0] = N;
for( i = 0; i <= N ; i++ )
di[i] = ge[i] = biao[i];
for( total = 0, now = INF,i = S; dist[i] < N; ){
his[i] = now;
for( flag = false,p=di[i]; p!=NULL; p= p->next){
if( p->w > 0 && dist[i] ==dist[p->to] + 1 ){
now = min( now,p->w );
pre[ p->to ] = i;
path[ p->to ] = p;
di[i] = p;
i = p->to;
if( i == T ){
for( total += now; i != S; i = pre[i] )
path[i]->w -= now, path[i]->anti->w += now;
now = INF;
}
flag = true;
break;
}
}
if( !flag ){
for( md = N-1,p=ge[i];p!= NULL;p=p->next )
if( p->w > 0 && dist[p->to] < md )
md = dist[p->to],locate = p;
di[i] = locate;
if( !(--cd[ dist[i] ] ) ) break;
cd[ dist[i] = md+1 ] ++;
if( i != S )
i = pre[i],now = his[i];
}
}
return total;
}
vector<int> check(int L ){
int flag[Vsize];
memset( flag,0,sizeof(flag) );
dfs1( S, flag );
dfs2( T, flag );
vector<int> v;
for(int i = 0; i < 2*L; i+=2 )
if( flag[A[i].from]==1 && flag[A[i].to] ==2 )
v.push_back(i/2+1);
return v;
}
void dfs1( int u,int *flag ){
flag[u] = 1;
for( Arc*p=biao[u];p!=NULL;p=p->next )
if( !flag[p->to] && p->w )
dfs1( p->to, flag );
}
void dfs2( int u, int *flag ){
flag[u]= 2;
for(Arc*p=biao[u];p!=NULL;p=p->next )
if( !flag[p->to] && p->anti->w )
dfs2( p->to, flag);
}
};
Network< 150 , 2300 > Net;
int main(void){
int N,M,L,S,T;
int i,j,k,from,to,w;
while( scanf("%d%d%d",&N,&M,&L) && N ){
Net.init( N+M+2 );
S = N+M+1; T = 0;
for( i = 1; i <= L; i++ ){
scanf("%d%d%d",&from,&to,&w);
Net.add( from,to,w );
}
for( i = 1; i <=N; i++)
Net.add( S, i, INF );
Net.MaxFlowSap(S,T);
vector<int> v = Net.check(L);
sort( v.begin(), v.end() );
for( i = 0; i < v.size(); i++ ){
if( i ) printf(" ");
printf("%d",v[i]);
}
printf("\n");
}
return 0;
}