BZOJ4883 棋盘上的守卫（环套树+最小生成树）

　　容易想到网络流之类的东西，虽然范围看起来不太可做，不过这提供了一种想法，即将行列分别看做点。那么我们需要找一种连n+m条边的方案，使得可以从每条边中选一个点以覆盖所有点。显然每个点至少要连一条边。于是这个东西就必须是环套树森林了，并且显然其可以满足条件。现在要求的就是最小环套树森林。

　　求法类似kruskal，只要连了这条边之后该连通块的边数<=点数就给他连上。显然这样得到的是环套树森林，至于为什么最小，证明方法也与kruskal类似，即如果当前边不冗余却不加，则需要另一条边来做等效（这里等效比较广义，比如树边可以与其端点连通块的环边等效）的事，而贪心过程说明不存在更小的这样的边了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,t,fa[N],size[N],cnt[N];

ll ans;

struct data

{

    int x,y,z;

    bool operator <(const data&a) const

    {

        return z<a.z;

    }

}edge[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4883.in","r",stdin);

    freopen("bzoj4883.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

        t++,edge[t].x=i,edge[t].y=n+j,edge[t].z=read();

    sort(edge+,edge+n*m+);

    for (int i=;i<=n+m;i++) fa[i]=i,size[i]=,cnt[i]=;

    for (int i=;i<=n*m;i++)

    {

        int x=find(edge[i].x),y=find(edge[i].y);

        if (x!=y)

        {

            if (cnt[x]+cnt[y]+<=size[x]+size[y])

            ans+=edge[i].z,fa[x]=y,size[y]+=size[x],cnt[y]+=cnt[x]+;

        }

        else if (cnt[x]<size[x]) ans+=edge[i].z,cnt[x]++;

    }

    cout<<ans;

    return ;

}

秒客网

BZOJ4883 棋盘上的守卫（环套树+最小生成树）

相关文章