POJ3228 Gold Transportation < MST >

Problem

Gold Transportation

Time Limit: $2000MS$
Memory Limit: $65536K$

Description

Recently, a number of gold mines have been discovered in Zorroming State. To protect this treasure, we must transport this gold to the storehouses as quickly as possible. Suppose that the Zorroming State consists of N towns and there are M bidirectional roads among these towns. The gold mines are only discovered in parts of the towns, while the storehouses are also owned by parts of the towns. The storage of the gold mine and storehouse for each town is finite. The truck drivers in the Zorroming State are famous for their bad temper that they would not like to drive all the time and they need a bar and an inn available in the trip for a good rest. Therefore, your task is to minimize the maximum adjacent distance among all the possible transport routes on the condition that all the gold is safely transported to the storehouses.

Input

The input contains several test cases. For each case, the first line is integer $N$$(1\le N\le 200)$. The second line is $N$ integers associated with the storage of the gold mine in every towns .The third line is also $N$ integers associated with the storage of the storehouses in every towns .Next is integer $M$$(0\le M\le \frac{(n-1)\times n}{2})$.Then M lines follow. Each line is three integers $x$, $y$ and $d$$(1\le x,y\le N, 0<d\le 10^4)$, means that there is a road between $x$ and $y$ for distance of $d$. $N=0$ means end of the input.

Output

For each case, output the minimum of the maximum adjacent distance on the condition that all the gold has been transported to the storehouses or “No Solution”.

Sample Input

4
3 2 0 0
0 0 3 3
6
1 2 4
1 3 10
1 4 12
2 3 6
2 4 8
3 4 5
0

Sample Output

6

Translation

有$n$个村庄，每个村庄有一个黄金矿和一个仓库，求一棵生成树森林，使得每棵生成树上的黄金矿都可被这棵生成树上的仓库存下，并且森林中最大边权最小。

标签：MST

Solution

一个简单的$\mathrm{MST}$变形。
用$\mathrm{Kruskal}$从大到小贪心选边，每加一条边就$O(n)$判断森林中是否所有点所在的树都可以“自给自足”。总时间复杂度$O(mn)$，即$O(n^3)$。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MAX_N 200
#define MAX_M 20000
using namespace std;
int n, m, f[MAX_N+5], s[MAX_N+5];
struct node {int u, v, c;} E[MAX_M+5];
bool cmp(const node &a, const node &b) {return a.c < b.c;}
int getf(int x) {if (f[x] == x)    return x;	int tmp = getf(f[x]);	s[tmp] += s[x], s[x] = 0;	return f[x] = tmp;}
bool chk() {for (int i = 1; i <= n; i++)    if (f[i] == i && s[i] < 0)	return false;	return true;}
int main() {
    while (scanf("%d", &n) && n) {
        for (int i = 1; i <= n; i++)	f[i] = i, s[i] = 0;
        for (int i = 1, x; i <= n; i++)	scanf("%d", &x), s[i] -= x;
        for (int i = 1, x; i <= n; i++)	scanf("%d", &x), s[i] += x;
        scanf("%d", &m);
        for (int i = 0; i < m; i++)	scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].c);
        sort(E, E+m, cmp);	bool flag = false;
        for (int i = 0; i < m; i++) {
            int u = getf(E[i].u), v = getf(E[i].v);
            if (u != v)	f[u] = v, s[v] += s[u], s[u] = 0;
            if (chk()) {flag = true, printf("%d\n", E[i].c);	break;}
        }
        if (!flag)	printf("No Solution\n");
    }
    return 0;
}