AcWing 323. 战略游戏(格式化输入)
原题链接
简单
作者:
宇小苏
,
2020-03-30 15:16:24
,
所有人可见
,
阅读 774
import java.util.*;
class Main{
private static int[][] f;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int n = sc.nextInt();
createAdj(n);
f = new int[n][2];
boolean[] st = new boolean[n];
for(int i = 0; i < n; i++){
String p = sc.next();
int l = p.indexOf('(');
int r = p.indexOf(')');
int s = Integer.parseInt(p.substring(0, l-1));
int m = Integer.parseInt(p.substring(l+1, r));
for(int j = 0; j < m; j++){
int t = sc.nextInt();
add(s, t);
st[t] = true;
}
}
int root = 0;
while(st[root]) root++;
dfs(root);
System.out.println(Math.min(f[root][0], f[root][1]));
}
}
private static void dfs(int u){
f[u][1] += 1;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
dfs(j);
f[u][0] += f[j][1];
f[u][1] += Math.min(f[j][0], f[j][1]);
}
}
private static int[] h, e, ne;
private static int idx;
private static void createAdj(int n){
h = new int[n+1];
e = new int[n+1];
ne = new int[n+1];
Arrays.fill(h, -1);
idx = 0;
}
private static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}
Memory Limit Exceeded
java刷这题真苦