【題目大意】

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

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

?

【題目解析】

A國(guó)人相互為朋友的只有可能是奇數(shù)和偶數(shù)。

所以S中A國(guó)人員可能：無(wú)、1奇數(shù)、1偶數(shù)、1奇數(shù)+1偶數(shù)。

?

B國(guó)人相互為朋友的可能是奇數(shù)和奇數(shù)、偶數(shù)和偶數(shù)、部份奇數(shù)和偶數(shù)。

所以B國(guó)人朋友關(guān)系的補(bǔ)圖只有可能是奇數(shù)和偶數(shù)。是一個(gè)二分圖。

補(bǔ)圖的最大獨(dú)立集就是是原圖中的最大團(tuán)。

二分圖上的最大獨(dú)立集 = 點(diǎn)數(shù) - 最大匹配。

?

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

看眾多大佬用時(shí)間戳代替memset。我不會(huì)。

?

#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); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ruthank/p/10604136.html

總結(jié)

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

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。