bzoj 1854: [Scoi2010]游戏

二分图匹配

我们都能够想到让每个装备和它的属性去连边.

首先提供一种初步想法：

如果我们闭着眼去跑二分图匹配的最大匹配，那么我们得到的答案很显然是错误的.因为我们在得到最大匹配的时候没有考虑从\(1\)到\(n\)的连续性。

那我们该怎么办呢？睁开眼再去跑二分图匹配的最大匹配

我们可以二分一个答案，我们只对小于等于\(mid\)的属性去跑最大匹配，最后看看匹配的点的个数是否等于mid,如果等于的话说明我们可以都匹配上，那就扩大\(l\)，否则就缩小\(r\)。

这样的时间复杂度(在Dinic算法下)是O(\(n \sqrt{m}log(k)\))其中\(k\)为10000.时间复杂度只能过前几个数据。

那么我们考虑另一种方法：

我们二分之所以会超时，是因为我们做了很多次无用的最大匹配.我们可以考虑一下匈牙利算法，即对每一个属性点依次进行配对。因为我们是将属性点从大到小依次进行匹配，所以我们不用考虑会有不合法的情况，当我们某一次无法匹配属性点\(i\)的时候，我们就得到了答案\(i-1\).

还有匈牙利算法它只用建单向边，因为我们每次更新的时候都只会用到一个边上的点来更新，用不到另一边上的点。

另外\(n=10^6\)的时候我们就不能每次memset了，否则也会超时，我们记录一下时间点，在遍历的时候看一下时间点是不是冲突了即可。

还有一定要开大数组 不要问我为什么会知道

献上我丑陋的代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,a,b,tot,now;
const int M=10100,N=1100000;
int head[M],vis[N],k[N];
struct bian
{
    int to,nt;
}e[N<<1];
void add(int f,int t)
{
    e[++tot].to=t;
    e[tot].nt=head[f];
    head[f]=tot;
}
int read()
{
    char ch;int x=0,f=1;
    while(!isdigit(ch=getchar()))
    {(ch=='-')&&(f=-f);}
    while(isdigit(ch))
    {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int find(int x)
{
    for(int i=head[x];i;i=e[i].nt)
    {
        if(vis[e[i].to]==now)continue;
        vis[e[i].to]=now;
        if(!k[e[i].to]||find(k[e[i].to]))
        {
            k[e[i].to]=x;
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        a=read(),b=read();
        add(a,i);add(b,i);
    }
    for(int i=1;i<=10001;++i)
    {
        now=i;
        if(!find(i))
        {
            cout<<i-1;
            return 0;
        }
    }
    return 0;
}