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 思路： 這題直接二分圖匹配即可。? 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define rep(i,a,b) for(R i=a;i<=b;i++) 5 #define Rep(i,a,b) for(R i=a;i>=b;i--) 6 #define gc() getchar() 7 #define ms(i,a) memset(a,i,sizeof(a)) 8 template<class T>void read(T &x){ 9 x=0; char c=0; 10 while (!isdigit(c)) c=gc(); 11 while (isdigit(c)) x=x*10+(c^48),c=gc(); 12 } 13 int const N=1000+3; 14 struct Edge{ 15 int to,nt; 16 }E[N<<1]; 17 int v[N],match[N],H[N],cnt,n,m; 18 void add(int a,int b){ 19 E[cnt]=(Edge){b,H[a]}; H[a]=cnt++; 20 } 21 int find(int x){ 22 for(R i=H[x];i!=-1;i=E[i].nt){ 23 int t=E[i].to; 24 if(v[t]) continue; 25 v[t]=1; 26 if(match[t]==-1 || find(match[t])){ 27 match[t]=x; 28 return 1; 29 } 30 } 31 return 0; 32 } 33 int main(){ 34 read(n); read(m); 35 ms(-1,H); ms(-1,match); 36 rep(i,1,m) { 37 int x,y; 38 read(x); read(y); 39 add(i,x); add(i,y); 40 } 41 int ans=0; 42 rep(i,1,m){ 43 ms(0,v); 44 if(find(i)) ans++; 45 else break; 46 } 47 cout<<ans<<endl; 48 return 0; 49 } View Code

?

轉載于:https://www.cnblogs.com/ZJXXCN/p/10558778.html

總結

以上是生活随笔為你收集整理的bzoj 1191 [HNOI2006]超级英雄Hero的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。