欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BZOJ1854: [Scoi2010]游戏 二分图

程序员文章站 2022-05-22 13:35:27
...

很早之前写的题了,发现没有更博,想了想,更一发出来。

Orz ljss

这是冬令营上的例题...之后,我推出来了一种时间复杂度没有问题,空间复杂度没有问题的方法,额(⊙o⊙)…和给出的正解不同,但是能AC

分析:

正解是什么我忘了,我还是讲一下我自己的方法吧...

首先,这是一个并查集的题...但是,我没有用并查集...之后呢,我当时并不会二分图,也不会匈牙利...之后,我根据臆测...莫名其妙的想到了用二分图+匈牙利算法的方法解决这道题...(这也可以?!)

我们可以这样考虑一下,每个武器有两个属性,那么我们可以连两条边,属性和对应的武器号,顺便,开一个桶处理出每一个属性有多少把武器。

之后呢,枚举答案,对,枚举答案!

枚举答案从1到最大值,判断一下桶中的个数是否为0,如果为0,输出i-1,并且退出程序

如果桶中个数为1,那么说明,如果想要到达这个答案,我们必须使用这把武器的这个属性,那么,我们在对应武器的另一个属性的桶中减去这把武器,即:num[a[i^1]]--;

并且,将这把武器打上标记,下次使用的时候,不能继续使用。

在a[i^1]<a[i]的前提下:

如果num[a[i^1]]减成0,那么答案为i-1,并且退出程序。

如果num[a[i^1]]大于1,那么继续枚举答案。

如果num[a[i^1]]恰好等于1,那么我们递归的继续处理a[i^1]这个属性,处理方法同上。

(手动模拟匈牙利算法,捂脸!!!鬼知道我当时怎么想出来的!!!)

时间复杂度:(可过)

附上代码:

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define N 1000005
#define M 10005
int n;
int a[N<<1],num[M],u;
bool vis[N<<1];
struct node
{
    int to,next;
}e[N<<1];
int head[M],cnt;
void add(int x,int y)
{
    e[cnt].to=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
    return ;
}
bool work(int x)
{
    if(num[x]==0&&u>=x)return 0;
    if(num[x]==1&&u>=x)
    {
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to1=e[i].to;
            if(!vis[to1])
            {
                num[a[to1^1]]--;
                vis[to1]=vis[to1^1]=1;
                if(!work(a[to1^1]))
                {
                    return 0;
                }else
                {
                    return 1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d",&n);
    for(int i=0;i<(n<<1);i++)
    {
        scanf("%d",&a[i]);
        num[a[i]]++;
        add(a[i],i);
    }
    int i;
    for(i=1;i<M;i++)
    {
        if(num[i]==0)break;
        if(num[i]==1)
        {
            u=i;
            if(!work(i))
            {
                break;
            }
        }
    }
    printf("%d\n",i-1);
    return 0;
}