ZigZagK的博客
[二分图匹配]BZOJ1191(HNOI2006)【超级英雄Hero】题解
ZigZagK
2018年7月7日 20:25
BZOJ
查看标签

题目概述

有 $n$ 个ZZK $m$ 个JZ，每个JZ可以虐两个指定的ZZK中的一个，一个ZZK被虐之后就心态爆炸不能再被虐，问从第一个JZ开始按顺序连续不断的虐ZZK，最多有多少个JZ能虐ZZK。

解题报告

水水博客有利身体健康。

示例程序

#include<cstdio>
using namespace std;
const int maxn=1000;

int n,m,a[maxn+5][2],who[maxn+5],ti,vis[maxn+5],ans;

bool Find(int x){
    if (vis[x]==ti) return false;vis[x]=ti;
    if (!who[a[x][0]]||Find(who[a[x][0]])) return who[a[x][0]]=x,true;
    if (!who[a[x][1]]||Find(who[a[x][1]])) return who[a[x][1]]=x,true;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&a[i][0],&a[i][1]);
        if (ti++,Find(i)) ans++; else break;
    }
    return printf("%d\n",ans),0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！