题目链接：https://code.google.com/codejam/contest/11254486/dashboard#s=p2
大意是教授的学生每个人在纸条上写一个自己的topic，每个topic由两个单词组成，那么纸上留下了若干个topic。topic分为 "faked" 或者 "un-faked"，所谓faked意思就是其实这个topic的第一个和第二个单词都是随便由之前纸上已经有的topic来构成的，当然，不能是由原来的同一个topic组成，这样就重复了。现在给出这些topic，原来的顺序不知道，试问，最多可能有多少个topic属于faked。
小数据是最多18个topic，大数据是最多1000个。
首先肯定不能暴力枚举顺序，这样复杂度太高了。小数据的做法是可以二进制标记，哪些topic属于faked，那么不属于faked的那些把它们的两个单词都存进map，检查枚举的faked的topic是否两个单词都在map中存在，更新答案。
大数据的做法其实是规约到二分图最小边覆盖的模型上。如果我们把每个topic的第一个和第二个单词分开，就构成了一个二分图，每个topic其实对应了这张二分图上的一条边。现在的问题就是寻找最少的边集（也就是un-faked topic集）使得所有的点都被边集中的至少一条边覆盖到。
这就意味着所有的单词都会被选出来的topic覆盖到，也就做到了题目中的要求，此时只需要再将topic个数n减去求出来的最小边覆盖（un-faked topic数）就得到了最大的faked topic个数了。
最小边覆盖的计算方式是二分图的点数（左部+右部）减去最大匹配数。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <cassert>
#include <set>
using namespace std; const int N=; bool g[N][N],vis[N];
int nx,ny;
int cx[N],cy[N];
bool dfs(int u){
for (int i=;i<=ny;i++){
if (g[u][i]&&!vis[i]){
vis[i]=true;
if (cy[i]==-||dfs(cy[i])){
cy[i]=u;
cx[u]=i;
return true;
}
}
}
return false;
}
int maxMatch(){
int ret=;
memset(cx,-,sizeof(cx));
memset(cy,-,sizeof(cy));
for (int i=;i<=nx;i++){
if (cx[i]==-){
memset(vis,,sizeof(vis));
ret+=dfs(i);
}
}
return ret;
} string a[N],b[N];
int main () {
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
int T;
cin>>T;
while (T--) {
int n;
cin>>n;
nx=;ny=;
map<string,int>ma,mb;
for (int i=;i<=n;i++) {
cin>>a[i]>>b[i];
if (ma[a[i]]==)
ma[a[i]]=++nx;
if (mb[b[i]]==)
mb[b[i]]=++ny;
}
memset(g,,sizeof g);
for (int i=;i<=n;i++) {
int l=ma[a[i]];
int r=mb[b[i]];
g[l][r]=true;
}
int match=maxMatch();
int minEdgeCover=nx+ny-match;
int ret=n-minEdgeCover;
static int cas=;
cout<<"Case #"<<cas++<<": "<<ret<<endl;
}
return ;
}