神转化。。。
首先我们考虑因为每一次只会知道奇偶性，所以我们对于一个区间[l,r]是否有球至少保证要知道[l...r]全部的奇偶性才可以判定每个杯子下面是否有球。（意味着如果每个杯子抽象成点，那么这些点之间必须全部连通才会知道每个杯子下面是否有球）
因为要费用最少，所以我们每次选择费用最小且有用的边加上去
然后就变成了最小生成树了。。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,en,h[2005],cnt,f[2005];
long long ans=0;
struct Edge{
int a,b,v;
friend bool operator<(Edge a,Edge b){return a.v<b.v;}
}e[4000005];
void AddEdge(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){f[sb]=sa;}
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("3714.in","r",stdin);
freopen("3714.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
int x;
scanf("%d",&x);
AddEdge(i,j+1,x);
}
}
sort(e+1,e+en+1);
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=en && cnt<=n;i++){
if(Find(e[i].a)!=Find(e[i].b)){Union(Find(e[i].a),Find(e[i].b));ans+=(long long)e[i].v;cnt++;}
}
printf("%lld\n",ans);
return 0;
}
评论 (0)
