1、HDU  1102  Constructing Roads    最小生成树

2、总结:

题意:修路,裸题

(1)kruskal

//kruskal
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#define max(a,b) a>b?a:b
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int N=; int n,k;
int father[N]; struct Eage
{
int st,en,val;
}eage[N*(N+)/]; bool cmp(Eage a,Eage b)
{
return a.val<b.val;
} int findn(int x) //即并查集的查找
{
int t=x;
while(x!=father[x]){
x=father[x];
}
int p;
while(t!=x){
p=t;
t=father[t];
father[p]=x;
}
return x;
} int kruskal()
{
int sum=;
sort(eage,eage+k,cmp);
for(int i=;i<k;i++){
int x=findn(eage[i].st);
int y=findn(eage[i].en);
if(x!=y){
sum+=eage[i].val;
x=findn(x);
y=findn(y);
father[x]=y;
}
}
return sum;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
int m;
k=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&m);
if(i<j){
eage[k].st=i; //st边起点,en边终点,k为边的条数
eage[k].en=j;
eage[k++].val=m;
}
}
} for(int i=;i<=n;i++){
father[i]=i;
}
int q,a,b;
scanf("%d",&q);
while(q--){
scanf("%d%d",&a,&b);
a=findn(a);
b=findn(b);
father[a]=findn(b); //把a与b连通
} int ans=kruskal();
printf("%d\n",ans);
} return ;
}

(2)prim

//prim
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#define max(a,b) a>b?a:b
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
const int N=; int n;
int mapn[N][N];
int visit[N],dis[N]; //dis存储每个点到所选结点的最短距离 int prim()
{
int sum=;
memset(visit,,sizeof(visit));
visit[]=;
for(int i=;i<=n;i++){ //先选第一个结点
dis[i]=mapn[][i];
}
for(int i=;i<n;i++) //注,<不是<=
{
int next,minn=INF;
for(int j=;j<=n;j++){ //找到下一个最近的结点
if(!visit[j]&&minn>dis[j]){
next=j;
minn=dis[j];
}
}
sum+=minn;
visit[next]=; for(int j=;j<=n;j++){ //更新dis
if(!visit[j]&&dis[j]>mapn[next][j]){
dis[j]=mapn[next][j];
}
}
}
return sum;
} int main()
{
int q,a,b;
while(scanf("%d",&n)!=EOF)
{
memset(mapn,INF,sizeof(mapn));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&mapn[i][j]);
}
} scanf("%d",&q);
while(q--){
scanf("%d%d",&a,&b);
mapn[a][b]=mapn[b][a]=;
} int ans=prim();
printf("%d\n",ans);
} return ;
}
04-22 15:37