1488 新的开始
新的开始…
保证最少的花费,那么很明显这就是一个最小生成树了
做题之前盲猜一下,这个题应该要跑两遍最小生成树,因为他说了使用两种情况,p和v——在井上修建一个和在各个井中间修建一个;所以跑两遍之后进行比较出最小的答案?
我似乎猜对了
补充:C++的小技巧,将cin变成scanf这么快,不过我不想记
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
好了,接着来分析本题
和刚才那个题类似,都是维护两个距离,那么直接进行分类讨论就好了
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
struct node
{
int u,v,w;
bool operator<(const node &x) const
{
return w<x.w;
}
}a[305*305];
int fa[305];
int n,x;
int num;
int findd(int x)
{
if(fa[x]!=x)
fa[x]=findd(fa[x]);
return fa[x];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
a[num].u=i;
a[num].v=n+1;
a[num].w=x;
num++;
fa[i]=i;
}
fa[n+1]=n+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>x;
if(i<j)
{
a[num].u=i;
a[num].v=j;
a[num].w=x;
num++;
}
}
}
sort(a,a+num);
int cnt=0;
int ans=0;
for(int i=0;i<num;i++)
{
int xx=findd(a[i].u),yy=findd(a[i].v);
if(xx!=yy)
fa[xx]=yy,ans+=a[i].w;
if(cnt==n)
break;
}
cout<<ans<<endl;
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)