[BZOJ3714][PA2014]Kuglarz 最小生成树



题面免翻译.
我们注意到,以下三个区间:
[a,b];
[b+1,c];
[a,c].
只需要知道其中两个就可以了.也就是说,三个条件中的任意两个可以推知第三个.
那么体现在一张图上就是说,三条边都连了的话会产生环.
我们要求的是什么呢?容易证明,当这个图联通的时候,就可以确定每个点是否有球啦.
找出权值和最小的边集使得图联通,最小生成树.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
using namespace std;
typedef long long ll;
inline void read(int &x)
{
    x=0;char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
}
int n,map[N][N],v[N],f[N];
ll prim()
{
    ll re=0;
    memset(f,0x3f,sizeof f);
    f[1]=0;
    for(int j,k,i=1;i<=n+1;++i)
    {
        k=0;
        for(j=1;j<=n+1;++j)if(!v[j]&&f[j]<f[k])k=j;
        v[k]=1;re+=f[k];
        for(j=1;j<=n+1;++j)if(!v[j]&&f[j]>map[k][j])
            f[j]=map[k][j];
    }
    return re;
}
int main()
{
    cin>>n;
    memset(map,0x3f,sizeof map);
    for(int j,i=1;i<=n;++i)
    {
        for(j=i;j<=n;++j)
        {
            read(map[i][j+1]);
            map[j+1][i]=map[i][j+1];
        }
    }
    cout<<prim();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注