menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[二分图匹配]BZOJ1191(HNOI2006)【超级英雄Hero】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

有 $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协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up