洛谷P1640 [SCOI2010]连续攻击游戏题解

题目链接：P1640 [SCOI2010]连续攻击游戏

题意：lxhgww 最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww 遇到了终极 boss，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击，才能对 boss 产生伤害。也就是说一开始的时候，lxhgww 只能使用某个属性值为 $1$ 的装备攻击 boss，然后只能使用某个属性值为 $2$ 的装备攻击 boss，然后只能使用某个属性值为 $3$ 的装备攻击 boss……以此类推。现在 lxhgww 想知道他最多能连续攻击 boss 多少次？

说实话，这题一眼二分图。

左侧点为属性值，右侧点为装备

然后跑个匈牙利算法就好了

如果匹配某个属性值失败就直接跑路退出循环即可

时间复杂度 $O(k^2),k=$ 最大属性值

但是实际上很难跑到这个上界，所以还是蛮快的

代码1：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)
int n,m,vis[N],mch[N];
vector<int> vec[N];
bool dfs(int u,int now)
{
    if(vis[u]==now)return 0;
    vis[u]=now;
    for(int v:vec[u])
        if(!mch[v]||dfs(mch[v],now))
        {
            mch[v]=u;
            return 1;
        }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(m);
    for(int i=1,x,y; i<=m; i++)
    {
        read(x);read(y);
        n=max(n,max(x,y));
        vec[x].push_back(i);
        vec[y].push_back(i);
    }
    for(int i=1; i<=n; i++)
        if(!dfs(i,i))return printf("%lld\n",i-1),0;
    printf("%lld\n",n);
    return 0;
}

但是这个题还有一个超强的做法

注意到我们并不关心选择了哪些装备

直接把每个武器的两个属性值连无向边

用并查集判断连通块是否存在环

对于一个大小为 $d$ 的连通块

如果其不存在环，则一定有办法使得其中 $d-1$ 个点被选到

显然我们不会选择最大的那个点
如果其存在环，则一定可以使这 $d$ 个点被选到

当然，这些点不一定是连续的 $1,2,3\dots$

因此我们从 $1$ 到 $k+1$ （与上文同义）扫一遍

$k+1$ 的原因是防止正好这所有的属性值都可以选然后就没输出，见代码2

对于不存在环的结点 $i$ ，只要看它是不是这个连通块最大的点即可

这个最大点怎么判断呢？

我们只要维护一下它所在连通块的大小

显然最大的点会最后一次被扫到

那么就搞定了

时间复杂度 $O(k)$ ，跑得飞快

代码2：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e4+15)
namespace MERGE
{
    int f[N],num[N];
    int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
    void init(int n){for(int i=1; i<=n; i++)f[i]=i,num[i]=1;}
}using namespace MERGE;

int n,cir[N];
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);init(N-5);
    for(int i=1,a,b; i<=n; i++)
    {
        read(a);read(b);
        a=find(a);b=find(b);
        if(a==b)
        {
            cir[a]=1;
        }else
        {
            cir[a]|=cir[b];
            num[a]+=num[b];
            f[b]=a;
        }
    }
    for(int i=1,id; i<=N-5; i++)
        if(!cir[id=find(i)])
        {
            if(num[id]==1)
                return printf("%d\n",i-1),0;
            else --num[id];
        }
    return 0;
}