lightoj1029

maksyuki 发表于 oj 分类，标签: 图论-最小生成树

27 8月 2015

1029 - Civil and Evil Engineer

Since the Civil Engineer is clever enough and tries to make some profit, he made a plan. His plan is to find the best possible connection scheme and the worst possible connection scheme. Then he will report the average of the costs.A Civil Engineer is given a task to connect n houses with the main electric power station directly or indirectly. The Govt has given him permission to connect exactly n wires to connect all of them. Each of the wires connects either two houses, or a house and the power station. The costs for connecting each of the wires are given.

Now you are given the task to check whether the Civil Engineer is evil or not. That's why you want to calculate the average before he reports to the Govt.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains a blank line and an integer n (1 ≤ n ≤ 100) denoting the number of houses. You can assume that the houses are numbered from 1 to n and the power station is numbered0. Each of the next lines will contain three integers in the form u v w (0 ≤ u, v ≤ n, 0 < w ≤ 10000, u ≠ v) meaning that you can connect u and v with a wire and the cost will be w. A line containing three zeroes denotes the end of the case. You may safely assume that the data is given such that it will always be possible to connect all of them. You may also assume that there will not be more than 12000 lines for a case.

Output

For each case, print the case number and the average as described. If the average is not an integer then print it in p/q form. Where p is the numerator of the result and q is the denominator of the result; p and q are relatively-prime. Otherwise print the integer average.

Sample Input

Output for Sample Input

310 1 10

0 1 20

0 0 0

0 1 99

0 2 10

1 2 30

2 3 30

0 0 0

0 1 10

0 2 5

0 0 0

Case 1: 15Case 2: 229/2Case 3: 15

题目类型：MST

算法分析：将边表edge按照边权从小到大和从大到小排两次并使用kruskal分别计算权值和，最后求两者之和并按照题目要求输出即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 16000;

struct Node
{
    int u, v, w;
};

Node edge[maxn];
int len, suma, sumb, parent[666];
int n;

void Init ()
{
    int i;
    for (i = 0; i < 666; i++)
        parent[i] = i;
}

int UnFind (int val)
{
    if (parent[val] == val)
        return val;

return parent[val] = UnFind (parent[val]);
}

void kruskal ()
{
    Init ();

    int i, remain = n;
    for (i = 0; i < len && remain > 1; i++)
    {
        if (UnFind (edge[i].u) != UnFind (edge[i].v))
        {
            parent[UnFind(edge[i].u)] = UnFind (edge[i].v);
            remain--;
            suma += edge[i].w;
        }
    }
}

int gcd (int a, int b)
{
    if (b == 0)
        return a;

return gcd (b, a % b);
}

bool Cmpa (Node a, Node b)
{
    return a.w < b.w;
}

bool Cmpb (Node a, Node b)
{
    return a.w > b.w;
}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        cout << "Case " << flag++ << ": ";

        cin >> n;
        n++;

        len = 0;
        while (cin >> edge[len].u >> edge[len].v >> edge[len].w)
        {
            if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)
                break;

            len++;
        }

        suma = 0;
        sort (edge, edge + len, Cmpa);
        kruskal ();

        sumb = suma;
        suma = 0;
        sort (edge, edge + len, Cmpb);
        kruskal ();

        int tot = suma + sumb;
        if (tot % 2 == 0)
            cout << tot / 2 << endl;

        else
        {
            int temp = gcd (max (tot, 2), min (tot, 2));
            cout << tot / temp << "/" << 2 / temp << endl;
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 16000;

struct Node

{

int u, v, w;

};

Node edge[maxn];

int len, suma, sumb, parent[666];

int n;

void Init ()

{

int i;

for (i = 0; i < 666; i++)

parent[i] = i;

}

int UnFind (int val)

{

if (parent[val] == val)

return val;

return parent[val] = UnFind (parent[val]);

}

void kruskal ()

{

Init ();

int i, remain = n;

for (i = 0; i < len && remain > 1; i++)

{

if (UnFind (edge[i].u) != UnFind (edge[i].v))

{

parent[UnFind(edge[i].u)] = UnFind (edge[i].v);

remain--;

suma += edge[i].w;

}

int gcd (int a, int b)

{

if (b == 0)

return a;

return gcd (b, a % b);

}

bool Cmpa (Node a, Node b)

{

return a.w < b.w;

}

bool Cmpb (Node a, Node b)

{

return a.w > b.w;

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cout << "Case " << flag++ << ": ";

cin >> n;

n++;

len = 0;

while (cin >> edge[len].u >> edge[len].v >> edge[len].w)

{

if (edge[len].u == 0 && edge[len].v == 0 && edge[len].w == 0)

break;

len++;

}

suma = 0;

sort (edge, edge + len, Cmpa);

kruskal ();

sumb = suma;

suma = 0;

sort (edge, edge + len, Cmpb);

kruskal ();

int tot = suma + sumb;

if (tot % 2 == 0)

cout << tot / 2 << endl;

else

{

int temp = gcd (max (tot, 2), min (tot, 2));

cout << tot / temp << "/" << 2 / temp << endl;

}

return 0;

}

lightoj1020

lightoj1035

超客的水墨烟雨

lightoj1029

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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