[bzoj4883][Lydsy2017年5月月赛]棋盘上的守卫

来自FallDream的博客，未经允许，请勿转载，谢谢。

在一个n*m的棋盘上要放置若干个守卫。对于n行来说，每行必须恰好放置一个横向守卫；同理对于m列来说，每列

必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的，且每个位置最多只能放置一个守卫，一个守卫

不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。

n*m<=10^5

费用流比较好想，把行和列拿出来，第i行向第j列连费用是a[i][j]的边，然后限制每行每列流量1即可。

但是费用流不是很科学（好像有人大力艹过了？），考虑优化。

费用流每次的增广路其实就是选择了费用最小的一行一列，假如把a[i][j]看作i->j的边，那么得到的显然会是一个环套树森林。

那么就跑最小生成树，然后记录每个点所在连通块是树还是图即可。

假如要合并i,j

如果ij都是图了，那么就没办法咯。

不然，i,j在同一个集合时加入这条边即可树->图；不在同一个集合的话，就把他们并起来，然后判断得到的是一个什么图形。

如果原来是树+树，得到树，树+图得到图。

复杂度nmlog(nm)

#include<iostream>

#include<cstdio>

#include<algorithm>

#define rint register int

#define getchar() (*S++)

#define MN 100000

#define ll long long

char B[<<],*S=B;

using namespace std;

inline int read()

{

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

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

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int n,m,cnt=,fa[MN*+];

ll ans=;

struct data{int x,c,r;}a[MN+];

bool b[MN*+];

bool cmp(data a,data b){return a.x<b.x;}

inline int getfa(int x){return !fa[x]?x:fa[x]=getfa(fa[x]);}

int main()

{

    fread(B,,<<,stdin);

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

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

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

            a[++cnt]=(data){read(),i,j+n};

    sort(a+,a+cnt+,cmp);

    for(rint i=;i<=cnt;++i)

    {

        int x=getfa(a[i].c),y=getfa(a[i].r);

        if(!(b[x]&b[y]))

        {

            if(x!=y)

                fa[x]=y,b[y]|=b[x];

            else b[x]=;

            ans+=a[i].x;

        }

    }

    printf("%lld\n",ans);

    return ;

}

巴特西

[bzoj4883][Lydsy2017年5月月赛]棋盘上的守卫

最新文章

热门文章