BZOJ1854 [Scoi2010]游戏 [二分图匹配]

$游戏$游戏

题目描述见链接 .

---

$\color{red}{正解部分}$正解部分

由于每个武器只能选择一种属性, 可以想到 二分图,

• 对于武器 $i$i, $x_i, y_i$xi​,yi​ 向 $i$i 连边, 这可以保证每个武器只能选择一个属性的条件,

• 按属性从小到大进行 二分图匹配, 可以保证攻击力连续递增的条件 .

---

$\color{red}{实现部分}$实现部分

• 十年 $OI$OI 一场空, 数组开小见祖宗 .

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 1e6 + 5;

int N;
int num0;
int hs_cnt;
int hs[maxn];
int vis[maxn];
int head[maxn];
int match[maxn];

struct Edge{ int nxt, to; } edge[maxn<<1];

void Add(int from, int to){ edge[++ num0] = (Edge){ head[from], to }; head[from] = num0; }

bool DFS(int k){
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(vis[to]) continue ; vis[to] = 1; hs[++ hs_cnt] = to;
                if(!match[to] || DFS(match[to])) return match[to]=k, true;
        }
        return false;
}

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++){
                int x = read(), y = read();
                Add(x, i), Add(y, i);
        }
        int Ans = 0;
        for(reg int i = 1; i <= 10000; i ++){
                if(DFS(i)) Ans ++; else break ;
                while(hs_cnt) vis[hs[hs_cnt --]] = 0;
        }
        printf("%d\n", Ans);
        return 0;
}