题解 P1640 【[SCOI2010]连续攻击游戏】
Leianha
2019-09-10 20:12:36
## 二分图匹配
我们都能够想到让每个装备和它的属性去连边.
首先提供一种初步想法：
如果我们闭着眼去跑二分图匹配的最大匹配，那么我们得到的答案很显然是错误的.因为我们在得到最大匹配的时候没有考虑从$1$到$n$的连续性。
那我们该怎么办呢？睁开眼再去跑二分图匹配的最大匹配
我们可以二分一个答案，我们只对小于等于$mid$的属性去跑最大匹配，最后看看匹配的点的个数是否等于mid,如果等于的话说明我们可以都匹配上，那就扩大$l$，否则就缩小$r$。
这样的时间复杂度(在Dinic算法下)是O($n \sqrt{m}log(k)$)其中$k$为10000.时间复杂度只能过前几个数据。
那么我们考虑另一种方法：
我们二分之所以会超时，是因为我们做了很多次无用的最大匹配.我们可以考虑一下匈牙利算法，即对每一个属性点依次进行配对。因为我们是将属性点从大到小依次进行匹配，所以我们不用考虑会有不合法的情况，当我们某一次无法匹配属性点$i$的时候，我们就得到了答案$i-1$.
还有匈牙利算法它只用建单向边，因为我们每次更新的时候都只会用到一个边上的点来更新，用不到另一边上的点。
另外$n=10^6$的时候我们就不能每次memset了，否则也会超时，我们记录一下时间点，在遍历的时候看一下时间点是不是冲突了即可。
还有一定要开大数组 ~~不要问我为什么会知道~~
献上我~~丑陋~~的代码
```cpp
#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;
}
```