這題很簡單，我差不多15分鐘就寫好代碼了，運行結果也是正確的。可提交就是RE，百思不得其解，調了兩個小時的時候，我才忽然發現我存邊的時候數組開小了，我當時也想到肯定是數組問題，但是我卻忽律了圖的邊不等于頂點的個數，我是拿頂點個數來開的數組（我不是用矩陣存的）。改過之后，就AC了。

?1?#include<iostream>
?2?#include<algorithm>
?3?using?namespace?std;
?4?#define?MAXN?110
?5?struct?edge{
?6???int?s;
?7???int?e;
?8???int?dis;
?9?}a[MAXN*60];
10?
11?int?N,Q,pre[MAXN],rank[MAXN];
12?
13?void?init(){
14???int?i;
15???for(i=1;i<=N;i++){
16?????pre[i]=-1;
17?????rank[i]=1;
18???}
19?}
20?
21?int?find(int?i){
22???if(pre[i]==-1)?return?i;
23???else?return?pre[i]=find(pre[i]);
24?}
25?
26?void?Union(int?i,int?j){
27???i=find(i);
28???j=find(j);
29???if(i==j)?return;
30???int?temp=rank[i]+rank[j];
31???if(rank[i]<rank[j]){
32?????pre[i]=j;
33?????rank[j]=temp;
34???}
35???else{
36?????pre[j]=i;
37?????rank[i]=temp;
38???}
39?}
40?int?cmp(const?void?*c,const?void?*b){
41???return?(*(edge*)c).dis-(*(edge*)b).dis;
42?}
43?int?main(){
44???int?i,j,k,temp;
45???int?z,y,sum;
46???while(scanf("%d",&N)!=-1){?
47?????k=0;
48?????for(i=1;i<=N;i++){
49???????for(j=1;j<=i;j++)?scanf("%d",&temp);
50???????for(;j<=N;j++){
51?????????scanf("%d",&temp);
52?????????a[k].s=i;
53?????????a[k].e=j;
54?????????a[k].dis=temp;
55?????????k++;
56???????}
57?????}
58?????qsort(a,k,sizeof(a[0]),cmp);
59?????init();
60?????scanf("%d",&Q);
61?????while(Q--){
62???????scanf("%d%d",&z,&y);
63???????Union(z,y);
64?????}
65?????sum=0;
66?????for(i=0;i<k;i++){
67???????if(find(a[i].s)!=find(a[i].e)){
68?????????sum+=a[i].dis;
69?????????Union(a[i].s,a[i].e);
70???????}
71?????}
72?????printf("%d\n",sum);
73???}????
74?}

轉載于:https://www.cnblogs.com/saintqdd/archive/2007/11/07/951690.html

總結

以上是生活随笔為你收集整理的hdu 1102 pku 2421 解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。