Created
June 16, 2017 11:15
-
-
Save takageymt/85ccc57cc00c88617e78bccfb8de48fc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
#define int long long | |
#define all(v) (v).begin(), (v).end() | |
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__) | |
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++) | |
#define rep(i, n) reps(i, 0, n) | |
template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;} | |
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;} | |
typedef pair<int, int> Pi; | |
typedef tuple<int, int, int> Ti; | |
typedef vector<int> vint; | |
const int inf = 1LL << 55; | |
const int mod = 1e9 + 7; | |
int V, E; | |
vector< vector<int> > graph; | |
int color[100010]; | |
Pi dfs(int u, int c) { | |
Pi res(0, 0); | |
color[u] = c; | |
if(c == 1) res.first++; | |
else res.second++; | |
for(int v : graph[u]) { | |
if(color[v] == c) return Pi(-1, -1); | |
if(color[v] == 0) { | |
Pi tmp = dfs(v, -c); | |
if(tmp.first < 0) return Pi(-1, -1); | |
res.first += tmp.first; | |
res.second += tmp.second; | |
} | |
} | |
return res; | |
} | |
map<int, int> mp; | |
int dp[100010]; | |
signed main() | |
{ | |
cin.tie(0); | |
ios_base::sync_with_stdio(0); | |
cout << fixed << setprecision(12); | |
cin >> V >> E; | |
resz(graph, V); | |
rep(i, E) { | |
int a, b; | |
cin >> a >> b; | |
--a, --b; | |
graph[a].push_back(b); | |
graph[b].push_back(a); | |
} | |
mp.clear(); | |
memset(color, 0, sizeof(color)); | |
int v = 0; | |
rep(i, V) { | |
if(color[i] != 0) continue; | |
Pi p = dfs(i, 1); | |
int a = min(p.first, p.second); | |
int b = max(p.first, p.second); | |
if(a < 0) { | |
cout << -1 << endl; | |
return 0; | |
} | |
mp[b-a]++; | |
v += a; | |
} | |
memset(dp, -1, sizeof(dp)); | |
dp[0] = 0; | |
for(auto p : mp) { | |
int plus = p.first, num = p.second; | |
rep(i, V+1) { | |
if(dp[i] >= 0) dp[i] = num; | |
else if(i < plus || dp[i-plus] <= 0) dp[i] = -1; | |
else dp[i] = dp[i-plus]-1; | |
} | |
} | |
int ans = 0; | |
rep(i, V+1) if(dp[i] >= 0) chmax(ans, (v+i)*(V-v-i)); | |
cout << ans-E << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment