題意：給定多個(gè)城市的網(wǎng)絡(luò)，每個(gè)城市之間的通信有花費(fèi)，要求使得首都和最大城市之間的通信斷掉的最小花費(fèi)。要求輸出砸掉的邊。
解法：給出了源點(diǎn)和匯點(diǎn)，果斷最小割。也許是許久沒有寫圖論的題了，最小割輸出出錯(cuò)，忘記了可能有多個(gè)最小割存在。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 55
#define INF 1 << 28
int cap[N][N], dis[N], pre[N], cnt[N];
bool g[N][N], mk[N];
int ISAP(int src, int sink, int n)
{
int maxflow = 0, flow, u = src, v, d;
for(int i = 0; i < n; i++)
dis[i] = cnt[i] = 0;
pre[src] = src;
cnt[src] = n;
while(dis[src] < n)
{
if(u == sink)
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
if(cap[pre[i]][i] < flow)
flow = cap[pre[i]][i];
maxflow += flow;
u = src;
for(int i = sink; i != src; i = pre[i])
{
cap[pre[i]][i] -= flow;
cap[i][pre[i]] += flow;
}
}
for(d = n, v = 0; v < n; v++)
{
if(!cap[u][v]) continue;
d = d < dis[v] ? d : dis[v];
if(dis[v] + 1 == dis[u]) break;
}
if(v < n) pre[v] = u, u = v;
else
{
if(!(--cnt[dis[u]])) break;
++cnt[dis[u] = d + 1];
u = pre[u];
}
}
return maxflow;
}
void Dfs(int u, int n)
{
mk[u] = 1;
for(int i = 0; i < n; i++)
{
if(!mk[i] && cap[u][i]) Dfs(i, n);
}
}
int main()
{
int n, m;
while(scanf("%d %d", &n, &m), n + m)
{
memset(cap, 0, sizeof(cap));
memset(g, 0, sizeof(g));
memset(mk, 0, sizeof(mk));
for(int i = 0; i < m; i++)
{
int a , b, c;
scanf("%d %d %d", &a, &b, &c);
a--, b--;
cap[a][b] = cap[b][a] = c;
g[a][b] = g[b][a] = 1;
}
int ans = ISAP(0, 1, n);
Dfs(0, n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(g[i][j] && !cap[i][j] && mk[i] != mk[j])
printf("%d %d\n", i + 1, j + 1);
}
}
printf("\n");
}
return 0;
}