[AtCoder ARC099]E - Independence（图论，二分图染色）

发表于 分类于 ， ，
AtCoder ARC099.E

E - Independence

Time limit : 2sec / Memory limit : 1024MB
Score : 700 points

Problem Statement

In the State of Takahashi in AtCoderian Federation, there are $N$ cities, numbered $1,2,…,N$. $M$ bidirectional roads connect these cities. The $i$-th road connects City $A_i$ and City $B_i$. Every road connects two distinct cities. Also, for any two cities, there is at most one road that directly connects them.

One day, it was decided that the State of Takahashi would be divided into two states, Taka and Hashi. After the division, each city in Takahashi would belong to either Taka or Hashi. It is acceptable for all the cities to belong Taka, or for all the cities to belong Hashi. Here, the following condition should be satisfied:

  • Any two cities in the same state, Taka or Hashi, are directly connected by a road.

Find the minimum possible number of roads whose endpoint cities belong to the same state. If it is impossible to divide the cities into Taka and Hashi so that the condition is satisfied, print -1.

Constraints

$2≤N≤700$
$0≤M≤N(N?1)/2$
$1≤A_i≤N$
$1≤B_i≤N$
$A_i≠B_i$
If $i≠j$, at least one of the following holds: $A_i≠A_j$ and $B_i≠B_j$.
If $i≠j$, at least one of the following holds: $A_i≠B_j$ and $B_i≠A_j$.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1 B_1$
$A_2 B_2$
:
$A_M$ $B_M$

Output

Print the answer.

Samples

Input Output
5 5
1 2
1 3
3 4
3 5
4 5		 4
5 1
1 2		 -1
4 3
1 2
1 3
2 3		 3
10 39
7 2
7 1
5 6
5 8
9 10
2 8
8 7
3 10
10 1
8 10
2 3
7 4
3 9
4 10
3 4
6 1
6 7
9 5
9 7
6 9
9 4
4 6
7 5
8 3
2 5
9 2
10 7
8 6
8 9
7 3
5 3
4 5
6 3
2 10
5 10
4 2
6 2
8 4
10 6
 21

Sample#1:
For example, if the cities 1,2 belong to Taka and the cities 3,4,5 belong to Hashi, the condition is satisfied. Here, the number of roads whose endpoint cities belong to the same state, is 4.

Sample#2:
In this sample, the condition cannot be satisfied regardless of which cities belong to each state.

解题思路

题目大意：将一个图分成两个子图，使得每一个子图都是完全图。
所有不相连的点不能在一个子图里，那么我们就对这些不相连点进行建边，然后二分图染色（即建立了一个原图的补图）
在新图中，同一个连通块中且是相同颜色的点一定在同一个子图里，而不同连通块中不同颜色的点可以放在一起
那么，用一个布尔数组 $s$ 做一个统计，$s[i]$ 表示是否存在大小为 $i$ 的子图，答案取最小情况即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# include<cstdio>
# include<cstring>
# include<algorithm>

using namespace std;

const int N = 705;
const int M = 490005;
int n, m, u, v, ans = 0x7fffffff;
bool g[N][N], s[N], t[N];
int col[N], cnt[2];

void dfs(int x, int c){
	col[x] = c;
	cnt[c == 1]++;
	for(int i = 1; i <= n; i++){
		if(i == x || g[x][i])	continue;
		if(!col[i])	dfs(i, -c);
		else if(col[i] == c){
			puts("-1");
			exit(0);
		}
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i++){
		scanf("%d%d", &u, &v);
		g[u][v] = g[v][u] = 1;
	}
	s[0] = 1;
	for(int i = 1; i <= n; i++){
		if(col[i])	continue;
		cnt[0] = cnt[1] = 0;
		dfs(i, 1);
		memset(t, 0, sizeof t);
		for(int j = 0; j <= n; j++){
			t[j+cnt[0]] |= s[j];
			t[j+cnt[1]] |= s[j];
		}
		for(int j = 0; j <= n; j++)
			s[j] = t[j];
	}
	for(int i = 0; i <= n; i++)
		if(s[i])
			ans = min(ans, i*(i-1)/2 + (n-i)*(n-i-1)/2);
	printf("%d\n", ans);
	return 0;
}