P1640 [SCOI2010]连续攻击游戏

Link

好久没写过匈牙利算法了，今天来复习一下。

这题是典型的二分图匹配问题。

我们考虑怎么建边。因为每种装备只能用一次。

所以我们可以把装备属性和他的装备序号连边。然后从一开始匹配，第一个匹配失败的点的上一个就是我们最终的答案。

这个题 \(n\) 的范围挺大的，所以我们不能写网络流（网络流多好写啊）。

匈牙利算法理论上是 O(n^2) 的，但是跑不满，勉勉强强可以过吧。

Code：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,x,y,tot,head[1000010],match[1000010];
bool vis[1000010];
struct node
{
    int to,net;
}e[2000010];
inline int read()
{
    int s = 0,w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
    return s * w;
}
void add(int x,int y)
{
    e[++tot].to = y;
    e[tot].net = head[x];
    head[x] = tot;
}
bool dfs(int x)//二分图匹配
{
    for(int i = head[x]; i; i = e[i].net)
    {
        int to = e[i].to;
        if(!vis[to])//已经尝试过不行的点就不用再尝试匹配了。
        {
            vis[to] = 1;//标记一下
            if(!match[to] || dfs(match[to]))//如果说 to 没有被用，或者 to 还可以找到另一个点来匹配就返回 true
            {
            	match[to] = x;//记录一下和他匹配的是哪个
            	return true;
            }
        }
    }
    return false;
}
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        x = read(); y = read();
        add(x,i); add(y,i);//建边
    }
    for(int i = 1; i <= n+1; i++)//一定要循环到n-1不然第一个点会 WA
    {
        memset(vis,0,sizeof(vis));//每次清空一下，在进行匹配
        if(!dfs(i))
        {
            printf("%d\n",i-1);//第一个匹配失败的点就是我们的答案
            return 0;
        }
    }
}

这道题还可以用并查集来写，先咕着吧，等我写完在更