http://acm.hdu.edu.cn/showproblem.php?pid=2768
Per testcase:
* One line with the maximum possible number of satisfied voters for the show.
Sample Input
2
1 1 2
C1 D1
D1 C1
1 2 4
C1 D1
C1 D1
C1 D2
D2 C1
Sample Output
1
3
题目描述：
给出每个观众喜欢的动物和不喜欢的动物，满足一个观众就是要他喜欢的留下了、不喜欢的走人。问最多能满足多少观众。
分析：
每个观众看出一个点，每2个不相容的观众建边，选最多的观众就是找出最多的两两无边相连的点，即|最大独立集|=总点数-|最大匹配数|。
因为边是没有方向的，如果像下面这样建边就wa了。
for(int i=1;i<=v;i++) { for(int j=i+1;j<=v;j++) add(i,j);//建边 }
应该双向建边，最后求的最大匹配数/2。
for(int i=1;i<=v;i++) { for(int j=1;j<=v;j++) add(i,j);//建边 }
代码：
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<sstream> #include<vector> #include<stack> #include<deque> #include<cmath> #include<hash_map> #include<map> #include<queue> #define sd(x) scanf("%d",&x) #define ms(x) memset(x,0,sizeof x) #define fu(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; using namespace __gnu_cxx; typedef long long ll; const int maxn=1e4+6; const int mod=1e9+7; const int INF=1e9; int mat[maxn]; bool used[maxn]; string s1[maxn],s2[maxn]; vector<int> to[maxn]; void add(int x,int y) { if((s1[x]==s2[y])||(s1[y]==s2[x])) { to[x].push_back(y); } } bool find(int x) { used[x]=1; if(!to[x].empty()) fu(i,0,to[x].size()-1) { int y=to[x][i]; if(!mat[y]) { mat[y]=x; return 1; } else { int z=mat[y]; if(!used[z]) { if(find(z)) { mat[y]=x; return 1; } } } } return 0; } void init(int n) { ms(mat); fu(i,1,n) to[i].clear(),s1[i].clear(),s2[i].clear(); } int main() { int T; cin>>T; while(T--) { int c,d,v; sd(c);sd(d);sd(v); init(v); fu(i,1,v) { cin>>s1[i]>>s2[i]; } fu(i,1,v) { fu(j,1,v) { add(i,j);//建边 } } int ans=0; fu(i,1,v) { ms(used); if(find(i)) ans++; } cout<<v-ans/2<<endl; } return 0; }
原文：https://www.cnblogs.com/studyshare777/p/13081233.html