题解 P1640 【[SCOI2010]连续攻击游戏】

awdx · 2015-11-24 22:30:55 · 题解

据说写写题解有益RP++

首先膜黄学长orz

这题可以用并查集做…… 新姿势get

我们每有一个武器(a, b)时我们可以把它当做一条边(a, b)。

然后对于构图之后，一个大小为k联通块，我们发现有如下性质：

——如果这个联通块没有环（树）：因为有k-1条边，那么总有方法使其中的k-1个节点被覆盖。容易知道这个联通块中一定不选最大的点。

——如果这个联通块有环：那么这k个节点一定都可以被覆盖

这时我们可以用并查集去维护联通块有没有环，联通块的大小。

然后我们扫一遍就行了……看看该联通块有没有环，如果没有环的话是不是看它是不是这个联通块的最大一个点。

于是这是代码

#include<iostream>
#include<algorithm>
using namespace std;
int fa[1100000], cir[1100000], num[1100000];
int ans;
int n;
int gf(int t)
{
    if (fa[t]==t) return t;
    else 
    {
        fa[t]=gf(fa[t]);
        return fa[t];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    for (int i=1; i<=n+1; ++i) fa[i]=i;
    for (int i=1; i<=n+1; ++i) num[i]=1;
    for (int i=1; i<=n; ++i)
    {
        int a, b;
        cin>>a>>b;
        int ap=gf(a), bp=gf(b);
        if (ap==bp) cir[ap]=1;
        else
        {
            cir[ap]=cir[ap]|cir[bp]; cir[bp]=0;
            num[ap]+=num[bp]; num[bp]=0;
            fa[bp]=ap;
        }
    }
    for (int i=1; i<=n+1; ++i)
        if (!cir[gf(i)])
        {
            if (num[gf(i)]==1) {ans=i-1; break;}
            else num[gf(i)]--;
        }
    cout<<ans;
}