?pid=3371
题目大意：告诉你有几座城市，再告诉你哪两座城市之间建路要多少钱，，在给你哪几个城市之间已经有路，不需要再建。要求的是要使所有城市之间连通最小要花费多少钱。
这里我用了prim算法。。保存城市之间的权值，对于已经建好的城市，将他们的权值赋为0。还有就是要判断是否能找出最小生成树，如果不可以就输出-1，如果在遍历点的时候，并不能找出一个最小的边，那么肯定就是没有最小生成树。（注意要在每个kase开始的时候将所有的边都初始化为INF）。
贡献了好几次WA。。。因为脑残的在每个kase里面也打了一个while，一直退不出来。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define M 1009#define INF 0x3f3f3f3fint dis[M];int map[M][M];bool vis[M];int n;int ans;int city[M];bool prim(){for(int i = 1;i <= n;i++)dis[i] = map[1][i];vis[1] = true;for(int i = 2;i <= n;i++){int min = INF;int k;for(int j = 1;j <= n;j++){if(!vis[j] && dis[j]<min){min = dis[j];k = j;}}if(min==INF) return false; //判断是否有这个最小生成树，如果找不出这个最小边就意味着没有ans += min;vis[k] = true;for(int j = 1;j <= n;j++){if(!vis[j] && dis[j]>map[k][j]){dis[j] = map[k][j];}}}return true;}int main(){int t;scanf("%d",&t);while(t–){ans = 0;memset(vis,0,sizeof(vis));memset(city,0,sizeof(city));int m,k;scanf("%d%d%d",&n,&m,&k); //一开始打成while(scanf(…)) 被反馈一个WA 找了好久for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++){map[i][j] = INF;map[j][i] = INF;}for(int i = 1;i <= m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(map[a][b]>c)map[a][b] = map[b][a] = c;}for(int i = 1;i <= k;i++){int temp;scanf("%d",&temp);for(int i = 1;i <= temp;i++)scanf("%d",&city[i]);//保存已经连通的城市for(int i = 1;i <= temp;i++)for(int j = i+1;j <= temp;j++){int a = city[i],b = city[j];map[a][b] = 0;map[b][a] = 0;}}bool ok = prim();if(!ok)printf("-1\n");elseprintf("%d\n",ans);}return 0;}
与那些新人和旧人们共同经历吧！
