题意：
一些城市通过网络连接，首都的编号是1，最大的城市的编号是2，要破坏一些边使得首都到最大的城市的连接中断，破坏不同的边有不同的花费。求最小的花费？
解题思路：
使s-t的路径断开，就是增广后的残余网络，即为s-t的最小割，因此用增光路求最大流即可。答案要求输出该切掉那些边，这些即使残余网络中使s-t路径断开的边，从s开始用BFS搜索一次标记可达的点，再来扫描参与网络中的边，若这条边的端点分别为标记过和未标记过的点，输出这条边即可，注意边要去重。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
#include<queue>
#include<vector>
#include<list>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define INF 0x3f3f3f3f
#define MAX_V 805
struct edge{int to,cap,rev;};
vector<edge> G[MAX_V];
int V;
int prevv[MAX_V],preve[MAX_V];
int iter[MAX_V],num[MAX_V],level[MAX_V];
void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,0,G[from].size()-1});
}
void bfs(int s,int t)
{
memset(level,-1,sizeof level);
memset(num,0,sizeof num);
queue<int> que;
que.push(t);
level[t]=0;
num[0]=1;
while(!que.empty())
{
int u=que.front();que.pop();
for(int i=0;i<G[u].size();i++)
{
edge e=G[u][i];
edge rev=G[e.to][e.rev];
if(rev.cap>0&&level[e.to]<0)
{
level[e.to]=level[u]+1;
num[level[e.to]]++;
que.push(u);
}
}
}
}
int augment(int s,int t)
{
int f=INF;
for(int v=t;v!=s;v=prevv[v])
{
edge e=G[prevv[v]][preve[v]];
f=min(f,e.cap);
}
for(int v=t;v!=s;v=prevv[v])
{
edge &e=G[prevv[v]][preve[v]];
e.cap-=f;
G[e.to][e.rev].cap+=f;
}
return f;
}
int max_flow(int s,int t)
{
int flow=0;
int u=s;
memset(iter,0,sizeof iter);
bfs(s,t);
while(level[u]<V)
{
if(u==t)
{
int d=augment(s,t);
flow+=d;
u=s;
}
int rebuild=0;
for(int &i=iter[u];i<G[u].size();i++)
{
edge e=G[u][i];
if(e.cap>0&&level[u]==level[e.to]+1)
{
prevv[e.to]=u;
preve[e.to]=i;
u=e.to;
rebuild=1;
break;
}
}
if(!rebuild)
{
int d=V-1;
for(int i=0;i<G[u].size();i++)
{
edge e=G[u][i];
if(e.cap>0) d=min(d,level[e.to]);
}
iter[u]=0;
num[level[u]]--;
if(num[level[u]]==0) break;
level[u]=d+1;
num[level[u]]++;
if(u!=s) u=prevv[u];
}
}
return flow;
}
int n,m;
int vis[MAX_V];
map<pair<int,int>,bool> mp;
int main()
{
while(~scanf("%d%d",&n,&m)&&n+m)
{
memset(vis,0,sizeof vis);
for(int i=0;i<MAX_V;i++) G[i].clear();
mp.clear();
int s=1,t=2;
V=n;
for(int i=1;i<=m;i++)
{
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
add_edge(u,v,c);
add_edge(v,u,c);
}
int f=max_flow(s,t);
queue<int> que;
que.push(s);
vis[s]=1;
while(!que.empty())
{
int u=que.front();que.pop();
for(int i=0;i<G[u].size();i++)
{
edge e=G[u][i];
if(e.cap>0&&!vis[e.to])
{
vis[e.to]=1;
que.push(e.to);
}
}
}
for(int i=1;i<=n;i++)
if(vis[i])
{
for(int j=0;j<G[i].size();j++)
{
edge e=G[i][j];
if(!vis[e.to]&&!mp[pair<int,int>(i,e.to)]) printf("%d %d\n",i,e.to),mp[pair<int,int>(i,e.to)]=1;
}
}
puts("");
}
return 0;
}