C++YJC最近写了一篇关于游戏的论文。CJY看他那么喜欢游戏决定出一道题考考他。CJY给出了一种两个人玩的游戏。定义游戏规则如下：给一张n个点m条边的有向无环图每条边有颜色c在图上放了q颗石子每颗石子在一个点上。每次操作时选择一个有出边且点上有石子的点x从点上取走一颗石子然后选择一个颜色集合S对于每条满足颜色e∈S的出边i在边i的终点上放上一颗石子。双方轮流操作不能操作者负。CJY问YJC是先手

【解题思路】 这是一个博弈问题，可以使用动态规划来解决。先定义一个状态dp[i]，表示当前状态为i时，先手是否必胜。然后根据题意，可以得到状态转移方程：dp[i] = !dp[j]，其中j是所有满足条件的下一个状态。最终，如果dp[0]为真，则先手必胜，否则先手不必胜。

【伪代码】

1. 构建一个有向图，用邻接表来表示图的边关系。
2. 初始化状态dp[]为false，表示先手不必胜。
3. 根据输入的边信息，构建邻接表。
4. 根据输入的石子信息，初始化状态dp[]，将石子所在的点置为true。
5. 从状态dp[n-1]开始，对每个状态进行判断：
   • 如果当前状态为true，直接跳过。
   • 否则，对于每个出边，如果有石子且下一个状态为false，则当前状态为true。
6. 返回dp[0]的结果。

【代码实现】

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1005;
const int MAXM = 10005;

struct Edge {
    int to, color;
    Edge(int t, int c) : to(t), color(c) {}
};

vector<Edge> graph[MAXN];
bool dp[MAXN];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int s, t, c;
        cin >> s >> t >> c;
        graph[s].push_back(Edge(t, c));
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int p;
        cin >> p;
        dp[p] = true;
    }

    for (int i = n - 1; i >= 0; i--) {
        if (dp[i]) {
            continue;
        }
        for (int j = 0; j < graph[i].size(); j++) {
            int next = graph[i][j].to;
            int color = graph[i][j].color;
            if (dp[next] == false && dp[i] == false) {
                dp[i] = true;
                break;
            }
        }
    }

    cout << dp[0] << endl;

    return 0;
}

【复杂度分析】 时间复杂度：O(n+m)，其中n为点数，m为边数。需要遍历所有的边和点。

空间复杂度：O(n)，需要使用一个数组来存储状态