題目連結:http://www.lydsy.com/JudgeOnline/problem.php?id=1191
題意:
有m道題,每答對一題才能接着回答下一個問題。
你一道題都不會,但是你有n個“錦囊妙計”(每個隻能用一次)。
對于每道題,你隻能用該題規定的兩種錦囊中的一種,來解決這道題。
問你最多能解決多少道題。
題解:
二分圖最大比對。
匈牙利算法。
問題與錦囊比對。
最大比對即為最多回答數。
但是題目中要求題目必須連續回答,不能中斷。
是以在給每一個問題配對時,一旦比對不上,就終止比對。
AC Code:
1 #include <iostream>
2 #include <stdio.h>
3 #include <string.h>
4 #define MAX_N 1005
5
6 using namespace std;
7
8 int n,m;
9 int ans=0;
10 int match[MAX_N];
11 bool vis[MAX_N];
12 bool edge[MAX_N][MAX_N];
13
14 bool hungary(int now)
15 {
16 for(int i=0;i<n;i++)
17 {
18 if(edge[now][i] && !vis[i])
19 {
20 vis[i]=true;
21 if(match[i]==-1 || hungary(match[i]))
22 {
23 match[i]=now;
24 return true;
25 }
26 }
27 }
28 return false;
29 }
30
31 void read()
32 {
33 memset(edge,false,sizeof(edge));
34 cin>>n>>m;
35 int a,b;
36 for(int i=0;i<m;i++)
37 {
38 cin>>a>>b;
39 edge[i][a]=true;
40 edge[i][b]=true;
41 }
42 }
43
44 void solve()
45 {
46 memset(match,-1,sizeof(match));
47 for(int i=0;i<m;i++)
48 {
49 memset(vis,false,sizeof(vis));
50 if(hungary(i)) ans++;
51 else break;
52 }
53 }
54
55 void print()
56 {
57 cout<<ans<<endl;
58 }
59
60 int main()
61 {
62 read();
63 solve();
64 print();
65 }
轉載于:https://www.cnblogs.com/Leohh/p/7476650.html