二分图 BZOJ1854-游戏

· · 个人记录

游戏

网上做法有两种。

一种是并查集

这种我不会...(才不会是因为看起来太麻烦懒得写)

一种玄学二分图。

先把每个点的两个属性值向它连边，然后跑最大匹配。

但是这个二分图的匹配方法比较特殊...

列举1~Max的属性值，一旦该属性值找不到一个对应的节点（即不能成功拓展），那么就立刻break，输出当前值-1；

因为题目要求“攻击值必须连续”。

还有个小细节:

每次寻找拓展的时候不能直接memset清空标记，这样的话时间复杂度直接飙到Max * Max...

所以采用时间戳。

貌似用时间戳代替memset标记的方法也是套路了吧...

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k; 
int link[1000010];
int vis[1000010];//时间戳。否则每次O(10000)的清空会T。 
int head[1000010];
struct node
{
    int nxt,to;
} edge[2000010];
void build(int u,int v)
{
    edge[++k].to=v; edge[k].nxt=head[u];
    head[u]=k; return ;
}
bool dfs(int x,int num)
{
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int j=edge[i].to;
        if(vis[j]!=num)
        {
            vis[j]=num;
            if(link[j]==-1 || dfs(link[j],num))
            {
                link[j]=x; return true;
            }
        }
    }
    return false ;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) link[i]=-1;
    for(int i=1;i<=n;i++)
    {
        int a;
        int b;
        scanf("%d%d",&a,&b);
        build(a,i); build(b,i);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfs(i,i))
        {
            printf("%d",i-1);
            return 0;
        }
    }
    return 0;
}