BZOJ-1191 [HNOI2006]超級英雄Hero(二分圖比對)

1191: [HNOI2006]超級英雄Hero

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 3837  Solved: 1767

[​​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

4

HINT

Source

原來BZOJ上也是有水題的ovo，不過他說必須答出這題才能答下一題，是以我就智障的被坑了ovo

1 #include "bits/stdc++.h"
 2 #define mem(a,b) memset(a,b,sizeof(a))
 3 using namespace std;
 4 typedef long long LL;
 5 const int MAX=3005;
 6 int n,m,K,tot;
 7 int head[MAX],adj[MAX],next[MAX],cy[MAX];
 8 bool vis[MAX];
 9 void addedge(int u,int v){
10     tot++;
11     adj[tot]=v;
12     next[tot]=head[u];
13     head[u]=tot;
14 }
15 void init(){
16     int i,j,x,y;
17     scanf("%d%d",&K,&n);
18     mem(head,0),mem(cy,-1);
19     for (i=1;i<=n;i++){
20         scanf("%d%d",&x,&y);
21         ++x,++y;
22         addedge(i,x);
23         addedge(i,y);
24     }
25 }
26 int dfs(int x){
27     int i,j,v;
28     for (i=head[x];i;i=next[i]){
29         v=adj[i];
30         if (!vis[v]){
31             vis[v]=true;
32             if (cy[v]==-1 || dfs(cy[v])){
33                 cy[v]=x;
34                 return 1;
35             }
36         }
37     }
38     return 0;
39 }
40 int main(){
41     freopen ("hero.in","r",stdin);
42     freopen ("hero.out","w",stdout);
43     int i,j;
44     init();
45     for (i=1;i<=n;i++){
46         mem(vis,false);
47         if (!dfs(i)) break;
48     }
49     printf("%d",i-1);
50     return 0;
51