本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=3371，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这是今天xd弄的一个专题，，，，很是坑爹，，，c++过了，但是g++就是过不了，，，让我纠结了半个多小时，，，悲催，，，
prim算法：
#include<iostream>
#include<string.h>
#define N 505
#define M 99999999
#define FOR(i,s,t) for(int i=(s);i<=(t);++i)
using namespace std;
int n,m,p;
int map[N][N];
bool visit[N];
int dist[N];
int prim()
{ FOR(i,1,n){ dist[i]=M;visit[i]=true;}int now=1;dist[now]=0;visit[now]=false;int ans=0;FOR(i,1,n){ FOR(j,1,n)if(visit[j]&&dist[j]>map[now][j])dist[j]=map[now][j];int minx=M;FOR(j,1,n)if(visit[j]&&minx>dist[j])minx=dist[now=j];visit[now]=false;}for(int i=1;i<=n;++i)if(dist[i]==M) return -1;else ans+=dist[i];return ans;}
int main()
{ int Case;scanf("%d",&Case);while(Case--){ scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)map[i][j]=M;for(int i=0;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<=p;i++){ int t,tt;scanf("%d%d",&t,&tt);for(int j=1;j<t;++j)一开始用数组整的，，听了kk了以后在，，，这样整。。{ int a;scanf("%d",&a);map[tt][a]=map[a][tt]=0;}}int ans=prim();printf("%d\n",ans);}}
krusal算法：
#include <stdio.h>
#include <string.h>
#include <set>
using namespace std;
const int MAXN = 501;
struct E{ int x,y , weight;
};set<int> s;
E edge[25001];
int father[MAXN];
int cmp(const void *d1,const void *d2)
{ return (*(E*)d1).weight - (*(E*)d2).weight;}
void makeSet(int n)
{ for(int i = 0; i <= n; i++) father[i] = i;s.clear();
}
int find(int x)
{ return x==father[x]?x:father[x]=find(father[x]);}
int main()
{ int cas,n,m,k,cost; scanf("%d",&cas); while( cas-- )
{ scanf("%d %d %d",&n, &m, &k); makeSet(n); cost = 0; for(int i = 1; i <= m; i++)
{ scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].weight); } int num,first,city; for(int i = 1; i <= k;i++){ scanf("%d%d",&num,&first); for(int j = 1; j < num; j++){ scanf("%d",&city); int xx = find(first); int yy = find(city); if(xx != yy) father[yy]=xx; } } qsort(edge+1,m,sizeof(E),cmp); for(int i = 1; i <= m; i++){ int xx = find(edge[i].x); int yy = find(edge[i].y); if(xx != yy){ father[yy]=xx; cost += edge[i].weight; } } for(int i = 1; i <= n; i++) 整体进行压缩路径。。。find(i); for(int i = 1; i <= n; i++) s.insert(father[i]); 判断根节点的个数，，，，， if(s.size() > 1) printf("-1\n"); else printf("%d\n",cost); } return 0;}
这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=3371的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
