[关键字]：图论
[题目大意]：有n道题只能按顺序回答，每到题只能用两个锦囊中的一个，问最多答上多少道题。
//=================================================================================================
[分析]：一开始看着和一道POJ上的2-sat很像，想都没就开始做，然后我就2了……又仔细看了一遍2-sat的定义：（1）、有N各组每组只能出一个。（2）、某两个之间不能同时选。这道题明显不符和第一的条件，然后仔细一看居然是二分图！每到题想每个可以解开它的锦囊连边，然后求最大匹配。注意的是这道题是要求顺序的，所以要从1到m循环，并且一遇到找不到增广路的就break出来。
[代码]：
View Code #include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int MAXN=1002;int n,m,ans=0;int match[MAXN],map[MAXN][3];bool b[MAXN];bool DFS(int u){for (int i=1;i<=2;++i)if (!b[map[u][i]]) { b[map[u][i]]=1;if (match[map[u][i]]==-1 || DFS(match[map[u][i]])) { match[map[u][i]]=u;return 1; } }return 0;}int main(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); scanf("%d%d",&n,&m);for (int i=1;i<=m;++i) scanf("%d%d",&map[i][1],&map[i][2]); ans=0; memset(match,255,sizeof(match));for (int i=1;i<=m;++i) { memset(b,0,sizeof(b));if (DFS(i)) ++ans; else break; } printf("%d\n",ans);return 0;}转载于:https://www.cnblogs.com/procedure2012/archive/2012/03/12/2391226.html
