现 在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。主持人问题准备 了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”， 比如求助现场观众，或者去掉若干个错误答案（选择题）等等。 这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种 “锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。现在我来到了节目现场，可是我实在是太笨了，以 至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多 的题数吗？
输入文件的一行是两个正整数n和m(0 < n <1001,0 < m < 1001)表示总共有n中“锦囊妙计”，编号为0~n-1，总共有m个问题。
以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。
注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。
第一行为最多能通过的题数p
【题解】
以前一直以为二分图匹配都是存的真的图。。
其实存的u->v是X集中编号为u的点和Y集中编号为v的点有一条无向边
lk[y] = x表示Y集中编号为y的点指向X集中编号x的点
如此做二分图匹配
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 6 inline void read(int &x) 7 { 8 x = 0;char ch = getchar(), c = ch; 9 while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar(); 10 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar(); 11 if(c == ‘-‘)x = -x; 12 } 13 14 const int MAXN = 1000 + 10; 15 const int MAXM = 1000 + 10; 16 17 struct Edge 18 { 19 int u,v,next; 20 Edge(int _u, int _v, int _next){u = _u;v = _v;next = _next;} 21 Edge(){} 22 }edge[MAXN << 1]; 23 24 int n,m,head[MAXN],cnt; 25 26 inline void insert(int a, int b) 27 { 28 edge[++cnt] = Edge(a,b,head[a]); 29 head[a] = cnt; 30 } 31 32 int lk[MAXN], b[MAXN]; 33 34 int dfs(int u) 35 { 36 for(register int pos = head[u];pos;pos = edge[pos].next) 37 { 38 int v = edge[pos].v; 39 if(!b[v]) 40 { 41 b[v] = 1; 42 if(lk[v] == -1 || dfs(lk[v])) 43 { 44 lk[v] = u; 45 return 1; 46 } 47 } 48 } 49 return 0; 50 } 51 52 int xiongyali() 53 { 54 int ans = 0; 55 memset(lk, -1, sizeof(lk)); 56 for(register int i = 1;i <= m;++i) 57 { 58 memset(b, 0, sizeof(b)); 59 if(dfs(i))++ ans; 60 else return ans; 61 } 62 return ans; 63 } 64 65 int main() 66 { 67 read(n), read(m); 68 register int tmp1, tmp2; 69 for(register int i = 1;i <= m;++ i) 70 { 71 read(tmp1), read(tmp2); 72 insert(i, tmp2); 73 insert(i, tmp1); 74 } 75 printf("%d", xiongyali()); 76 return 0; 77 }
原文：http://www.cnblogs.com/huibixiaoxing/p/7552718.html
