Submission #3637457

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll mod = 1e9+7;
ll inf=1e18;

/*
AC
補グラフを考え，２部グラフになってるかを確認する．２部グラフになってたら，連結成分を交互に２色に塗り分け，高国と橋国のどちらに振り分けるか決める．
作りうる全ての数を作るdpで片方の国の大きさを列挙し，それをc1とすると，答えは(c1,2)+(c2,2)の最小値（(a,b)は二項係数）
*/

bool ok=true;
ll n,m,d[710][710],visit[710]={},color[710]={},dp[710]={},smallest=1e9;
vector<int> c1,c2;

int main(void){
	rep(i,710)rep(j,710)d[i][j]=0;
	cin>>n>>m;
	rep(i,m){
		ll a,b;
		cin>>a>>b;
		d[a-1][b-1]=1;
		d[b-1][a-1]=1;
	}
	rep(i,n)rep(j,n){
		if(i==j)continue;//補グラフでも自己辺は認めない
		d[i][j]=1-d[i][j];
	}
	//孤立点があった時も大丈夫（後述）
	rep(i,n){
		if(visit[i]==0){
			int a[3]={};
			a[1]++;
			visit[i]=1;
			color[i]=1;
			queue<mp> Q;
			Q.push({i,1});
			while(!Q.empty()){
				mp p=Q.front();Q.pop();
				rep(j,n){
					if(d[p.first][j]==1){
						if(visit[j]==0){
							visit[j]=1;
							color[j]=3-p.second;
							a[color[j]]++;
							Q.push({j,color[j]});
						}else{
							if(color[j]!=3-color[p.first]){
								ok=false;
								break;
							}
						}
					}
				}
			}
			//孤立点でも1,0になり，ほかと同様に扱えるので行ける．
			c1.push_back(a[1]);
			c2.push_back(a[2]);
		}
	}
	//作りうる全ての数を作るdp
	dp[0]=1;
	rep(i,c1.size()){
		int dp2[710]={};
		rep(j,710){
			if(dp[j]==1){
				if(j+c1[i]<710)dp2[j+c1[i]]=1;
				if(j+c2[i]<710)dp2[j+c2[i]]=1;
			}
		}
		rep(j,710)dp[j]=dp2[j];
	}
	rep(i,710){
		if(dp[i]==1){
			smallest=min(smallest,i*(i-1)/2+(n-i)*(n-i-1)/2);//ここを最小にする
		}
	}
	cout<<(ok?smallest:-1)<<endl;
	return 0;
}

Submission Info

Judge Result