本文主要是介绍HDU 3371和COJ 1191 Connect the Cities（kruscal），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
我靠 简直不忍直视
WA了好多发，原来并查集没错，是把输入给看错了……晕……
原题是：Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
让我看成了输入的是c,p,q，所以一直错，因为这道题目数据正好让我的答案与样例答案一样，所以没想到输入错误的问题，搞了好多，WA了好多发，然后重新看题了才知道，太晕了……………………不过这题在COJ上过了，因为时间是2000ms，所以过了；但是在HDU上，时间是1000ms，所以没过，我还以为是并查集写挫了呢，原来是在HDU上用G++提交会超时，得用C++提交才过……这两个方法的代码都是在HDU上用C++提交才过的……
第一种kruscal：是用秩写的，秩确实树的高度，以确定父子关系
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int edge,sum,f[25002],rank[25002];
struct abc
{int u,v;int len;
} e[25002];
bool cmp(abc a, abc b)
{return a.len<b.len;
}
int find(int k)
{return f[k]==k?k:f[k]=find(f[k]);
}
void uni(int x,int y,int w)
{int a = find(x);int b = find(y);if (a == b) return;//若不在同一集合，则MST中包含该边if(rank[a]>rank[b]) f[b]=a;else{if(rank[a]==rank[b]) rank[b]++;f[a]=b;}sum+=w;edge++;
}
int main()
{int t;scanf("%d", &t);while(t--){int n,m,k,i,j,t1,s[105];edge=0;sum=0;scanf("%d%d%d",&n,&m,&k);for(i=0;i<m;i++){scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].len);}for(i=1;i<=n;i++){f[i]=i;rank[i]=0;}sort(e,e+m,cmp);for(i=0; i<k; i++){scanf("%d", &t1);for(j=0; j<t1; j++){scanf("%d", &s[j]);if(j) uni(s[j],s[j-1],0);}}for(i=0; i<m; i++)uni(e[i].u,e[i].v,e[i].len);if(edge==n-1) printf("%d\n",sum);else printf("-1\n");}return 0;}
改进了一下…这个就不需要用秩了，直接确立父子关系！因为不管他们的大小如何，只要通过find函数，如果有关系，都是根是相同的…通过了HDU，不过用G++提交也没通过的，用C++提交才行……#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<set> #include<queue> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #define mem(a,b) memset(a,b,sizeof(a)) typedef long long ll; using namespace std; int f[25002]; struct abc {int u,v;int len; } e[25002]; bool cmp(abc a, abc b) {return a.len<b.len; } int find(int k) {return f[k]==k?k:f[k]=find(f[k]); } int main() {int t;scanf("%d", &t);while(t--){int edge=0,sum=0,n,m,k,i,j,t1,s[105];scanf("%d%d%d",&n,&m,&k);for(i=0; i<m; i++)scanf("%d%d%d", &e[i].u,&e[i].v,&e[i].len);for(i=1; i<=n; i++)f[i]=i;sort(e,e+m,cmp);for(i=0; i<k; i++){scanf("%d", &t1);for(j=0; j<t1; j++){scanf("%d", &s[j]);if(j){int a1=find(s[j]);int b1=find(s[j-1]);if(a1!=b1){f[a1]=b1;edge++;}}}}for(i=0; i<m; i++){int a1=find(e[i].u);int b1=find(e[i].v);if(a1!=b1){f[a1]=b1;edge++;sum+=e[i].len;}if(edge==n-1) break;}if(edge==n-1) printf("%d\n",sum);else printf("-1\n");}return 0;}
这篇关于HDU 3371和COJ 1191 Connect the Cities（kruscal）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
