C++14(g++5.4) 解法, 执行用时: 2009ms, 内存消耗: 15352K, 提交时间: 2020-07-23 08:53:14

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,vis[N],cnt[3],res; bitset<N> dp;
vector<int> g[N];
void dfs(int x,int col){
	vis[x]=col;	cnt[col]++;
	for(int to:g[x]) if(!vis[to]) dfs(to,col^3);
}
signed main(){
	cin>>n>>m; dp[0]=1;
	for(int i=1,a,b;i<=m;i++) scanf("%d %d",&a,&b),g[a].push_back(b),g[b].push_back(a);
	for(int i=1;i<=n;i++)	if(!vis[i]){
		cnt[2]=cnt[1]=0;	dfs(i,1);
		dp=(dp<<cnt[1])|(dp<<cnt[2]);
	}
	for(int i=n/2;i<=n;i++) if(dp[i]){res=i;	break;}
	cout<<1LL*res*(n-res)-m;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1834ms, 内存消耗: 15416K, 提交时间: 2020-07-28 15:53:56

#include<bits/stdc++.h>
using namespace std;

bitset<200005>T;
int i,n,m,a,b,V[200005]={0};
vector<int>R[200005];
void DFS(int x)
{
	int i,j;
	for(i=0;i<R[x].size();i++)
	{
		j=R[x][i];
		if(V[j])continue;
		V[j]=V[x]^3,DFS(j);
		if(V[j]==1)a++;
		else b++;
	}
}
int main()
{
    T[0]=1;
	scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
    	scanf("%d%d",&a,&b);
    	R[a].push_back(b),R[b].push_back(a);
	}
	for(i=1;i<=n;i++)
	{
		if(V[i])continue;
		V[i]=a=1,b=0,DFS(i);
		T=(T<<a)|(T<<b);
	}
	for(i=n/2;i<=n;i++)if(T[i])break;
	printf("%lld\n",(long long)i*(n-i)-m);
    return 0;
}