题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5005

题目巨长，所以不贴题目了，直接说大意（话说大意也不短。。。。）。

题目大意：有两个人A和X，给一个有向无环图（DAG），每一个出度为0的节点（下面称这些节点为“叶子节点”）有两个权值x和y（所有的x，y都不一样，这点非常重要）。除了叶子节点，其他所有节点都都由A或X控制。如果当前位置在非叶子节点U，如果U被A控制，则A可以选择接下来转移的点V（满足U->V存在一条有向边），反之亦然。如果到达了叶子节点，则A得x分，X得y分。现在A和X玩一个游戏，从1节点出发，每个人都希望自己的得分最大（重点）。现在X有一种特殊的操作，他可以告诉A他的策略，所谓策略就是在每个X所控制的点，X会选择的转移节点。（X一定会按照策略行动,至少A是这么认为的)。现在问两个问题：

1.X不使用特殊操作时，所能得到的最大分数。

2.X使用特殊操作时，所能得到的最大分数。

思路：第一问无比简单，因为是DAG，设dp[i][0]，dp[i][1]分别表示在i节点A和X所能得到的最大得分。然后分叶子节点，A控制的节点，X控制节点三种情况进行转移即可，应该都会。

关键是第二问，乍一看来好像告诉对方自己的策略是一种愚蠢的行为，并不会对最后的得分有多少改进，但是考虑到双方的目标都是使得自己的得分最大，而不是要使对方的得分最小或是自己和对方的差值最大（这点很重要）。所以X可以采用一种策略使得自己的得分比不使用特殊操作更大，具体看样例即可。至于怎么制定自己的策略，直接制定貌似很难（我不会而已），我们可以换一种思路，因为A，X最后的得分一定是一个叶子节点的权值，那么我们可以按照y值从大到小依次枚举，枚举该叶子节点是否可以由B的某种策略到达，如果到达了显然答案就是当且枚举的叶子节点的y权值了（因为是从大到小枚举）。

现在考虑一个叶子节点，设为V。V是否可以到达不仅取决于X，还取决于A的心情，X当然想要到达V，因为V是目前为止的最好选择，前面比V好的都无法到达（否则也不会枚举V了。。。），现在问题就是A是否会选择也到达V。设V的x权值为Limit，那么如果A可以到达更好的叶子节点使得其权值大于Limit,A才不会选择V呢，那么现在的关键问题是要保证A无法到达比V还优（对A来说）的叶子节点。我们来定义一个节点是“好的”当且仅当从这个节点出发，无论A怎么转移，X都能使用策略使得A无法到达一个比V更优的叶子节点。否则这个节点称为“坏的”。那么我们可以根据dp来算出每个节点是“好的”还是“坏的”。

对于叶子节点，如果其x值大于Limit，则它是"坏的"，否则它是"好的"。

对于非叶子节点，（1）如果它被A控制，且它的后继节点有一个是坏的，则说明A可以到达一个比V更优的节点，说明它是”坏的“。否则A无论如何也只能到达”好的"点,则它是“好的”。

（2）如果它被X控制，且它的后继节点中有一个是“好的”，则说明X可以选择转移到“好的”节点中去，所以它是“好的”，否则它是“坏的”。

那么如果1号节点是"坏的"，表示A可以选择一个比V更优的叶子节点，则不能到达V。如果1号节点是“好的”节点，也只能说明X可以用策略使得A无法到达一个比V更优的叶子节点，并不能说明可以到达V。

V能到达的依据为：如果存在一跳仅由“好的”点组成的简单路径从1号节点到V，那么说明V可达。

那么这个时候只要从1号节点dfs一遍即可判断。

现在说明一下为什么这样能到达V。因为1号节点是“好的”，说明对于A来说，V是对他来说最优的叶子节点，（其他更优节点已被标为“坏的”，而X是不会让A走到“坏的”节点上去的），同时对X来说，V也是最优节点（前面说过了），那么现在又有一条从1号节点到V的仅由好的节点组成的路径。那么V可达。那么这道题就做完了。

最后说一下X的策略，由上面的分析，可知，如果V可达，X只要告诉A：“对于我所有控制的点，我必然会转移到一个好的后继节点(至于是哪个根据V的选择而定)。即可，这样的话，A只能选择V节点为最优节点了。终于写完了。。。。。

代码如下：（没优化版本，写得巨长。。。）

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define maxn 210
using namespace std;
struct edge
{
    int to,next;
}e[maxn];
int box[maxn],cnt;
void init()
{
    memset(box,-1,sizeof(box));
    cnt=0;
}
void add(int from,int to)
{
    e[cnt].to=to;
    e[cnt].next=box[from];
    box[from]=cnt++;
}
int bel[maxn],A[maxn],B[maxn];
struct node
{
    int id,A,B;
    node(){}
    node(int x,int y,int z)
    {
        id=x,A=y,B=z;
    }
};
bool cmp(const node &x,const node &y)
{
    return x.B>y.B;
}
vector<node> vec;
int dp[maxn][2],vis[maxn];
void dfs1(int now)
{
    if(dp[now][0]!=-1)
    return;
    if(bel[now]==-1)//不属于任何人
    {
        dp[now][0]=A[now];
        dp[now][1]=B[now];
        return;
    }
    for(int t=box[now];t+1;t=e[t].next)
    {
        int v=e[t].to;
        dfs1(v);
        if(bel[now]==0)//属于A
        {
            if(dp[v][0]>dp[now][0])
            {
                dp[now][0]=dp[v][0];
                dp[now][1]=dp[v][1];
            }
        }
        else//属于X
        {
            if(dp[v][1]>dp[now][1])
            {
                dp[now][0]=dp[v][0];
                dp[now][1]=dp[v][1];
            }
        }
    }
}
int dfs(int now,int limit)
{
    if(vis[now]!=-1)
    return vis[now];
    if(bel[now]==-1)
    {
        if(A[now]>limit)
        return vis[now]=0;
        return vis[now]=1;
    }
    if(bel[now]==0)
    {
        for(int t=box[now];t+1;t=e[t].next)
        {
            int v=e[t].to;
            dfs(v,limit);
        }
        for(int t=box[now];t+1;t=e[t].next)
        {
            int v=e[t].to;
            if(!vis[v])
            return vis[now]=0;
        }
        return vis[now]=1;
    }
    else
    {
        for(int t=box[now];t+1;t=e[t].next)
        {
            int v=e[t].to;
            dfs(v,limit);
        }
        for(int t=box[now];t+1;t=e[t].next)
        {
            int v=e[t].to;
            if(vis[v])
            {
                return vis[now]=1;
            }
        }
        return vis[now]=0;
    }
}
bool dfs2(int now,int limit)
{
    if(bel[now]==-1)
    {
        if(A[now]==limit)
        return true;
        return false;
    }
    for(int t=box[now];t+1;t=e[t].next)
    {
        int v=e[t].to;
        if(vis[v]==1)
        {
            if(dfs2(v,limit))
            return true;
        }
    }
    return false;
}
int main()
{
    //freopen("dd.txt","r",stdin);
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        int n;
        scanf("%d",&n);
        init();
        vec.clear();
        memset(bel,-1,sizeof(bel));
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            int num;
            scanf("%d",&num);
            if(num==0)
            {
                scanf("%d%d",&A[i],&B[i]);
                vec.push_back(node(i,A[i],B[i]));
            }
            else
            {
                int x;
                for(int j=0;j<num;j++){
                    scanf("%d",&x);
                    add(i,x);
                }
                char typ[10];
                scanf("%s",typ);
                if(typ[0]=='A')
                bel[i]=0;
                else
                bel[i]=1;
            }
        }
        dfs1(1);
        int ans1=dp[1][1];
        printf("%d ",ans1);
        sort(vec.begin(),vec.end(),cmp);
        int ans2=-1;
        for(int i=0;i<(int)vec.size();i++)
        {
            memset(vis,-1,sizeof(vis));
            int now=vec[i].id;
            if(dp[now][0]==-1)
            continue;
            if(dfs(1,vec[i].A))
            {
                if(dfs2(1,vec[i].A))
                {
                    ans2=vec[i].B;
                    break;
                }
            }
        }
        printf("%d\n",ans2);
    }
    return 0;
}

hdu 5005 Compromise (2014 ACMICPC regional Anshan Site 1009)