题解 P1640 【[SCOI2010]连续攻击游戏】

· · 题解

是的，我来解释一下二分图的建图：

每件装备只能用一次，如果把攻击序列建成点，就是装备和攻击顺序的匹配。

比如属性值是3和5，那么这件装备要么在3位置要么在5位置被使用。

当然，按攻击顺序开始匹配，一旦匹配不成功，根据题意就必须中止。

还有，每次memset太慢了，用时间戳id。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 1010000
#define MAXM 4040000
#define X(n) (n+10000)
struct Edge
{
    int to,nex;
    Edge(){}
    Edge(int _to, int _nex):to(_to),nex(_nex){}
};
Edge e[MAXM+5];
int first[MAXN+5], book[MAXN+5], match[MAXN+5], N, tot, id, op;
void Add(int a, int b)
{
    e[tot] = Edge(b,first[a]);
    first[a] = tot++;
    return;
}
bool DFS(int x)
{
    for(register int u = first[x], v; u+1; u = e[u].nex)
        if(book[v=e[u].to]-id)
        {
            book[v] = id;
            if(!match[v] || DFS(match[v]))
            {
                match[x] = v, match[v] = x;
                return true;
            }
        }
    return false;
}
int Hungary()
{
    int ans = 0;
    for(register int i = id = 1; i <= 10000; i++, id++)
        if(DFS(i))
            ans++;
        else
            break;
    return ans;
}
int main()
{
    scanf("%d",&N), memset(first,-1,sizeof(first));
    for(register int i = 1, j; i <= N; i++)
        for(j = 0; j < 2; j++)
            scanf("%d",&op), Add(op,X(i)), Add(X(i),op);
    printf("%d\n",Hungary());
     return 0;
}