UVA12083 Guardian of Decency（二分图最大独立集）

UVA12083 Guardian of Decency（二分图最大独立集）

Problem

Solution

• 原题要求选出的点中任意两点需至少满足一个条件，可以在四个条件都不满足的点间连边，所得图为二分图（一边男一边女），等价于求二分图的最大独立集。

二分图最大独立集与最小覆盖集

• 二分图最独立集大小=结点数-最大匹配（这里的最大匹配可以看成选择有边相连的两个点时要去掉其中一个，最大匹配数即为最小要去掉的点数，同时也是最小覆盖）。
• 覆盖集：对于每条边，至少有一个点要被选中。独立集：对于每条边，至少有一个点不被选中。因此两者互补。最小覆盖集大小=最大匹配的大小。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 505;
int n,t,e[maxn][maxn],py[maxn],used[maxn],mxer,h[maxn],hb1[maxn],hb2[maxn];
string xing[maxn];
bool find(int x){for (int j=1;j<=n;j++){    if (e[x][j]&&!used[j])      {used[j]=1;if (!py[j] || find(py[j])) { py[j]=x;return true;}}}return false;
}
void init()
{memset(py,0,sizeof(py));memset(e,0,sizeof(e));mxer = 0;
}
int main()
{cin>>t;while(t--){init();cin>>n;map<string,int>hob,sp;int cnt1 = 0,cnt2 = 0;for(int i=1;i<=n;i++){string s1,s2;cin>>h[i]>>xing[i]>>s1>>s2;if(!hob[s1]) hob[s1] = ++cnt1;hb1[i] = hob[s1];if(!sp[s2]) sp[s2] = ++cnt2;hb2[i] = sp[s2];}for(int i=1;i<=n;i++){if(xing[i]=="M"){for(int j=1;j<=n;j++){if(xing[j]=="F"){if(abs(h[i]-h[j])<=40&&hb1[i]==hb1[j]&&hb2[i]!=hb2[j])e[i][j] = 1;}}}}for(int i=1;i<=n;i++){memset(used,0,sizeof(used));if(xing[i]=="M")mxer+=find(i);}cout<<n-mxer<<endl;}return 0;
}