【題目大意】

??? 在很久很久以前，曾經有兩個國家和睦相處，無憂無慮的生活著。一年一度的評比大會開始了，作為和平的兩國，一個朋友圈數量最多的永遠都是最值得他人的尊敬，所以現在就是需要你求朋友圈的最大數目。
兩個國家看成是AB兩國，現在是兩個國家的描述：
?? ?1.A國：每個人都有一個友善值，當兩個A國人的友善值a、b，如果a xor b mod 2=1，那么這兩個人都是朋友，否則不是；
?? ?2.B國：每個人都有一個友善值，當兩個B國人的友善值a、b，如果a xor b mod 2=0或者 (a or b)化成二進制有奇數個1，那么兩個人是朋友，否則不是朋友；
?? ?3.A、B兩國之間的人也有可能是朋友，數據中將會給出A、B之間“朋友”的情況。
?? ?4.在AB兩國，朋友圈的定義：一個朋友圈集合S，滿足S∈A∪ B，對于所有的i，j∈ S，i和j是朋友。

?? ?由于落后的古代，沒有電腦這個也就成了每年最大的難題，而你能幫他們求出最大朋友圈的人數嗎？

?

【題目解析】

A國人相互為朋友的只有可能是奇數和偶數。

所以S中A國人員可能：無、1奇數、1偶數、1奇數+1偶數。

?

B國人相互為朋友的可能是奇數和奇數、偶數和偶數、部份奇數和偶數。

所以B國人朋友關系的補圖只有可能是奇數和偶數。是一個二分圖。

補圖的最大獨立集就是是原圖中的最大團。

二分圖上的最大獨立集 = 點數 - 最大匹配。

?

所以可以枚舉上述情況，看選哪個A國人，然后把B國中的、被選擇A國人的朋友中建補圖，求最大匹配。

看眾多大佬用時間戳代替memset。我不會。

?

#include <bits/stdc++.h> #define FOPI freopen("in.txt", "r", stdin); #define FOPO freopen("out.txt", "w", stdout); using namespace std; typedef long long LL; const int maxn = 3000 + 1000; int x, y; int lnk[maxn], vis[maxn], del[maxn]; int a[maxn], b[maxn]; vector<int> v[maxn], odd, even; vector<int> frd[maxn]; int A, B, m;void build(int x, int y) {v[x].push_back(y), v[y].push_back(x); }bool check(int x, int y) {if ((x ^ y) % 2 == 0) return true;int cnt = 0, tmp = x | y;while(tmp){cnt += tmp % 2;tmp >>= 1;}return cnt % 2; }bool dfs(int k) {int sz = v[k].size();for (int i = 0; i < sz; i++){if (!vis[v[k][i]] && del[v[k][i]]){vis[v[k][i]] = 1;if (lnk[v[k][i]] == -1 || dfs(lnk[v[k][i]])){lnk[v[k][i]] = k;return true;}}}return false; }int hungary(int s = 0, int t = 0, int sum = 0) {int cnt = 0;memset(del, 0, sizeof(del));if (s) for (int i = 0; i < frd[s].size(); i++) del[frd[s][i]]++;if (t) for (int i = 0; i < frd[t].size(); i++) del[frd[t][i]]++;for (int i = 1; i <= B; i++) cnt += del[i] = del[i] == sum;for (int i = 1; i <= B; i++) v[i].clear();for (int i = 1; i <= B; i++)for (int j = i+1; j <= B; j++)if (del[i] && del[j] && !check(b[i], b[j])) build(i, j);int res = 0;memset(lnk, -1, sizeof(lnk));for (int i = 1; i <= B; i++){memset(vis, 0, sizeof(vis));if (del[i] && dfs(i)) res++;}return cnt - res / 2; }int main() {//FOPI; scanf("%d%d%d", &A, &B, &m);for (int i = 1; i <= A; i++){scanf("%d", &a[i]);if (a[i] % 2) odd.push_back(i); else even.push_back(i);}for (int i = 1; i <= B; i++) scanf("%d", &b[i]);for (int i = 1; i <= m; i++){scanf("%d%d", &x, &y);frd[x].push_back(y);}int ans = hungary();for (int i = 0; i < odd.size(); i++) ans = max(ans, hungary(odd[i], 0, 1) + 1);for (int i = 0; i < even.size(); i++) ans = max(ans, hungary(even[i], 0, 1) + 1);for (int i = 0; i < odd.size(); i++)for (int j = 0; j < even.size(); j++)ans = max(ans, hungary(odd[i], even[j], 2) + 2);printf("%d\n", ans); }

?

轉載于:https://www.cnblogs.com/ruthank/p/10604136.html

總結

以上是生活随笔為你收集整理的BZOJ - 2744 朋友圈 （二分图上的最大团）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。