UVALive 3415 Guardian of Decency

UVALive 3415 Guardian of Decency

UVALive 3415 Guardian of Decency

二分图最大独立集

题意

一个老师带他的一群学生去旅游。带走的这群学生整体必须满足给出四个条件之一。问最多能带走多少学生。

思路

最大独立集就是，选最多的点，使得他们之间没有连边。
将不能共存的学生建边，跑匹配，独立集等于总点减去匹配数。

不过注意，匈牙利是对有向二分图的。如果循环使用

for(int i=1;i<=n;i++)
{for(int j=i+1;j<=n;j++){if(!ok(s[i],s[j])){bpm.addEdge(i,j);}}
}

那么无法保证建图正确，因为ij顺序不一定对。
可以根据男女判二分图，也可以建成无向的二分图，跑完匹配除以2。

代码

#include<bits/stdc++.h>
#define M(a,b) memset(a,b,sizeof(a))
typedef long long LL;
const int MAXN=507;
using namespace std;
struct BPM
{int n, m;vector<int > G[MAXN];int left[MAXN];int right[MAXN];bool T[MAXN];bool S[MAXN];void init(int n,int m){this->n = n;this->m = m;for(int i = 1; i <= n; i++) G[i].clear();}void addEdge(int u, int v){G[u].push_back(v);}bool match(int u){S[u] = true;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!T[v]){T[v] = true;if(left[v] == -1 || match(left[v])){left[v] = u;right[u] = v;return true;}}}return false;}int solve(){memset(left, -1, sizeof(left));memset(right, -1, sizeof(right));int ans = 0;for(int u = 1; u <= n; u++){memset(S, 0, sizeof(S));memset(T, 0, sizeof(T));if(match(u)) ans++;}return ans;}
} bpm;
struct Student
{int h;string sex;string music;string sport;void read(){cin>>h>>sex>>music>>sport;}
}s[MAXN];
bool ok(const Student &a,const Student &b)
{if(a.h-b.h>40||b.h-a.h>40) return 1;if(a.sex==b.sex) return 1;if(a.music!=b.music) return 1;if(a.sport==b.sport) return 1;return 0;
}
int main()
{int T;cin>>T;while(T--){int n;cin>>n;bpm.init(n,n);for(int i=1;i<=n;i++)s[i].read();for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){if(!ok(s[i],s[j])){bpm.addEdge(i,j);bpm.addEdge(j,i);}}}int res=bpm.solve();res=n-res/2;cout<<res<<endl;}return 0;
}