BZOJ 1191: [HNOI2006]超级英雄Hero (匈牙利)

Note: This article is available in Chinese only. 本文暂无英文版本。 View original

1191: [HNOI2006]超级英雄Hero
#

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 5221 Solved: 2356 [Submit][Status][Discuss]

Description
#

现在电视台有一种节目叫做超级英雄，大概的流程就是每位选手到台上回答主持人的几个问题，然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？

Input
#

输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”，编号为0~n-1，总共有m个问题。以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。

Output
#

第一行为最多能通过的题数p

Sample Input
#

5 6 3 2 2 0 0 3 0 4 3 2 3 2

Sample Output
#

思路：从题目向2条锦囊妙计连边，注意判重。由于有一道题答错比赛就结束，因此在hung的过程中一旦不能find就直接break掉。

hdu 2444 The Accomodation of Students (交叉染色法+匈牙利算法)

Sep 1, 2016·460 words·1 min

ACM 匈牙利算法

hdu 2444题目链接题意：判断一个有向图是否是二分图，是的话求最大匹配数。思路：交叉染色判二分图，是的话跑遍匈牙利即可。1A. 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年09月01日星期四 14时24分36秒 4File Name :code/hdu/2444.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=205; 32int n,m; 33vector<int>edge[N]; 34int col[N]; 35int link[N]; 36bool vis[N]; 37void init() 38{ 39 for ( int i = 0 ; i <= n ; i++) edge[i].clear(); 40 ms(col,-1); 41} 42bool dfs( int u,int x) 43{ 44 col[u] = x; 45 int siz = edge[u].size(); 46 for ( int i = 0 ; i < siz; i++) 47 { 48 int v = edge[u][i]; 49 if (col[v]==1-x) continue; 50 if (col[v]==x) return false; 51 if (!dfs(v,1-x)) return false; 52 } 53 return true; 54} 55bool solve() 56{ 57 for ( int i = 1 ; i <= n ; i++) if (col[i]==-1) if (!dfs(i,0)) return false; 58 return true; 59} 60bool Find( int u) 61{ 62 int siz = edge[u].size(); 63 for ( int i = 0 ; i < siz; i ++) 64 { 65 int v = edge[u][i]; 66 if (vis[v]) continue; 67 vis[v] = true; 68 if (link[v]==-1||Find(link[v])) 69 { 70 link[v] = u; 71 return true; 72 } 73 } 74 return false; 75} 76int hung( int n) 77{ 78 int ans = 0 ; 79 ms(link,-1); 80 for ( int i = 1 ; i <= n ; i++) 81 { 82 ms(vis,false); 83 if (Find(i)) ans++; 84 } 85 return ans; 86} 87int main() 88{ 89 #ifndef ONLINE_JUDGE 90 freopen("code/in.txt","r",stdin); 91 #endif 92 while (~scanf("%d %d",&n,&m)) 93 { 94 init(); 95 for ( int i = 1 ; i <= m ; i++) 96 { 97 int u,v; 98 scanf("%d%d",&u,&v); 99 edge[u].push_back(v); 100 } 101 if (!solve()) 102 { 103 puts("No"); 104 } 105 else 106 { 107 int ans = hung(n); 108 printf("%d\n",ans); 109 } 110 } 111 #ifndef ONLINE_JUDGE 112 fclose(stdin); 113 #endif 114 return 0; 115}

1191: [HNOI2006]超级英雄Hero#

Description#

Input#

Output#

Sample Input#

Sample Output#

Related