Description
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.
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.
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 numbered 0.
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 inp/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
3
1
0 1 10
0 1 20
0 0 0
3
0 1 99
0 2 10
1 2 30
2 3 30
0 0 0
2
0 1 10
0 2 5
0 0 0
Sample Output
Case 1: 15
Case 2: 229/2
Case 3: 15
这题的意思就是让你求出最小生成树和最大生成树的值加起来除以2（如果能整除的话）。。
开始理解题意理解错了，以为最短路和最长路的问题。。。。Orz。。
还有一点，这个题死在了memset函数上，一开始定义了一个 inf = 999999，让它等于一个特别大的数，
然后memset (map,inf,sizeof (map));(map是一个二维数组，是用来保存小值的矩阵)，结果利用Prime求最小生成树出来的都是负数。。这不科学啊。。求最大生成树的函数就是复制的Prime函数，把里面的 > 改成 < ，最大生成树的值都对。。最小的就是负的。然后就找错吧。。时间都浪费在这了。。
以前用的时候也没有出现过这种情况啊。。
memset ()函数里一般就是0 ， 1 ， -1，还有16进制的数。。所以以后初始化数组的时候用16进制数。
#include <stdio.h>
#include <iostream>
#include <string.h>
const int inf = 1e6;
using namespace std;
int map[1000][1000],Map[1000][1000];
int dis[10000],vist[10000];
int MIN = 0,MAX = 0;
int x;
void minn()
{
for(int i = 0; i<=x; i++)
{
vist[i] = 0;
dis[i] = map[0][i];
}
vist[0] = 1 ;
for(int i = 1; i<=x; i++)
{
int min = inf,pos = 0;
for(int j = 0; j<=x; j++)
{
if(vist[j] == 0 && dis[j] < min)
{
min = dis[j];
pos = j;
}
}
MIN += min;
vist[pos] = 1 ;
for(int j = 0; j<=x; j++)
{
if(vist[j] == 0 && dis[j] > map[pos][j])
{
dis[j] = map[pos][j];
}
}
}
}
void maxx()
{
for(int i = 0; i<=x; i++)
{
vist[i] = 0;
dis[i] = Map[0][i];
}
vist[0] = 1 ;
for(int i = 1; i<=x; i++)
{
int min = 0,pos = 0;
for(int j = 0; j<=x; j++)
{
if(!vist[j] && dis[j] > min)
{
min = dis[j];
pos = j;
}
}
MAX += min;
vist[pos] = 1 ;
for(int j = 0; j<=x; j++)
{
if(vist[j] == 0&& dis[j] < Map[pos][j])
{
dis[j] = Map[pos][j];
}
}
}
}
int main()
{
int a,b,c,t;
int cou = 1;
scanf("%d",&t);
while(t--)
{
scanf("%d",&x);
memset(Map,0,sizeof(Map));
memset(map,inf,sizeof (map));
// for(int i = 0; i<=x; i++)
// for(int j = 0; j<=x; j++)
// map[i][j] = inf;
while(~scanf("%d%d%d",&a,&b,&c))
{
if(a==0 &&b==0 &&c==0)
break;
if(c<map[a][b])
map[a][b] = map[b][a] = c;
if(c>Map[a][b])
Map[a][b] = Map[b][a] = c;
}
MIN = 0;
MAX = 0;
minn ();
maxx ();
// printf ("%d %d\n",MIN,MAX);
printf ("Case %d: ",cou);
cou++;
if ((MIN + MAX) % 2 == 0)
printf ("%d\n",(MIN + MAX)/2);
else printf ("%d/2\n",MAX+MIN);
}
return 0;
}