Google Code Jam 2016 Round 1B Problem C. Technobabble

题目链接：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个数了。

最小边覆盖的计算方式是二分图的点数（左部+右部）减去最大匹配数。

代码如下：

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <math.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11 #include <cassert>
12 #include <set>
13 using namespace std;
14 
15 
16 const int N=1005;
17 
18 bool g[N][N],vis[N];
19 int nx,ny;
20 int cx[N],cy[N];
21 bool dfs(int u){
22     for (int i=1;i<=ny;i++){
23         if (g[u][i]&&!vis[i]){
24             vis[i]=true;
25             if (cy[i]==-1||dfs(cy[i])){
26                 cy[i]=u;
27                 cx[u]=i;
28                 return true;
29             }
30         }
31     }
32     return false;
33 }
34 int maxMatch(){
35     int ret=0;
36     memset(cx,-1,sizeof(cx));
37     memset(cy,-1,sizeof(cy));
38     for (int i=1;i<=nx;i++){
39         if (cx[i]==-1){
40             memset(vis,0,sizeof(vis));
41             ret+=dfs(i);
42         }
43     }
44     return ret;
45 }
46 
47 string a[N],b[N];
48 int main () {
49     freopen("in.txt","r",stdin);
50     freopen("out.txt","w",stdout);
51     int T;
52     cin>>T;
53     while (T--) {
54         int n;
55         cin>>n;
56         nx=0;ny=0;
57         map<string,int>ma,mb;
58         for (int i=1;i<=n;i++) {
59             cin>>a[i]>>b[i];
60             if (ma[a[i]]==0)
61                 ma[a[i]]=++nx;
62             if (mb[b[i]]==0)
63                 mb[b[i]]=++ny;
64         }
65         memset(g,0,sizeof g);
66         for (int i=1;i<=n;i++) {
67             int l=ma[a[i]];
68             int r=mb[b[i]];
69             g[l][r]=true;
70         }
71         int match=maxMatch();
72         int minEdgeCover=nx+ny-match;
73         int ret=n-minEdgeCover;
74         static int cas=1;
75         cout<<"Case #"<<cas++<<": "<<ret<<endl;
76     }
77     return 0;
78 }

View Code

Google Code Jam 2016 Round 1B Problem C. Technobabble

相关推荐