BZOJ3741-[PA2014]Kuglarz

题目链接:BZOJ3741-PA2014-Kuglarz

题意:

n个杯子排成一行,编号为1-n,其中某些杯子下面有小球,支付Cij可以知道区间[i,j]内杯子下小球总数的奇偶性,问最少花费多少能保证知道哪些杯子下面有球。

题解:

利用前缀和思想,sum[i]表示区间[0,i]中小球和的奇偶性。我们必须知道所有的sum才能确定藏球的情况。Cij的本质上是确定sum[i-1]和sum[j]之间的关系,这样就转化成了最小生成树的问题。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt=0;
int f[2001];
struct Edge
{
    int u,v,w;
} edge[2001*2001];
bool cmp(Edge x,Edge y)
{
    return x.w<y.w;
}
int getf(int x)
{
    if(f[x]==x)
        return x;
    return f[x]=getf(f[x]);
}
bool march(int x,int y)
{
    int fx=getf(x),fy=getf(y);
    if(fx!=fy)
    {
        f[fy]=fx;
        return 1;
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
        {
            int w;
            scanf("%d",&w);
            edge[++cnt].u=i-1;
            edge[cnt].v=j;
            edge[cnt].w=w;
        }
    }
    sort(edge+1,edge+1+cnt,cmp);
    for(int i=0; i<=n; i++)
        f[i]=i;
    ll ans=0;
    int tot=0;
    for(int i=1; i<=cnt; i++)
    {
        if(march(edge[i].u,edge[i].v))
        {
            tot++;
            ans+=1ll*edge[i].w;
        }
        if(tot==n)
            break;
    }
    printf("%lld\n",ans);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。