Problem D

Re-connecting Computer Sites

Consider the problem of selecting a set T of high-speed lines for connecting N computer sites, from a universe of M high-speed lines each connecting a pair of computer sites. Each high-speed line has a given monthly cost, and the objective is to minimize the total cost of connecting the N computer sites, where the total cost is the sum of the cost of each line included in set T. Consider further that this problem has been solved earlier for the set of N computer sites and M high-speed lines, but that a few K new high-speed lines have recently become available.

Your objective is to compute the new set T' that may yield a cost lower than the original set T, due to the additional K new high-speed lines and when M+K high-speed lines are available.

Input

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.

The input is organized as follows:

• A line containing the number N of computer sites, with 1 <= N <= 1000000, and where each computer site is referred by a number i, 1 <= i <= N.
• The set T of previously chosen high-speed lines, consisting of N-1 lines, each describing a high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number K of new additional lines, 1 <= K <= 10.
• K lines, each describing a new high-speed line, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.
• A line containing the number M of originally available high-speed lines, with N-1 <= M <= N (N-1) / 2.
• M lines, each describing one of the originally available high-speed lines, and containing the numbers of the two computer sites the line connects and the monthly cost of using this line. All costs are integers.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output file must have one line containing the original cost of connecting the N computer sites with M high-speed lines and another line containing the new cost of connecting the N computer sites with M+K high-speed lines. If the new cost equals the original cost, the same value is written twice.

Sample Input

5
1 2 5
1 3 5
1 4 5
1 5 5
1
2 3 2
6
1 2 5
1 3 5
1 4 5
1 5 5
3 4 8
4 5 8

Sample Output

20
17

---

作法 : 最小生成樹

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct {
    int x, y;
    double v;
}Link;
struct {
    double x, y;
}P[100];
Link D[10001];
int cmp(const void *i, const void *j) {
    Link *a, *b;
    a = (Link *)i, b = (Link *)j;
    return a->v - b->v < 0 ? -1 : 1;
}
int Parent[100], Rank[100];
void MakeInit(int n) {
    int i;
    for(i = 0; i < n; i++)
        Parent[i] = i, Rank[i] = 1;
}
int FindParent(int x) {
    if(Parent[x] != x)
        Parent[x] = FindParent(Parent[x]);
    return Parent[x];
}
void PLink(int x, int y) {
    if(Rank[x] > Rank[y]) {
        Rank[x] += Rank[y];
        Parent[y] = x;
    } else {
        Rank[y] += Rank[x];
        Parent[x] = y;
    }
}
int Union(int x, int y) {
    x = FindParent(x), y = FindParent(y);
    if(x != y) {
        PLink(x, y);
        return 1;
    }
    return 0;
}
int main() {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        int m = 0, i, j;
        for(i = 0; i < n; i++)
            scanf("%lf %lf", &P[i].x, &P[i].y);
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                if(i != j) {
                    D[m].x = i, D[m].y = j;
                    D[m].v = sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x)+
                        (P[i].y-P[j].y)*(P[i].y-P[j].y));
                    m++;
                }
            }
        }
        qsort(D, m, sizeof(Link), cmp);
        double sum = 0;
        MakeInit(n);
        for(i = 0; i < m; i++) {
            sum += Union(D[i].x, D[i].y)*D[i].v;
        }
        printf("%.2lf\n", sum);
        if(T)    puts("");
    }
    return 0;
}