2014-07-23

UVa 11603 - Its all about the Bandwidth

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

My appartment has n computers. My friend’s appartment also has n computers. In each appartment, some pairs of computers are connected to each other with AcidNet cables (ignoring the routers). Each connection has a certain bandwidth (in bytes per second). My friend always brags about the speed of his computer network. He always shows me his n-by-n table that lists the bandwidths between each pair of computers. My network is slower, and I want to rebuild it. So I want to know how I should connect my computers in order to have the same n-by-n bandwidth table.

Since I don’t want to buy too many AcidNet cables, you’ll need to find a solution with the minimum number of connections. You may use AcidNet cables of any integer bandwidth - they all have the same price at my local Imaginary Hardware Store.
Problem, in short

Given a graph, you can compute the all-pairs maximum flow table, right? Now do the opposite: given an n-by-n symmetric table, find a graph with fewest edges that has the given table of all-pairs maximum flows.

Input

The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 200), followed by n lines with n integers each, giving the table T.

T[u][u] will always be 0.
T[u][v] will always be positive and equal to T[v][u].
T[i][j] ≤ 10000

T[u][v] is the largest possible speed (in bytes per second) for sending information from computer u to computer v, assuming there is no other traffic on the network.

Output

For each test case, output one line containing “Case #x:” followed by m - the number of cables I have to buy. The next m lines will each contain 3 integers u, v and w meaning that I need to connect computer u to computer v using an AcidNet cable of bandwidth w. Computers are numbered starting at 0.

If there is no solution, print Impossible.

Sample Input

Output for Sample Input

Case #1: 1
0 1 10
Case #2: 2
0 1 1
1 2 2
Case #3: 0
Case #4: Impossible

Solution

題目描述：

朋友給一個他的端點之間的頻寬關係，這些頻寬關係是對稱的，現在要用最少條的邊做出跟朋友一樣的網路頻寬關係，請問是否有可能，如果可能的話，請輸出需要擺設的邊。

題目解法：

假設有 n 個節點，要用最少條構成，相當於給定一個 n - 1 條邊的 tree，對於一個 tree 而言，彼此之間的流量關係符合不等式

$cap(i, j) \le min(cap(i, k), cap(k, j))$

也就是說，如果存在更好的流量方式，則會在關係圖中表示出來。在判斷是否可能即檢查所有情況是否符合不等式。最後根據這條不等式，相當於最小生成樹中 s - t 集合中的關係。

#include <stdio.h> 
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    E(int a = 0, int b = 0, int c = 0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return  v > a.v;
    }
};
E D[65536];
int p[256], rank[256];
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)	return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int main() {
    int testcase, cases = 0, n, g[256][256];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                scanf("%d", &g[i][j]);
        printf("Case #%d: ", ++cases);
        int eflag = 0;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++)
                for(int k = j+1; k < n; k++)
                    if(min(g[i][j], g[j][k]) > g[i][k] ||
                        min(g[i][k], g[j][k]) > g[i][j] ||
                        min(g[i][j], g[i][k]) > g[j][k])
                        eflag = 1, i = j = k = n;
        if(eflag)  {
            puts("Impossible");
            continue;
        }
        printf("%d\n", n - 1);
        int m = 0;
        for(int i = 0; i < n; i++)
            p[i] = i, rank[i] = 1;
        for(int i = 0; i < n; i++)
            for(int j = i+1; j < n; j++)
                D[m++] = E(i, j, g[i][j]);
        sort(D, D+m);
        for(int i = 0; i < m; i++) {
            if(joint(D[i].x, D[i].y)) {
                printf("%d %d %d\n", D[i].x, D[i].y, D[i].v);
            }
        }
    }
    return 0;
}

Morris' Blog