题目:http://acm.hdu.edu.cn/showproblem.php?pid=3371
984ms风险飘过~~~
/************************************************************************/
/*
hdu Connect the Cities
最小生成树
题目大意:最小生成树,题目很长,题意很简单就是最小生成树。关键是构建图
*/
/************************************************************************/ #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h> #define MAX 0xfffffff const int N = ;
int map[N][N];
int vis[N];
int mark[N];
int num,n; void build_map()
{
int m,k;
int q,p,c;
int t; scanf("%d%d%d",&n,&m,&k);
for (int i = ; i <= n; i++)
for (int j = i; j <= n; j++)
map[i][j] = map[j][i] = ((i==j)?:MAX); for (int i = ; i < m; i++)
{
scanf("%d%d%d",&p,&q,&c);
if (map[p][q] > c)
{
map[p][q] = map[q][p] = c;
} }
while(k--)
{
scanf("%d",&t);
for (int i = ; i < t; i++)
{
scanf("%d",&mark[i]);
for (int j = ; j < i; j++)
{
map[mark[j]][mark[i]] = map[mark[i]][mark[j]] = ;
}
}
}
} int prim()
{
int t = n;
int sum = ;
int min,k;
vis[] = ;
while(--t)
{
min = MAX;
for(int i = ; i <= n; i++)
{
if (vis[i] != && map[][i] < min)
{
min = map[][i];
k = i;
}
}
if(min == MAX)break;
vis[k] = ;
sum += min;
for (int i = ; i <= n; i++)
{
if (vis[i] != && map[k][i] < map[][i])
map[][i] = map[k][i];
}
}
return t==?sum:-;
} int main()
{
scanf("%d",&num);
while(num--)
{
build_map();
memset(vis,,sizeof(vis));
printf("%d\n",prim());
}
return ;
}