題目鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=1102

這題大意就不講了，

這題很容易，不過我做的很不爽，一個下午，一直WA，后來才發現數組開小了

只開了s[6000],本來100*100=10000，要開至少10000的搞糊了，一直WA

一個下午，以后做題，要把思路全部理清才開始敲代碼，別邊想邊敲，那樣，很容易搞錯

我的代碼

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node
{
int x,y,d;
}s[10005];

int father[111];
int sum;

bool cmp(const node &a,const node &b)
{
return a.d<b.d;
}

int Find(int x)
{
if(x==father[x]) return x;
father[x]=Find(father[x]);
return father[x];
}

void Union(int x,int y,int d)
{
x=Find(x);
y=Find(y);
if(x!=y)
{
father[x]=y;
sum=sum+d;
}
}

int main(void)
{
int n,m,i,j,k,l;
while(scanf("%d",&n)==1)
{
l=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
s[l].x=i;
s[l].y=j;
scanf("%d",&s[l].d);
l++;
}
}
int q,x,y;
scanf("%d",&q);
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
s[(x-1)*n+y-1].d=0;
s[(y-1)*n+x-1].d=0;
}
sort(s,s+l,cmp);
for(i=1;i<=n;i++)
father[i]=i;
sum=0;
for(i=0;i<l;i++)
{
Union(s[i].x,s[i].y,s[i].d);
}
k=0;
for(i=0;i<=n;i++)
{
if(i==father[i])
k++;
}
if(k)
printf("%d\n",sum);
}
return 0;
}

轉載于:https://www.cnblogs.com/liudehao/p/3940339.html

總結

以上是生活随笔為你收集整理的HDU-1102-Constructing Roads（并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

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