[UVA][MaxFlow/MinCut] 10480 - Sabotage
Sabotage
| Sabotage |
The regime of a small but wealthy dictatorship has been abruptly overthrown by an unexpectedrebellion. Because of the enormous disturbances this is causing in world economy, an imperialistmilitary super power has decided to invade the country and reinstall the old regime.
For this operation to be successful, communication between the capital and the largest city mustbe completely cut. This is a difficult task, since all cities in the country are connected by acomputer network using the Internet Protocol, which allows messages to take any path throughthe network. Because of this, the network must be completely split in two parts, with the capitalin one part and the largest city in the other, and with no connections between the parts.
There are large differences in the costs of sabotaging different connections, since some are muchmore easy to get to than others.
Write a program that, given a network specification and the costs of sabotaging each connection,determines which connections to cut in order to separate the capital and the largest city to thelowest possible cost.
Input
Input file contains several sets of input. The description of each set is given below.
The first line of each set has two integers, separated by a space: First one the number of cities, nin the network, which is at most 50. The second one is the total number of connections, m, atmost 500.
The following m lines specify the connections. Each line has three parts separated by spaces:The first two are the cities tied together by that connection (numbers in the range 1 - n). Thenfollows the cost of cutting the connection (an integer in the range 1 to 40000000). Each pair ofcites can appear at most once in this list.
Input is terminated by a case where values of n and m are zero. This case should not beprocessed. For every input set the capital is city number 1, and the largest city is number 2.
Output
For each set of input you should produce several lines of output. The description of output foreach set of input is given below:
The output for each set should be the pairs of cities (i.e. numbers) between which the connectionshould be cut (in any order), each pair on one line with the numbers separated by a space. Ifthere is more than one solution, any one of them will do.
Print a blank line after the output for each set of input.
Sample Input
5 81 4 301 3 705 3 204 3 54 5 155 2 103 2 252 4 505 81 4 301 3 705 3 204 3 54 5 155 2 103 2 252 4 500 0
Sample Output
4 13 43 53 24 13 43 53 2
Problem setter: Jesper Larsson, Lund University, Sweden
參照 DJWS 打出, 最大流的部分使用 SPFA 去找增廣路徑, 輸出的部分比較麻煩
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
bool diff[100];
int C[100][100], F[100][100];
vector<int> map[100];
int maxFlow(int, int, int);
void DFS(int node) {
diff[node] = true;
for(vector<int>::iterator i = map[node].begin(); i != map[node].end(); i++) {
if(diff[*i] == false && F[node][*i] != 0)
DFS(*i);
}
}
int minCut(int st, int ed, int n) {
maxFlow(st, ed, n);
memset(diff, 0, sizeof(diff));
DFS(st);
for(int i = 1; i <= n; i++) {
if(diff[i] == true) {
for(vector<int>::iterator j = map[i].begin(); j != map[i].end(); j++) {
if(diff[*j] == false) {
printf("%d %d\n", i, *j);
}
}
}
}
}
int maxFlow(int st, int ed, int n) {
int v[100], pre[100];
int maxflow = 0, i, tn, tc;
bool used[100];
memcpy(F, C, sizeof(F));
while(true) {
memset(v, 0, sizeof(v));
memset(used, 0, sizeof(used));
v[st] = 0xfffffff;
queue<int> Q;
Q.push(st);
pre[st] = st;
while(!Q.empty()) {
tn = Q.front();
Q.pop();
used[tn] = false;
for(vector<int>::iterator i = map[tn].begin(); i != map[tn].end(); i++) {
tc = v[tn] < F[tn][*i] ? v[tn] : F[tn][*i];
if(tc <= v[ed])
continue;
if(tc > v[*i]) {
v[*i] = tc, pre[*i] = tn;
if(used[*i] == false) {
Q.push(*i);
used[*i] = true;
}
}
}
}
if(v[ed] == 0)
break;
maxflow += v[ed];
for(i = ed; i != st; i = pre[i]) {
F[pre[i]][i] -= v[ed];
F[i][pre[i]] += v[ed];
}
}
return maxflow;
}
int main() {
int n, m, x, y, c;
int i, j;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0 && m == 0)
break;
for(i = 0; i <= n; i++)
map[i].clear();
memset(C, 0, sizeof(C));
while(m--) {
scanf("%d %d %d", &x, &y, &c);
C[x][y] += c;
C[y][x] += c;
map[x].push_back(y);
map[y].push_back(x);
}
minCut(1, 2, n);
puts("");
}
return 0;
}