As you know, the Expo garden is made up of many museums of different countries. In the Expo garden, there are a lot of bi-directional roads connecting those museums, and all museums are directly or indirectly connected with others. Each road has a tourist capacity which means the maximum number of people who can pass the road per second.
Because Nubulsa is not a rich country and the ticket checking machine is very expensive, the government decides that there must be only one entrance and one exit. The president has already chosen a museum as the entrance of the whole Expo garden, and it’s the Expo chief directory Wuzula’s job to choose a museum as the exit.
Wuzula has been to the Shanghai Expo, and he was frightened by the tremendous “people mountain people sea” there. He wants to control the number of people in his Expo garden. So Wuzula wants to find a suitable museum as the exit so that the “max tourists flow” of the Expo garden is the minimum. If the “max tourist flow” is W, it means that when the Expo garden comes to “stable status”, the number of tourists who enter the entrance per second is at most W. When the Expo garden is in “stable status”, it means that the number of people in the Expo garden remains unchanged.
Because there are only some posters in every museum, so Wuzula assume that all tourists just keep walking and even when they come to a museum, they just walk through, never stay.
For each test case:
The first line contains three integers N, M and S, representing the number of the museums, the number of roads and the No. of the museum which is chosen as the entrance (all museums are numbered from 1 to N). For example, 5 5 1 means that there are 5 museums and 5 roads connecting them, and the No. 1 museum is the entrance.
The next M lines describe the roads. Each line contains three integers X, Y and K, representing the road connects museum X with museum Y directly and its tourist capacity is K.
Please note:
1<N<=300, 0<M<=50000, 0<S,X,Y<=N, 0<K<=1000000
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL; const int MAXN = ; LL mat[MAXN][MAXN];
LL weight[MAXN];
bool del[MAXN], vis[MAXN];;
int n, m, st; void init() {
memset(mat, , sizeof(mat));
memset(del, , sizeof(del));
} LL StoerWagner(int &s, int &t, int cnt) {
memset(weight, , sizeof(weight));
memset(vis, , sizeof(vis));
for(int i = ; i <= n; ++i)
if(!del[i]) {t = i; break; }
while(--cnt) {
vis[s = t] = true;
for(int i = ; i <= n; ++i) if(!del[i] && !vis[i]) {
weight[i] += mat[s][i];
}
t = ;
for(int i = ; i <= n; ++i) if(!del[i] && !vis[i]) {
if(weight[i] >= weight[t]) t = i;
}
}
return weight[t];
} void merge(int s, int t) {
for(int i = ; i <= n; ++i) {
mat[s][i] += mat[t][i];
mat[i][s] += mat[i][t];
}
del[t] = true;
} LL solve() {
LL ret = -;
int s, t;
for(int i = n; i > ; --i) {
if(ret == -) ret = StoerWagner(s, t, i);
else ret = min(ret, StoerWagner(s, t, i));
merge(s, t);
}
return ret;
} int main() {
while(scanf("%d%d%d", &n, &m, &st) != EOF) {
if(n == && m == && st == ) break;
init();
while(m--) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
mat[x][y] += z;
mat[y][x] += z;
}
cout<<solve()<<endl;
}
}