题意

题目描述：
你知道多米诺骨牌除了用来玩多米诺骨牌游戏外，还有其他用途吗？多米诺骨牌游戏：取一 些多米诺骨牌，竖着排成连续的一行，两张骨牌之间只有很短的空隙。如果排列得很好，当你推 倒第 1张骨牌，会使其他骨牌连续地倒下（这就是短语“多米诺效应”的由来）。 然而当骨牌数量很少时，这种玩法就没多大意思了，所以一些人在 80 年代早期开创了另一个 极端的多米诺骨牌游戏：用上百万张不同颜色、不同材料的骨牌拼成一幅复杂的图案。他们开创 了一种流行的艺术。在这种骨牌游戏中，通常有多行骨牌同时倒下。 你的任务是编写程序，给定这样的多米诺骨牌游戏，计算后倒下的是哪一张骨牌、在什么 时间倒下。这些多米诺骨牌游戏包含一些“关键牌”，他们之间由一行普通骨牌连接。当一张关键 牌倒下时，连接这张关键牌的所有行都开始倒下。当倒下的行到达其他还没倒下的关键骨牌时， 则这些关键骨牌也开始倒下，同样也使得连接到它的所有行开始倒下。每一行骨牌可以从两个端 点中的任何一张关键牌开始倒下，甚至两个端点的关键牌都可以分别倒下，在这种情形下，该行 后倒下的骨牌为中间的某张骨牌。假定骨牌倒下的速度一致。

输入描述：
输入文件包含多个测试数据，每个测试数据描述了一个多米诺骨牌游戏。每个测试数据的第 1行为两个整数：n和m，n表示关键牌的数目，1≤n<500；m表示这 n张牌之间用 m行普通骨 牌连接。n 张关键牌的编号为 1～n。每两张关键牌之间至多有一行普通牌，并且多米诺骨牌图案 是连通的，也就是说从一张骨牌可以通过一系列的行连接到其他每张骨牌。 接下来有 m行，每行为 3个整数：a、b和t，表示第 a张关键牌和第 b张关键牌之间有一行 普通牌连接，这一行从一端倒向另一端需要 t 秒。每个多米诺骨牌游戏都是从推倒第 1 张关键牌 开始的。 输入文件后一行为 n = m = 0，表示输入结束。

输出描述：
对输入文件中的每个测试数据，首先输出一行”System /#k”，其中 k为测试数据的序号；然后 再输出一行，首先是后一块骨牌倒下的时间，精确到小数点后一位有效数字，然后是后倒下 骨牌的位置，这张后倒下的骨牌要么是关键牌，要么是两张关键牌之间的某张普通牌。输出格 式如样例输出所示。如果存在多个解，则输出任意一个。每个测试数据的输出之后输出一个空行。

先用最短路算出每个关键牌i的倒下时间d[i] 然后两个关键牌i,j间最后倒下的时间应该为 (d[i]+d[j]+mat[i][j])/2 取时间最大的就是答案了 注意当i==j时说明最后倒下的是关键节点 此时输出有所不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 505;
int d[N], v[N], mat[N][N], n, m;

void dijkstra()
{
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0;
    for(int i =  1; i <= n; ++i)
    {
        int cur = 0;
        for(int j = 1; j <= n; ++j)
            if(!v[j] && d[j] < d[cur]) cur = j;
        v[cur] = 1;
        for(int j = 1; j <= n; ++j)
            if(d[j] > d[cur] + mat[cur][j])
                d[j] = d[cur] + mat[cur][j];
    }
}

int main()
{
    int pi, pj, ans, a, b, c, cas = 0;
    while(scanf("%d%d", &n, &m), n)
    {
        memset(mat, 0x3f, sizeof(mat));
        for(int i = 1; i <= n; ++i) mat[i][i] = 0;
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            mat[a][b] = mat[b][a] = c;
        }
        dijkstra();

        int ans = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = i; j <= n; ++j)
            {
                if(mat[i][j] >= d[0]) continue;
                if(d[i] + d[j] + mat[i][j] > ans || (i == j && 2 * d[i] >= ans))
                {
                    ans = d[i] + d[j] + mat[i][j];
                    pi = i, pj = j;
                }
            }
        }

        double t = ans / 2.0;
        printf("System #%d\nThe last domino falls after %.1f seconds, ", ++cas, t);
        if(pi == pj)  printf("at key domino %d.\n\n", pi);
        else   printf("between key dominoes %d and %d.\n\n", pi, pj);
    }
    return 0;
}

Domino Effect

Description
Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase domino effect'' comes from). While this is somewhat pointless with only a few dominoes, some people went to the opposite extreme in the early Eighties. Using millions of dominoes of different colors and materials to fill whole halls with elaborate patterns of falling dominoes, they created (short-lived) pieces of art. In these constructions, usually not only one but several rows of dominoes were falling at the same time. As you can imagine, timing is an essential factor here. It is now your task to write a program that, given such a system of rows formed by dominoes, computes when and where the last domino falls. The system consists of several key dominoes’’ connected by rows of simple dominoes. When a key domino falls, all rows connected to the domino will also start falling (except for the ones that have already fallen). When the falling rows reach other key dominoes that have not fallen yet, these other key dominoes will fall as well and set off the rows connected to them. Domino rows may start collapsing at either end. It is even possible that a row is collapsing on both ends, in which case the last domino falling in that row is somewhere between its key dominoes. You can assume that rows fall at a uniform rate.

Input

The input file contains descriptions of several domino systems. The first line of each description contains two integers: the number n of key dominoes (1 <= n < 500) and the number m of rows between them. The key dominoes are numbered from 1 to n. There is at most one row between any pair of key dominoes and the domino graph is connected, i.e. there is at least one way to get from a domino to any other domino by following a series of domino rows.
The following m lines each contain three integers a, b, and l, stating that there is a row between key dominoes a and b that takes l seconds to fall down from end to end.
Each system is started by tipping over key domino number 1.
The file ends with an empty system (with n = m = 0), which should not be processed.

Output

For each case output a line stating the number of the case (‘System /#1’, ‘System /#2’, etc.). Then output a line containing the time when the last domino falls, exact to one digit to the right of the decimal point, and the location of the last domino falling, which is either at a key domino or between two key dominoes(in this case, output the two numbers in ascending order). Adhere to the format shown in the output sample. The test data will ensure there is only one solution. Output a blank line after each system.

Sample Input

2 1 1 2 27 3 3 1 2 5 1 3 5 2 3 5 0 0

Sample Output

System /#1 The last domino falls after 27.0 seconds, at key domino 2. System /#2 The last domino falls after 7.5 seconds, between key dominoes 2 and 3.

题意 中文

入门最小生成树 prim大法好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105;
int cost[N], mat[N][N], n, m, ans;

void prim()
{
    memset(cost, 0x3f, sizeof(cost));
    cost[1] = -1;
    int cur = 1, next = 0;
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(cost[j] == -1) continue;
            if(cost[j] > mat[cur][j]) cost[j] = mat[cur][j];
            if(cost[j] < cost[next]) next = j;
        }
        ans += cost[next], cost[cur = next] = -1, next = 0;
    }
}

int main()
{
    int a, b, c;
    while(scanf("%d%d", &m, &n), m)
    {
        memset(mat, 0x3f, sizeof(mat));
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(c < mat[a][b]) mat[a][b] = mat[b][a] = c;
        }
        ans = 0;
        prim();
        if(ans >= cost[0]) printf("?\n");
        else printf("%d\n", ans);
    }
    return 0;
}

畅通工程

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N
行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
Sample Input

3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
Sample Output

3 ?

题意 中文

最基础的最短路 注意边可能多次给出 取最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 205, M = 1005;
int mat[N][N], v[N], d[N], n, m, s, t;

void dijkstra()
{
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    for(int i = d[s] = 0; i < n; ++i)
    {
        int cur=n;   //d[n]是INF,cur为当前未标记且到s距离最小的点
        for(int j = 0; j < n; ++j)
            if(!v[j] && d[j] < d[cur]) cur = j;

        v[cur] = 1; if(cur == t) return;
        for(int j = 0; j < n; ++j)
        {
            if(d[j] > d[cur] + mat[cur][j])
                d[j] = d[cur] + mat[cur][j];
        }
    }
}

int main()
{
    int a, b, x;
    while(~scanf("%d%d", &n, &m))
    {
        memset(mat, 0x3f, sizeof(mat));
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &a, &b, &x);
            if(mat[a][b]>x)   //注意路径可能有多条
                mat[a][b] = mat[b][a] = x;
        }

        scanf("%d %d", &s, &t);
        dijkstra();
        if(d[t] >= d[n]) printf("-1\n");
        else printf("%d\n", d[t]);
    }
    return 0;
}

畅通工程续

Problem Description

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input

本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output

对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input

3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
Sample Output

2 -1

题意 有n辆卡车 每辆卡车用7个字符表示 输入n 再输入n行字符 第i行与第j行的两个字符串有多少个对应位置的字符不同 i与j之间的距离就是几 求连接所有卡车的最短长度 题目不是这个意思 这样理解就行了

prim啦啦啦啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2005;
int cost[N], dis[N][N], n, ans;

void prim()
{
    memset(cost, 0x3f, sizeof(cost));
    cost[1] = -1;
    int cur = 1, next = 0;
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(cost[j] == -1 || cur == j) continue;
            if(dis[cur][j] < cost[j]) cost[j] = dis[cur][j];
            if(cost[j] < cost[next]) next = j;
        }
        cur = next, next = 0, ans += cost[cur], cost[cur] = -1;
    }
}

int main()
{
    char s[N][10];
    while(scanf("%d", &n), n)
    {
        memset(dis, 0, sizeof(dis));
        for(int i = 1; i <= n; ++i)
            scanf("%s", s[i]);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                for(int k = 0; k < 7; ++k)
                    if(s[i][k] != s[j][k]) ++dis[i][j];
        ans = 0;
        prim();
        printf("The highest possible quality is 1/%d.\n", ans);
    }
}

Truck History

Description
Advanced Cargo Movement, Ltd. uses trucks of different types. Some trucks are used for vegetable delivery, other for furniture, or for bricks. The company has its own code describing each type of a truck. The code is simply a string of exactly seven lowercase letters (each letter on each position has a very special meaning but that is unimportant for this task). At the beginning of company’s history, just a single truck type was used but later other types were derived from it, then from the new types another types were derived, and so on.
Today, ACM is rich enough to pay historians to study its history. One thing historians tried to find out is so called derivation plan – i.e. how the truck types were derived. They defined the distance of truck types as the number of positions with different letters in truck type codes. They also assumed that each truck type was derived from exactly one other truck type (except for the first truck type which was not derived from any other type). The quality of a derivation plan was then defined as
1/Σ(to,td)d(to,td)
where the sum goes over all pairs of types in the derivation plan such that t o is the original type and t d the type derived from it and d(t o,t d) is the distance of the types.
Since historians failed, you are to write a program to help them. Given the codes of truck types, your program should find the highest possible quality of a derivation plan.

Input

The input consists of several test cases. Each test case begins with a line containing the number of truck types, N, 2 <= N <= 2 000. Each of the following N lines of input contains one truck type code (a string of seven lowercase letters). You may assume that the codes uniquely describe the trucks, i.e., no two of these N lines are the same. The input is terminated with zero at the place of number of truck types.

Output

For each test case, your program should output the text “The highest possible quality is 1/Q.”, where 1/Q is the quality of the best derivation plan.

Sample Input

4 aaaaaaa baaaaaa abaaaaa aabaaaa 0

Sample Output

The highest possible quality is 1/3.

Source

CTU Open 2003

题意 输入n 然后输入n个数 代表连接时每个站点自身的消耗 然后输入n/*n的矩阵 第i行第j列的数代表第i个站点和第j个站点之间路上的花费 链接i,j两个节点的总花费为两站点自身花费加上路上的花费 求⑩这n个站点连通的最小总花费

又是裸的最小生成树 给点的就用prim咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int cost[N], mat[N][N], a[N], n, ans;

void prim()
{
    memset(cost, 0x3f, sizeof(cost));
    cost[1] = -1;
    //cost[i]为把第i个节点加入到最小生成树的最小花费,-1代表已经加入
    int cur = 1, next = 0;
    //cur为当前加入到最小生成树中的节点
    //next为下一个应该加入最小生成树的节点
    for(int i = 1; i < n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            if(cost[j] == -1 || j == cur) continue;
            cost[j] = min(cost[j], mat[cur][j]);
            if(cost[j] < cost[next]) next = j;
        }
        ans += cost[next];
        cur = next, cost[cur] = -1, next = 0;
    }
}

int main()
{
    int cas, t;
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for(int i = 1; i <= n; ++i)
        {
           for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &t);
                mat[i][j] = a[i] + a[j] + t;
            }
        }
        ans = 0;  prim();
        printf("%d\n", ans);
    }
    return 0;
}

QS Network Time Limit:2 Seconds Memory Limit:65536 KB

Sunny Cup 2003 - Preliminary Round

April 20th, 12:00 - 17:00

In the planet w-503 of galaxy cgb, there is a kind of intelligent creature named QS. QScommunicate with each other via networks. If two QS want to get connected, they need to buy two network adapters (one for each QS) and a segment of network cable. Please be advised that ONE NETWORK ADAPTER CAN ONLY BE USED IN A SINGLE CONNECTION.(ie. if a QS want to setup four connections, it needs to buy four adapters). In the procedure of communication, a QS broadcasts its message to all the QS it is connected with, the group of QS who receive the message broadcast the message to all the QS they connected with, the procedure repeats until all the QS’s have received the message.

A sample is shown below:

A sample QS network, and QS A want to send a message.
Step 1. QS A sends message to QS B and QS C;
Step 2. QS B sends message to QS A ; QS C sends message to QS A and QS D;
Step 3. the procedure terminates because all the QS received the message.

Each QS has its favorate brand of network adapters and always buys the brand in all of its connections. Also the distance between QS vary. Given the price of each QS’s favorate brand of network adapters and the price of cable between each pair of QS, your task is to write a program to determine the minimum cost to setup a QS network.

Input

The 1st line of the input contains an integer t which indicates the number of data sets.
From the second line there are t data sets.
In a single data set,the 1st line contains an interger n which indicates the number of QS.
The 2nd line contains n integers, indicating the price of each QS’s favorate network adapter.
In the 3rd line to the n+2th line contain a matrix indicating the price of cable between ecah pair of QS.

Constrains:

all the integers in the input are non-negative and not more than 1000.

Output

for each data set,output the minimum cost in a line. NO extra empty lines needed.

Sample Input

1
3
10 20 30
0 100 200
100 0 300
200 300 0

Sample Output

370

题意 在n个村庄之间修路使所有村庄连通 其中有些路已经修好了 求至少还需要修多长路

还是裸的最小生成树 修好的边权值为0就行咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 105, M = 10050;
int par[N], n, m, mat[N][N];
int ans;
struct edge{int u, v, w;} e[M];
bool cmp(edge a, edge b){return a.w < b.w;}

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union (int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] < par[rv])
        par[rv] = ru, par[ru] = tmp;
    else
        par[ru] = rv, par[rv] = tmp;
}

void kruskal()
{
    memset(par, -1, sizeof(par));
    int cnt = 0;
    for(int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ++cnt;
            ans += e[i].w;
            Union(u, v);
        }
        if(cnt >= n - 1) break;
    }
}

int main()
{
    int t, u, v;
    while(~scanf("%d", &n))
    {
        m = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                scanf("%d", &mat[i][j]);
                if(j < i) e[++m].u = i, e[m].v = j, e[m].w = mat[i][j];
            }
        }

        scanf("%d", &t);
        while(t--)
        {
            scanf("%d%d", &u, &v);
            e[++m].u = u, e[m].v = v, e[m].w = 0;
        }

        sort(e + 1, e + m + 1, cmp);
        ans = 0; kruskal();
        printf("%d\n", ans);
    }
    return 0;
}

Constructing Roads

Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 19755 Accepted: 8250

Description
There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

Input

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 1000]) between village i and village j.
Then there is an integer Q (0 <= Q <= N /* (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

Output

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

Sample Input

3 0 990 692 990 0 179 692 179 0 1 1 2

Sample Output

179

题意 有n个空间站 接下n行依次输入n个空间站的x,y,z坐标和半径 求连接所有空间站总共至少要修多长的桥

也是裸的最小生成树 注意距离不会小于0 就是两个空间站相交的时候

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 105, M = 10050;
int par[N], n, m;
double ans;
struct edge{int u, v; double w;} e[M];
bool cmp(edge a, edge b){return a.w < b.w;}

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union (int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] < par[rv])
        par[rv] = ru, par[ru] = tmp;
    else
        par[ru] = rv, par[rv] = tmp;
}

void kruskal()
{
    memset(par, -1, sizeof(par));
    int cnt = 0;
    for(int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ++cnt;
            ans += e[i].w;
            Union(u, v);
        }
        if(cnt >= n - 1) break;
    }
}

int main()
{
    double x[N], y[N], z[N], r[N], dis;
    while(scanf("%d", &n), n)
    {
        m = 0;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%lf%lf%lf%lf", &x[i], &y[i], &z[i], &r[i]);
            for(int j = 1; j < i; ++j)
            {
                double tx = x[i] - x[j], ty = y[i] - y[j], tz = z[i] - z[j];
                double dis = sqrt(tx * tx + ty * ty + tz * tz) - r[i] - r[j];
                e[++m].u = i, e[m].v = j, e[m].w = max(0.0, dis);
            }
        }
        sort(e + 1, e + m + 1, cmp);
        ans = 0;
        kruskal();
        printf("%.3f\n", ans);
    }
    return 0;
}

Building a Space Station

Description
You are a member of the space station engineering team, and are assigned a task in the construction process of the station. You are expected to write a computer program to complete the task.
The space station is made up with a number of units, called cells. All cells are sphere-shaped, but their sizes are not necessarily uniform. Each cell is fixed at its predetermined position shortly after the station is successfully put into its orbit. It is quite strange that two cells may be touching each other, or even may be overlapping. In an extreme case, a cell may be totally enclosing another one. I do not know how such arrangements are possible.
All the cells must be connected, since crew members should be able to walk from any cell to any other cell. They can walk from a cell A to another cell B, if, (1) A and B are touching each other or overlapping, (2) A and B are connected by a `corridor’, or (3) there is a cell C such that walking from A to C, and also from B to C are both possible. Note that the condition (3) should be interpreted transitively.
You are expected to design a configuration, namely, which pairs of cells are to be connected with corridors. There is some freedom in the corridor configuration. For example, if there are three cells A, B and C, not touching nor overlapping each other, at least three plans are possible in order to connect all three cells. The first is to build corridors A-B and A-C, the second B-C and B-A, the third C-A and C-B. The cost of building a corridor is proportional to its length. Therefore, you should choose a plan with the shortest total length of the corridors.
You can ignore the width of a corridor. A corridor is built between points on two cells’ surfaces. It can be made arbitrarily long, but of course the shortest one is chosen. Even if two corridors A-B and C-D intersect in space, they are not considered to form a connection path between (for example) A and C. In other words, you may consider that two corridors never intersect.

Input

The input consists of multiple data sets. Each data set is given in the following format.
n
x1 y1 z1 r1
x2 y2 z2 r2
…
xn yn zn rn
The first line of a data set contains an integer n, which is the number of cells. n is positive, and does not exceed 100.
The following n lines are descriptions of cells. Four values in a line are x-, y- and z-coordinates of the center, and radius (called r in the rest of the problem) of the sphere, in this order. Each value is given by a decimal fraction, with 3 digits after the decimal point. Values are separated by a space character.
Each of x, y, z and r is positive and is less than 100.0.
The end of the input is indicated by a line containing a zero.

Output

For each data set, the shortest total length of the corridors should be printed, each in a separate line. The printed values should have 3 digits after the decimal point. They may not have an error greater than 0.001.
Note that if no corridors are necessary, that is, if all the cells are connected without corridors, the shortest total length of the corridors is 0.000.

Sample Input

3 10.000 10.000 50.000 10.000 40.000 10.000 50.000 10.000 40.000 40.000 50.000 10.000 2 30.000 30.000 30.000 20.000 40.000 40.000 40.000 20.000 5 5.729 15.143 3.996 25.837 6.013 14.372 4.818 10.671 80.115 63.292 84.477 15.120 64.095 80.924 70.029 14.881 39.472 85.116 71.369 5.553 0

Sample Output

20.000 0.000 73.834

题意 给你n个点 m条边 求最小生成树的权

这是最裸的最小生成树了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 55, M = 3000;
int par[N], n, m, ans;
struct edge{int u, v, w;} e[M];
bool cmp(edge a, edge b){return a.w < b.w;}

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union (int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] < par[rv])
        par[rv] = ru, par[ru] = tmp;
    else
        par[ru] = rv, par[rv] = tmp;
}

void kruskal()
{
    memset(par, -1, sizeof(par));
    int cnt = 0;
    for(int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ++cnt;
            ans += e[i].w;
            Union(u, v);
        }
        if(cnt >= n - 1) break;
    }
}

int main()
{
    int u, v, w;
    while(scanf("%d", &n), n)
    {
        scanf("%d", &m);
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            e[i].u = u, e[i].v = v, e[i].w = w;
        }
        sort(e + 1, e + m + 1, cmp);
        ans = 0;
        kruskal();
        printf("%d\n", ans);
    }
    return 0;
}

Networking Time Limit:2 Seconds Memory Limit:65536 KB

You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you are given the length of the cable that is needed to connect the points over that route. Note that there may exist many possible routes between two given points. It is assumed that the given possible routes connect (directly or indirectly) each two points in the area.
Your task is to design the network for the area, so that there is a connection (direct or indirect) between every two points (i.e., all the points are interconnected, but not necessarily by a direct cable), and that the total length of the used cable is minimal.

Input

The input file consists of a number of data sets. Each data set defines one required network. The first line of the set contains two integers: the first defines the number P of the given points, and the second the number R of given routes between the points. The following R lines define the given routes between the points, each giving three integer numbers: the first two numbers identify the points, and the third gives the length of the route. The numbers are separated with white spaces. A data set giving only one number P=0 denotes the end of the input. The data sets are separated with an empty line.
The maximal number of points is 50. The maximal length of a given route is 100. The number of possible routes is unlimited. The nodes are identified with integers between 1 and P (inclusive). The routes between two points i and j may be given as i j or as j i.

Output

For each data set, print one number on a separate line that gives the total length of the cable used for the entire designed network.

Sample Input

1 0
2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

Sample Output

0
17
16
26

题意 有n个村子 输入n 然后n-1行先输入村子的序号和与该村子相连的村子数t 后面依次输入t组s和tt s为村子序号 tt为与当前村子的距离 求链接所有村子的最短路径

还是裸的最小生成树咯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30,M=1000;
int par[N],n,m,ans;
struct edge{int u,v,w;} e[M];
bool cmp(edge a,edge b) {return a.w<b.w;}

int Find(int x)
{
    int r=x,tmp;
    while(par[r]>=0) r=par[r];
    while(x!=r)
    {
        tmp=par[x];
        par[x]=r;
        x=tmp;
    }
    return r;
}

void Union (int u,int v)
{
    int ru=Find(u),rv=Find(v),tmp=par[ru]+par[rv];
    if(par[ru]<par[rv])
        par[rv]=ru,par[ru]=tmp;
    else
        par[ru]=rv,par[rv]=tmp;
}

void kruskal()
{
    memset(par,-1,sizeof(par));
    int cnt=0;
    for(int i=1;i<=m;++i)
    {
        int u=e[i].u,v=e[i].v;
        if(Find(u)!=Find(v))
        {
            ++cnt;
            ans+=e[i].w;
            Union(u,v);
        }
        if(cnt>=n-1) break;
    }
}

int main()
{
    char s[2]; int t,tt;
    while(scanf("%d",&n),n)
    {
        m=0;
        for(int i=1;i<n;++i)
        {
            scanf("%s%d",s,&t);
            for(int j=1;j<=t;++j)
            {
                scanf("%s%d",s,&tt);
                e[++m].u=i,e[m].v=s[0]-'A'+1,e[m].w=tt;
            }
        }

        sort(e+1,e+m+1,cmp);
        ans=0; kruskal();
        printf("%d\n",ans);
    }
    return 0;
}

Jungle Roads

Description

The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

Input

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

Output

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

Sample Input

9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 3 A 2 B 10 C 40 B 1 C 20 0

Sample Output

216 30

题意 求n个点m条边的图的连通子图中最长边的最小值

实际上就是求最小生成树中的最长边 因为最小生成树的最长边肯定是所有生成树中最长边最小的 那么就也变成了最小生成树了 不要被样例坑到了 样例并不是最佳方案 只是最长边与最小生成树的最长边相等 题目是特判 直接用最小生成树做就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005, M = 15005;
struct edge{int u, v, w;} e[M];
int par[N], ea[N], n, m, num, ans;
bool cmp(edge a, edge b){ return a.w < b.w; }

int Find(int x)
{
    int r = x, tmp;
    while(par[r] >= 0) r = par[r];
    while(x != r)
    {
        tmp = par[x];
        par[x] = r;
        x = tmp;
    }
    return r;
}

void Union(int u, int v)
{
    int ru = Find(u), rv = Find(v), tmp = par[ru] + par[rv];
    if(par[ru] > par[rv])
        par[ru] = rv, par[rv] = tmp;
    else
        par[rv] = ru, par[ru] = tmp;
}

void kruskal()
{
    memset(par, -1, sizeof(par));
    for(int i = 1; i <= m; ++i)
    {
        int u = e[i].u, v = e[i].v;
        if(Find(u) != Find(v))
        {
            ea[++num] = i;
            ans = max(ans, e[i].w);
            Union(u, v);
        }
        if(num >= n - 1) break;
    }
}

int main()
{
    int u, v, w;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &u, &v, &w);
            e[i].u = u, e[i].v = v, e[i].w = w;
        }

        sort(e + 1, e + m + 1, cmp);
        ans = num = 0;
        kruskal();
        printf("%d\n%d\n", ans, num);
        for(int i = 1; i <= num; ++i)
        {
            int j = ea[i];
            printf("%d %d\n", e[j].u, e[j].v);
        }
    }
    return 0;
}

Network

Description
Andrew is working as system administrator and is planning to establish a new network in his company. There will be N hubs in the company, they can be connected to each other using cables. Since each worker of the company must have access to the whole network, each hub must be accessible by cables from any other hub (with possibly some intermediate hubs).
Since cables of different types are available and shorter ones are cheaper, it is necessary to make such a plan of hub connection, that the maximum length of a single cable is minimal. There is another problem — not each hub can be connected to any other one because of compatibility problems and building geometry limitations. Of course, Andrew will provide you all necessary information about possible hub connections.
You are to help Andrew to find the way to connect hubs so that all above conditions are satisfied.

Input

The first line of the input contains two integer numbers: N - the number of hubs in the network (2 <= N <= 1000) and M - the number of possible hub connections (1 <= M <= 15000). All hubs are numbered from 1 to N. The following M lines contain information about possible connections - the numbers of two hubs, which can be connected and the cable length required to connect them. Length is a positive integer number that does not exceed 106. There will be no more than one way to connect two hubs. A hub cannot be connected to itself. There will always be at least one way to connect all hubs.

Output

Output first the maximum length of a single cable in your hub connection plan (the value you should minimize). Then output your plan: first output P - the number of cables used, then output P pairs of integer numbers - numbers of hubs connected by the corresponding cable. Separate numbers by spaces and/or line breaks.

Sample Input

4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1

Sample Output

1 4 1 2 1 3 2 3 3 4