正文

洛谷p2319[hnoi2006]超级英雄

author  author  2022-09-09  165

关键词：

题目描述

现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。

这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

输入输出格式

输入格式：

输入的第一行是两个正整数 $技术分享$ 和 $技术分享$ ( $技术分享$ )表示总共有 n 种“锦囊妙计”，编号为 $技术分享$ ，总共有 $技术分享$ 个问题。

以下的m行，每行两个数，分别表示第 $技术分享$ 个问题可以使用的“锦囊妙计”的编号。

注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。

输出格式：

输出的第一行为最多能通过的题数 $技术分享$ ，接下来 $技术分享$ 行，每行为一个整数，第 $技术分享$ 行表示第 $技术分享$ 题使用的“锦囊妙计的编号”。

如果有多种答案，那么任意输出一种，本题使用 Special Judge 评判答案。

输入输出样例

输入样例#1：

输出样例#1：

说明

感谢@zhouyonglong 提供special Judge

裸匈牙利算法

但要注意失败后要直接break

因为题目是这么要求的

屠龙宝刀点击就送

#include <cstring>
#include <cstdio>
bool used[1005];
int solve,n,m,jn[1005],ans[1005],ok[1005][1005];
bool dfs(int x)
{
    for(int i=0;i<n;i++)
    {
        if(ok[x][i]&&!used[i])
        {
            used[i]=1;
            if(jn[i]==0||dfs(jn[i]))
            {
                jn[i]=x;
                ans[x]=i;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int a,b,i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        ok[i][a]=1;
        ok[i][b]=1;
    }
    for(int i=1;i<=m;i++)
    {
        memset(used,0,sizeof(used));
        if(dfs(i)) solve++; 
        else break;
    }
    printf("%d
",solve);
    for(int i=1;i<=solve;i++) printf("%d
",ans[i]);
    return 0;
}

[hnoi2006]超级英雄hero

1191:[HNOI2006]超级英雄HeroTimeLimit: 10Sec MemoryLimit: 162MBhttp://www.lydsy.com/JudgeOnline/problem.php?id=1191Description现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的... 查看详情

[hnoi2006]超级英雄

题目链接#include<cstdio>#include<cstring>#defineMAXN1005usingnamespacestd;intlink[MAXN],vis[MAXN],head[MAXN];structedgeintv,next;G[MAXN<<1];intans[MAXN];intN,M,tot=0;inlinevoidadd(intu 查看详情

bzoj1191:[hnoi2006]超级英雄hero

1191:[HNOI2006]超级英雄HeroTimeLimit:10Sec MemoryLimit:162MBSubmit:4983 Solved:2256[Submit][Status][Discuss]Description现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少... 查看详情

[hnoi2006]超级英雄网络流+二分版

...络流的我这里有一道非常好的"网络流练手题"------[HNOI2006]超级英雄.　　记得很久以前真的有这个节目来着,还是大兵主持的.　　其实这是一道匈牙利板子大水题,但对于我们这种刚学网络流的juruo碰到什么题不用网络流做就非常的... 查看详情

bzoj1191:[hnoi2006]超级英雄hero

1191:[HNOI2006]超级英雄HeroDescription现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确... 查看详情

1191:[hnoi2006]超级英雄hero二分图匹配（？）

bzoj1191[hnoi2006]超级英雄hero

二分图匹配水题。一开始WA了一发，没注意一题没答上就要滚粗。真残酷啊。就像Noip后将要滚粗的自己。//Twenty#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cmath>#include<cstring>#inc 查看详情

bzoj1191hnoi2006超级英雄hero

Description现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进... 查看详情

bzoj1191:[hnoi2006]超级英雄hero

bzoj1191[hnoi2006]超级英雄hero

bzoj1191:[hnoi2006]超级英雄hero

题解：二分图最大匹配，模板题注意：当不能匹配的时候直接输出注意：当不能匹配的时候直接输出注意：当不能匹配的时候直接输出重要的事情说三遍代码：#include<bits/stdc++.h>usingnamespacestd;constintN=1005;intmatch[N],f[N],n,m,x... 查看详情

bzoj1191:[hnoi2006]超级英雄hero

【传送门：BZOJ1191】简要题意：给出m个问题，给出n个锦囊，每个问题可以用两种锦囊解决（有可能这两种锦囊是同一种，这就很尴尬，可能出数据的神犇有点儿懒），但每种锦囊只能用一次，而且只有解决了前面的问题才能解... 查看详情

bzoj1191[hnoi2006]超级英雄hero-二分图匹配

现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题... 查看详情

入门匈牙利算法+hnoi2006hero超级英雄题解

一、关于匈牙利算法匈牙利算法是由匈牙利数学家Edmonds提出的，用增广路径求二分图最大匹配的算法。听起来高端，其实说白了就是：假设不存在单相思（单身狗偷偷抹眼泪），在一个同性恋不合法的国家里（不存在任何歧视#... 查看详情

bzoj1191[hnoi2006]超级英雄hero：二分图匹配匈牙利算法

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1191题意：　　有m道题，每答对一题才能接着回答下一个问题。　　你一道题都不会，但是你有n个“锦囊妙计”（每个只能用一次）。　　对于每道题，你只能用该题规定的两种锦... 查看详情

洛谷p2323[hnoi2006]公路修建问题

P2323[HNOI2006]公路修建问题题目描述输入输出格式输入格式：在实际评测时，将只会有m-1行公路输出格式：输入输出样例输入样例#1：42512651331239424613442输出样例#1：4213251输入样例#2：41512651331239424613443输出样... 查看详情

洛谷p3237[hnoi2014]米特运输(代码片段)

这其实是超级大水题，难度不及一道提高组的dp，如果读懂了题面...好吧我读懂了题面，然而并不知道1号节点是否一定要装满...（根据做题的情况来看1号也是要装满的，尽管不进行能量收集）然而为什么我还是不会做呢。。。... 查看详情

洛谷p3203[hnoi2010]弹飞绵羊lct(代码片段)

题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它... 查看详情