Skip to content

Instantly share code, notes, and snippets.

@hiroshi-cl
Created June 25, 2013 07:01
Show Gist options
  • Save hiroshi-cl/5856526 to your computer and use it in GitHub Desktop.
Save hiroshi-cl/5856526 to your computer and use it in GitHub Desktop.
ACM-ICPC 模擬国内予選 2012 E: 敵の敵は味方 [Licence: NYSL Version 0.9982]
import java.util.*;
public class Main {
private static final Scanner sc = new Scanner(System.in);
public static void main(String... args) {
while (sc.hasNext()) {
final int N = sc.nextInt();
if (N == 0)
break;
solve(N);
}
}
private static void solve(final int N) {
sc.nextLine();
final String[] lines = new String[N];
for (int i = 0; i < N; i++)
lines[i] = sc.nextLine();
final Map<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < N; i++)
map.put(lines[i].split(" ", 2)[0], i);
final int[] powers = new int[N];
final long[] masks = new long[N];
for (int i = 0; i < N; i++) {
final String[] ss = lines[i].split(" ");
powers[i] = Integer.parseInt(ss[1]);
masks[i] = 1L << i;
final int M = Integer.parseInt(ss[2]);
for (int j = 0; j < M; j++)
masks[i] |= 1L << map.get(ss[3 + j]);
}
System.out.println(powers[0] + dfs(N, 1, masks[0], powers, masks));
}
private static int dfs(final int N, final int c, final long used, final int[] powers, final long[] masks) {
if (c == N)
return 0;
int ret = 0;
if ((used & 1L << c) == 0) {
ret = dfs(N, c + 1, used | masks[c], powers, masks) + powers[c];
long rem = 0L;
for (int k = c + 1; k < N; k++)
if ((used & 1L << k) == 0)
rem |= masks[k];
if ((rem & 1L << c) == 0)
return ret;
}
return Math.max(ret, dfs(N, c + 1, used, powers, masks));
}
private static void debug(Object... os) {
System.err.println(Arrays.deepToString(os));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment