传送门：Sabotage
题意：给定多个城市的网络，每个城市之间的通信有花费，要求使得首都和最大城市之间的通信断掉的最小花费。要求输出任意一组砸掉的边。
分析：跑一遍最大流dinic后，根据最小割定理，整部图被分为S,T两部分，从源点出发dfs得到S集的点，剩下的为T集的点，然后输出左右两边各一个连着的点就是割边。
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <vector>
#include <set>
#include <map>
#define LL long long
#define mod 100000000
#define inf 0x3f3f3f3f
#define eps 1e-6
#define N 2010
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PII pair<int,int>
using namespace std;
inline int read()
{
char ch=getchar();int x=,f=;
while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}
while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,sum,vs,vt,tot,NV;
int pre[N],cur[N],h[N],q[N];
struct edge
{
int u,v,w,next;
edge() {}
edge(int u,int v,int w,int next):u(u),v(v),w(w),next(next) {}
} e[N<<];
void addedge(int u,int v,int w)
{
e[tot]=edge(u,v,w,pre[u]);
pre[u]=tot++;
e[tot]=edge(v,u,,pre[v]);
pre[v]=tot++;
}
void init()
{
memset(pre,-,sizeof(pre));
tot=;
} /*******************dinic************************/
int bfs()
{
int head=,tail=;
memset(h,-,sizeof(h));
q[]=vs;h[vs]=;
while(head!=tail)
{
int u=q[head++];
for(int i=pre[u];~i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(w&&h[v]==-)
{
h[v]=h[u]+;
q[tail++]=v;
}
}
}
return h[vt]!=-;
} int dfs(int u,int flow)
{
if(u==vt)return flow;
int used=;
for(int i=cur[u];~i;i=e[i].next)
{
int v=e[i].v,w=e[i].w;
if(h[v]==h[u]+)
{
w=dfs(v,min(flow-used,w));
e[i].w-=w;e[i^].w+=w;
if(e[i].w)cur[u]=i;
used+=w;
if(used==flow)return flow;
}
}
if(!used)h[u]=-;
return used;
}
int dinic()
{
int res=;
while(bfs())
{
for(int i=;i<=n;i++)cur[i]=pre[i];
res+=dfs(vs,inf);
}
return res;
}
/********************dinic***********************/
int u,v,w;
int vis[],mark[][];
void DFS(int u)
{
vis[u]=;
for(int i=pre[u];~i;i=e[i].next)
{
int v=e[i].v;
if(e[i].w&&!vis[v])DFS(v);
}
}
void build()
{
vs=;vt=;
for(int i=;i<=m;i++)
{
u=read();v=read();w=read();
addedge(u,v,w);
addedge(v,u,w);
}
dinic();
memset(vis,,sizeof(vis));
memset(mark,,sizeof(mark));
DFS();
for(int u=;u<=n;u++)
for(int i=pre[u];~i;i=e[i].next)
{
int a=e[i].u,b=e[i].v;
if(!e[i].w&&vis[a]!=vis[b]&&!mark[a][b])
printf("%d %d\n",a,b),mark[a][b]=;
}
puts("");
}
int main()
{
while(scanf("%d%d",&n,&m)>)
{
if(n+m==)break;
init();
build();
}
}