题目描述
Tyvj的通信渠道分为两大类,一类是必选通信渠道,无论价格多少,你都需要把所有的都选择上;还有一类是选择性的通信渠道,你可以从中挑选一些作为最终管理员联络的通信渠道。
prim算法答案
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dist[3000],ai[3000][3000];
bool st[3000];
int f[3000],n,m,ans;
int find(int x);
int main()
{
scanf("%d%d",&n,&m);
memset(ai,0x3f,sizeof(ai));
for(int i=1;i<=n;i++)
ai[i][i]=0;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&d,&a,&b,&c);
if(d==1)
ans+=c,
f[find(a)]=find(b);
else
ai[a][b]=ai[b][a]=min(ai[a][b],c);
}
for(int i=1;i<=n;i++)
if(find(i)!=i)st[i]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ai[find(i)][find(j)]=min(ai[i][j],ai[find(i)][find(j)]);
memset(dist,0x3f,sizeof(dist));
dist[f[1]]=0;
for(int i=1;i<n;i++)
{
int x=0;
for(int j=1;j<=n;j++)
if(!st[j]&&(x==0||dist[j]<dist[x]))
x=j;
st[x]=1;
for(int j=1;j<=n;j++)
if(!st[j])
dist[j]=min(dist[j],ai[x][j]);
}
for(int i=1;i<=n;i++)
if(dist[i]!=0x3f3f3f3f)
ans+=dist[i];
printf("%d",ans);
return 0;
}
int find(int x)
{
if(x==f[x])
return x;
return f[x]=find(f[x]);
}
以下为题解
memset(ai,0x3f,sizeof(ai));
for(int i=1;i<=n;i++)
ai[i][i]=0;
for(int i=1;i<=n;i++)
f[i]=i;
//以上是初始化
for(int i=1;i<=m;i++)//输入和结合
{
int a,b,c,d;
scanf("%d%d%d%d",&d,&a,&b,&c);
if(d==1)//将一个区域处理到一个点上
ans+=c,
f[find(a)]=find(b);
else
ai[a][b]=ai[b][a]=min(ai[a][b],c);
}
for(int i=1;i<=n;i++)
if(find(i)!=i)st[i]=1;//删除每一个区域的代表点
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
//处理标号为2的点
ai[find(i)][find(j)]=min(ai[i][j],ai[find(i)][find(j)]);
//之后部分为模板
memset(dist,0x3f,sizeof(dist));
dist[f[1]]=0;
for(int i=1;i<n;i++)
{
int x=0;
for(int j=1;j<=n;j++)
if(!st[j]&&(x==0||dist[j]<dist[x]))
x=j;
st[x]=1;
for(int j=1;j<=n;j++)
if(!st[j])
dist[j]=min(dist[j],ai[x][j]);
}
for(int i=1;i<=n;i++)
if(dist[i]!=0x3f3f3f3f)
ans+=dist[i];
printf("%d",ans);
//以及find函数
if(x==f[x])
return x;
return f[x]=find(f[x]);
//虽然是find函数,与Kruskal并无关系