The Enemy of My Enemy is My Friend
Time limit8sMemory limit512 MB
Given a country adjacency graph, pick a maximum-weight set of countries including our own, where no two chosen countries are adjacent or share a common neighbor.
- Level
Medium7 of 10
- Topics
- Graph, Brute force, Backtracking, Greedy
- Solved
- No attempts yet
Problem
The year is XXXX. It is an age of war.
Conflicts between neighboring countries over land and resources break out everywhere, and the future of the world is very uncertain. Amid this, one country decides to survive the turbulent age by forming military alliances with various countries. A military alliance must satisfy the following conditions.
- It cannot ally with a country that neighbors its own country.
- It cannot ally with a country that neighbors an allied country.
However, each country has a different military strength. It may be more advantageous to ally with one very strong country than with several weak ones. Here we want to find a way to form a military alliance that maximizes the sum of the military strengths of the countries in the alliance.
Input
The input consists of multiple datasets. The format of each dataset is as follows.
N
A1 B1 C1 D1,1 ... D1,C1
A2 B2 C2 D2,1 ... D2,C2
...
AN BN CN DN,1 ... DN,CN
In each dataset, the first line gives the number of countries N (1 ≤ N ≤ 40), and lines 2 through N+1 give the details of the countries. The details of a country are the country name Ai, the military strength Bi, the number of neighboring countries Ci, and the list of neighboring countries Di,1 ... Di,Ci. Our own country is the first country A1.
All country names Ai are distinct and consist of 1 to 16 uppercase or lowercase letters. The military strength Bi is an integer from 0 to 1000. Each country name Di,j in the neighbor list matches one of A1 through AN. The neighbor list of a country never contains the country itself, and the same country name never appears twice in it. Inputs in which the neighbor relation is not symmetric do not occur.
The end of the input is indicated by a line consisting of only 0.
Output
For each test case, output on one line the sum of military strengths when an alliance is formed to maximize the sum of military strengths including our own country.