Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?5860??Solved:?2617
[Submit][Status][Discuss]

Description

現(xiàn)在電視臺(tái)有一種節(jié)目叫做超級(jí)英雄,大概的流程就是每位選手到臺(tái)上回答主持人的幾個(gè)問題,然后根據(jù)回答問題的 多少獲得不同數(shù)目的獎(jiǎng)品或獎(jiǎng)金。主持人問題準(zhǔn)備了若干道題目，只有當(dāng)選手正確回答一道題后，才能進(jìn)入下一題 ，否則就被淘汰。為了增加節(jié)目的趣味性并適當(dāng)降低難度，主持人總提供給選手幾個(gè)“錦囊妙計(jì)”，比如求助現(xiàn)場 觀眾，或者去掉若干個(gè)錯(cuò)誤答案（選擇題）等等。這里，我們把規(guī)則稍微改變一下。假設(shè)主持人總共有m道題，選 手有n種不同的“錦囊妙計(jì)”。主持人規(guī)定，每道題都可以從兩種“錦囊妙計(jì)”中選擇一種，而每種“錦囊妙計(jì)” 只能用一次。我們又假設(shè)一道題使用了它允許的錦囊妙計(jì)后，就一定能正確回答，順利進(jìn)入下一題。現(xiàn)在我來到了 節(jié)目現(xiàn)場，可是我實(shí)在是太笨了，以至于一道題也不會(huì)做，每道題只好借助使用“錦囊妙計(jì)”來通過。如果我事先 就知道了每道題能夠使用哪兩種“錦囊妙計(jì)”，那么你能告訴我怎樣選擇才能通過最多的題數(shù)嗎？

Input

輸入文件的一行是兩個(gè)正整數(shù)n和m(0 < n <1001,0 < m < 1001)表示總共有n中“錦囊妙計(jì)”，編號(hào)為0~n-1，總共有m個(gè)問題。
以下的m行，每行兩個(gè)數(shù)，分別表示第m個(gè)問題可以使用的“錦囊妙計(jì)”的編號(hào)。
注意，每種編號(hào)的“錦囊妙計(jì)”只能使用一次，同一個(gè)問題的兩個(gè)“錦囊妙計(jì)”可能一樣。

Output

第一行為最多能通過的題數(shù)p

Sample Input

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

Sample Output

4

HINT

Source

很zz的一道二分圖匹配

對于$m$個(gè)問題，向他能選的兩個(gè)連邊

跑匈牙利

如果不能匹配的話直接退出！！

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #define LL long long using namespace std; const int MAXN = 1e3 + 10, INF = 1e9 + 10; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, M; vector<int> v[MAXN]; int link[MAXN], vis[MAXN], cnt = 1, Ans[MAXN]; bool Aug(int x) {for(int i = 0; i < v[x].size(); i++) {int to = v[x][i];if(vis[to] == cnt) continue;vis[to] = cnt;if(link[to] == -1 || Aug(link[to])) {link[to] = x; return 1;}}return 0; } main() { #ifdef WIN32freopen("1191.in", "r", stdin);freopen("1191.out", "w", stdout); #endifmemset(link, -1, sizeof(link));memset(Ans, -1, sizeof(Ans));N = read(); M = read();for(int i = 0; i < M; i++) {int x = read(), y = read();v[i].push_back(x);if(x != y) v[i].push_back(y);}int ans = 0;for(int i = 0; i < M; i++, cnt++)if(Aug(i)) ans++;else break; for(int i = 0; i < N; i++)Ans[link[i]] = i;printf("%d\n", ans);/*for(int i = 0; i < N; i++)if(Ans[i] != -1)printf("%d\n", Ans[i]);*/return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/9285468.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1191: [HNOI2006]超级英雄Hero(二分图匹配)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。