bzoj 3722: PA2014 Final Budowa

3722: PA2014 Final Budowa

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 303 Solved: 108
[Submit][Status][Discuss]

Description

Fancy爷宣布XJOI群将要选举下一任群主。候选人有两名，分别是XYW和吉丽。
共有n个人（从1~n编号）参加这次投票。他们之间形成了一个树结构，根结点（1号结点）为Fancy。树上的结点有两种身份：专家（叶子结点）或领导（非叶子结点）。每位专家都有自己的选择——支持XYW和吉丽之中的一个；每位领导都有若干个下属（儿子结点），领导的选择决定于下属中人数较多的那一方，下属的数目保证为奇数，从而不会出现平局状况。最后，Fancy的选择即为选举结果。
吉丽和XYW知道，目前仍有一些专家处于犹豫未决的状态，只要前去游说，就可获得他的支持。但是由于精力不够，每人每天只能选择游说1名专家；XYW起床更早，他比吉丽先进行游说。这样两人交替进行，直到每位专家都有了确定的选择。请问XYW是否有策略保证自己赢得选举胜利？

Input

第一行一个整数n(2<=n<=1000)，表示人数。
接下来有n行。第i行中，第一个数为c[i](-2<=c[i]<=n0)。如果c[i]<=0，则i是专家，-2表示其支持XYW，-1表示支持吉丽，0表示仍在犹豫；如果c[i]>0，则c[i]为奇数，表示i是领导，其后c[i]个整数为i的下属。
（数据保证为树结构，即除了根节点1以外每个结点有且仅有一个上级）

Output

若XYW无法保证胜利，仅输出一行NIE。
否则，输出第一行包含TAK和一个非负整数d；输出第二行包含d个整数，按升序排列，表示XYW在必胜策略下，第一天可以选择游说的专家的编号。（如果不存在犹豫不决的专家，且XYW获得胜利的情况下，则d=0，第二行为空行）

Sample Input

4
3 2 3 4
-2
0
-1

Sample Output

TAK 1
3

/*

    支持先手为-2，后手为-1，犹豫为0

    从叶子开始往上考虑

    如果一个人有偶数个0孩子，相当于没有0孩子，可以把他变成-2/-1

    如果一个人有奇数个0孩子，且剩余孩子中-2=-1，那么这个人相当于0，否则也可以决定他的决策

    一直缩上根，如果根是-2或0则先手必胜否则必败

    然后是输出方案

    根是-2时显然先手可以任选一个0开始

    根是0时，从根往下走，当一个孩子y的状态是0或者y是-1但是y中-2+0的数量=-1的数量，先手就有可能在y中取，往下dfs一遍就好了

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 1010

#define INF 0x7fffffff

using namespace std;

int n,num,tp;

int c[maxn],col[maxn],a[maxn],head[maxn];

struct node{

    int to,pre;

}e[maxn];

void Insert(int from,int to){

    e[++num].to=to;

    e[num].pre=head[from];

    head[from]=num;

}

int dfs(int x){

    if(c[x]<=)return col[x];

    int sum=;

    for(int i=head[x];i;i=e[i].pre)sum+=dfs(e[i].to);

    if(sum>)return ;

    if(sum<)return -;

    return ;

}

int main(){

    scanf("%d",&n);int v;

    for(int i=;i<=n;i++){

        scanf("%d",&c[i]);

        for(int j=;j<=c[i];j++)scanf("%d",&v),Insert(i,v);

        if(c[i]==-)col[i]=;

        if(c[i]==-)col[i]=-;

        if(c[i]==)col[i]=;

        if(c[i]>)col[i]=INF;

    }

    if(dfs()==-){puts("NIE");return ;}

    for(int i=;i<=n;i++)

        if(col[i]==){

            col[i]=;

            if(dfs())a[++tp]=i;

            col[i]=;

        }

    printf("TAK %d\n",tp);

    for(int i=;i<=tp;i++)printf(i!=tp?"%d ":"%d",a[i]);

    return ;

}

巴特西