本文共 2127 字，大约阅读时间需要 7 分钟。
#include#include #include using namespace std;const int maxn = 505;const int INF = 999999;int T, n, m, k, t, sum;bool flag;int graph[maxn][maxn];int root[maxn];int city[maxn];int sign[maxn];void prim(){ sum = 0; memset(sign, 0, sizeof(sign)); for(int i = 1; i <= n; i ++) root[i] = graph[1][i]; sign[1] = 1; for(int cnt = 2; cnt <= n; cnt ++) { int min_num = INF; int minn = 1; for(int i = 2; i <= n; i ++) if(root[i] < min_num && !sign[i]) { min_num = root[i]; minn = i; } if(min_num >= INF) { flag = false; break; } sum += min_num; sign[minn] = 1; for(int i = 2; i <= n; i ++) if(graph[minn][i] < root[i] && !sign[i]) root[i] = graph[minn][i]; }}int main(){ scanf("%d", & T); while(T --) { scanf("%d %d %d", & n, & m, & k); for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) { if(i == j) graph[i][j] = 0; else graph[i][j] = INF; } while(m --) { int a, b, c; scanf("%d %d %d", & a, & b, & c); if(c < graph[a][b]) graph[a][b] = graph[b][a] = c; } while(k --) { scanf("%d", & t); for(int i = 0; i < t; i ++) scanf("%d", & city[i]); for(int i = 0; i < t; i ++) for(int j = 0; j < t; j ++) graph[city[i]][city[j]] = 0; } flag = true; prim(); if(flag) printf("%d\n", sum); else printf("-1\n"); } return 0;}
题意：
（摘自timebug|时间漏洞）输入一个T，代表有总共有T组测试数据，接下来一行输入n,m,k，其中n(3<=n<=500)表示城市的个数，m(0<=m<=25000)表示可以选择桥的个数，k(0<=k<=100)表示已连接的分块个数。接着，输入m行可供选择的桥的参数p,q,r，表示该桥连接p和q需要花费c(0<=c<=1000)。最后输入k行，其中，每行的第一个代表(t)，代表有t个已经互相连接在一起的城市，然后，就是t个该城市的代号(1~n)。问：连接所有的城市，所需要的最小花费？若无法连接，则输出-1。 题解： 真不知道这题什么东西..TLE半天…最后从Kruskal改成prim..这道题别做了 无聊 差不多只能卡时间过去。转载地址：http://cctpi.baihongyu.com/