本文主要是介绍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;
}
这篇关于UVA12083 Guardian of Decency(二分图最大独立集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!