题解：P17235 [Algo Beat Contest 017 D] 图博弈

gggshsh · 2026-08-10 21:36:36 · 题解

其实题目等价于找一个棒棒糖型的生成子图，意思是

那么有连边规则

• v_{i+1}\to v_{i},\, i=0,\cdots,t-1
• u_{i}\to u_{i+1}, u_{s}=u_0,\;i=0,\cdots,s-1
• 在已知的这些点中，没有其他的连边。

然后记 S=\{v_0,\cdots,v_t,u_1,\cdots,u_{s-1}\}，那么对于图的其他边，约定都是从 S 的点指向非 S 的点；如果2个点都不属于 S，随意。

那么只有 S 中的点可以指向 k，然后很容易得出有且仅有一个点走 n 步到达了 k。

证明是显然的，因为题意就是有且仅有一个点 v，可以走 n 步通向 k，每一步不能走上一步走过的。那么必须要求 k 所在（无向图）有环，没有环就是树，树肯定走不了回头路，那么n-1 步之后无路可走。

如果有环，就一定可以生成这个棒棒糖。这个可以用极端原理不停减小规模。

至于怎么找棒棒糖，只要从 k 开始广搜，再找最近的不是 BFS 树边就可以了。

下面是代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e3 + 100;
int n, m, k;
struct Edge
{
    int to, val;
    Edge(int t = 0, int v = 0): to(t), val(v){}
};
Edge e[N << 2];

int pre[N], dis[N];
vector<int> G[N];
void init()
{
    for(int i=0;i<=n;i++) G[i].clear();
}
void solve()
{
    cin>>n>>m>>k;
    init();
    int u, v;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        e[2*i] = Edge(v, 0);
        e[2*i+1] = Edge(u, 0);
        G[u].push_back(2*i);
        G[v].push_back(2*i+1);
    }
    memset(pre, 0, sizeof(pre));
    memset(dis, 0, sizeof(dis));
    pre[k] = -1;
    // BFS
    queue<int> Q;
    Q.push(k);
    int l = 0, r = 0, lr = 0;
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int idx: G[u])
        {
            int v = e[idx].to;
            if(pre[v] && v != e[pre[u]^1].to)
            {
                l = u, r = v, lr = idx; // lr 是 l 引出的边的序号
                break;
            }
            else if(! pre[v])
            {
                dis[v] = dis[u] + 1;
                pre[v] = idx;
                Q.push(v);
            }
        }
        if(l && r) break;
    }
    if(l == 0 || r == 0)
    {
        cout << "No\n";
        return ;
    }
    // 现在的任务就是把这个子图搭回来
    cout << "Yes\n";
    // cout << "--- " << l << " " << r << " ---\n";
    vector<int> chain;
    e[lr].val = 1;
    e[lr ^ 1].val = 0;
    if(dis[r] > dis[l])
    {
        int idx = pre[r];
        e[idx].val = 0;
        e[idx ^ 1].val = 1;
        chain.push_back(r);
        r = e[idx ^ 1].to;
    }
    while(l != r)
    {
        int idx1 = pre[l], idx2 = pre[r];
        e[idx1].val = 1, e[idx1 ^ 1].val = 0;
        e[idx2].val = 0, e[idx2 ^ 1].val = 1;
        chain.push_back(l);
        chain.push_back(r);
        l = e[idx1 ^ 1].to;
        r = e[idx2 ^ 1].to;
    }
    while(l != k)
    {
        int idx = pre[l];
        e[idx].val = 0, e[idx ^ 1].val = 1;
        chain.push_back(l);
        l = e[idx ^ 1].to;
    }
    chain.push_back(k);
    for(int u: chain)
    {
        for(int idx: G[u])
        {
            if(e[idx].val || e[idx ^ 1].val)
                continue;
            e[idx].val = 1;
            e[idx ^ 1].val = 0;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(e[2*i].val) cout << 0;
        else cout << 1;
    }
    cout << "\n";
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}