首先就是求联通块，每个联通块里记录两个部分的元素个数
目标是使一边的体积接近n/2
那么每个联通块作为一组，进行分组背包，dp[i]表示体积i是否可以被凑出来，可行性背包是可以用bitset优化的
最后找最接近n/2的体积即可
#include<bits/stdc++.h> using namespace std; #define maxn 10005 #define maxm 100005 int n,m,cnt,vis[maxn]; struct Node{int a,b;}p[maxn]; vector<int>G[maxn]; void dfs(int u,int c){ vis[u]=1; if(c==0)p[cnt].a++; else p[cnt].b++; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(vis[v])continue; dfs(v,!c); } } int main(){ int t;cin>>t; while(t--){ memset(p,0,sizeof p); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)G[i].clear(); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } //求出联通块 cnt=0; memset(vis,0,sizeof vis); for(int i=1;i<=n;i++) if(!vis[i]){ ++cnt; dfs(i,0); } bitset<10005>dp; dp.reset(); dp[0]=1; for(int i=1;i<=cnt;i++)//从每组里找一个 dp=(dp<<p[i].a)|(dp<<p[i].b); long long ans=0; for(int i=1;i<n;i++) if(dp[i]) ans=max(ans,(long long)(n-i)*i-m); cout<<ans<<'\n'; } return 0; }
转载于:https://www.cnblogs.com/zsben991126/p/11181878.html
