Special Economic Zone
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Fox Ciel is the queen of Fox Kingdom. There are n cities and m bidirectional roads between them. Two cities are called neighbours if there is a road between them. She wants to select some of the cities to establish as SEZs (Special Economic Zones). Also she must ensure that no two neighbouring cities are SEZ's as it will hinders growth of both the cities.
People in SEZ will be happy due to huge employments opportunities. People living in a non SEZ city and having at least one neighbouring SEZ city will be unhappy due to jealousy.
Let x be the number of happy cities and y be the number of unhappy cities. Ciel's goal is to maximize the value of (x - y). Please output the maximal value of (x - y).
- There will be exactly one test case in a single test file.
- The first line will contain two space separated integers n and m.
- In the next m lines, each line will contain two space integers u, v denoting that there is a road between city u and v.
- 1 ≤ n ≤ 200
- 1 ≤ m ≤ 400
- There won't be any self-loop or repeated edges.
- 5%: n <= 20
- 95%: no other constraints
Print a single integer corresponding to the maximal value of (x - y).
Input: 6 5 1 2 2 3 4 5 5 6 6 4 Output: 1
Ciel will select city 1 and 3 as SEZ. So x = 2 (city 1 and 3), y = 1 (city 2), x - y = 1.
|Tags||cgy4ever, lp, may15, medium-hard|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.