傳送門

解題思路

直接跑最大團(tuán)洛谷上能得70分，驚了。說說正解，首先A國的必須xor后mod2余1，就相當(dāng)于兩個人必須是1奇1偶，所以A國的人只能選0,1,2個，我們可以暴力枚舉選誰。繼續(xù)考慮B國，現(xiàn)在的問題實(shí)際上就簡化為了在B國中選出一個最大團(tuán)，這個團(tuán)也必須和A國所選出的人是朋友，又因?yàn)樽畲髨F(tuán)=總點(diǎn)數(shù)-補(bǔ)圖的最大匹配，補(bǔ)圖就是將原來連著的邊斷了，原來沒連的邊連上，而進(jìn)一步可以發(fā)現(xiàn)其實(shí)B國的補(bǔ)圖是一個二分圖，左部點(diǎn)是%2余1的，右部點(diǎn)是%2余0的，如果它們或起來有偶數(shù)個1就可以連邊，然后就是二分圖中求一個最大匹配，我用的匈牙利卡了過去。。

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib>using namespace std; const int MAXN = 3205; const int MAXM = 1500*1500+5;inline int rd(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return f?x:-x; }int T,A,B,M,head[MAXM],cnt,ans; int to[MAXM],nxt[MAXM],now; int a[MAXN],b[MAXN],e[MAXN][MAXN]; int num,t,vis[MAXN],flag[MAXN],match[MAXN];inline void add(int bg,int ed){to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt; }inline bool dfs(int x){for(register int i=head[x];i;i=nxt[i]){int u=to[i];if(vis[u]!=num && flag[u]==t){vis[u]=num;if(!match[u] || dfs(match[u])){match[u]=x;return true;}}}return false; }int main(){ // T=rd(); A=rd();B=rd();M=rd();for(register int i=1;i<=A;i++) a[i]=rd();for(register int i=1;i<=B;i++) b[i]=rd();for(register int i=1;i<=B;i++)if((b[i]&1))for(register int j=1;j<=B;j++) if(!(b[j]&1) && !((__builtin_popcount((b[i]|b[j])))&1)) add(i,j);for(register int i=1;i<=M;i++) {int x=rd(),y=rd();e[x][y+A]=e[y+A][x]=1;}for(register int i=1;i<=B;i++)if((b[i]&1)){num++;if(dfs(i)) ans++;}ans=B-ans;for(register int i=1;i<=A;i++){t++;int sum=0;now=0;memset(match,0,sizeof(match));for(register int j=1;j<=B;j++)if(e[i][j+A]) flag[j]=t,now++; for(register int j=1;j<=B;j++)if(flag[j]==t && (b[j]&1)) {num++;if(dfs(j)) sum++; }ans=max(ans,now-sum+1);}for(register int i=1;i<=A;i++)for(register int j=i+1;j<=A;j++)if((a[i]^a[j])&1){memset(match,0,sizeof(match));t++;int sum=0;now=0;for(register int k=1;k<=B;k++)if(e[i][k+A] && e[j][k+A]) flag[k]=t,now++;for(register int k=1;k<=B;k++)if(flag[k]==t && (b[k]&1)) {num++;if(dfs(k)) sum++;}ans=max(ans,now-sum+2);}cout<<ans<<endl;return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的BZOJ 2744: [HEOI2012]朋友圈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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