CSP2019-J，第二轮T4《加工零件》

骗分，dfs，记忆化，正解(奇偶性分析和最短路)

//20pts，利用L=1的数据范围
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N * 2], ne[N * 2], idx;
int n, m, q;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        add(a, b); add(b, a);
    }

    while (q--)
    {
        int x, L;
        scanf("%d%d", &x, &L);

        bool flag = false;
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (j == 1)
            {
                flag = true;
                break;
            }
        }

        if (flag) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

//打暴力，35pts
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N * 2], ne[N * 2], idx;
int n, m, q;
int ans;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int step)
{
    if (u == 1 && step == 0) {ans = 1; return ;}
    if (step <= 0) return ;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j, step - 1);
    }

    return ;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        add(a, b); add(b, a);
    }

    while (q--)
    {
        int a, L;
        scanf("%d%d", &a, &L);

        ans = 0;
        dfs(a, L);

        if (ans) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

//加上记忆化，优秀的80pts
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N * 2], ne[N * 2], idx;
int n, m, q;

int mem[1010][10010];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u, int step)
{
    if (mem[u][step] != -1) return mem[u][step];

    if (u == 1 && step == 0)
        return mem[u][step] = 1;

    if (step <= 0) return 0;

    int ans = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        ans += dfs(j, step - 1);
    }

    if (ans) return mem[u][step] = 1;
    else return mem[u][step] = 0;
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        add(a, b); add(b, a);
    }

    memset(mem, -1, sizeof mem);
    while (q--)
    {
        int a, L;
        scanf("%d%d", &a, &L);

        int ans = dfs(a, L);

        if (ans) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}

//正解,100pts
//分析出，奇偶性问题，一个点，到达1号点的最短路径是奇数的话，那么只要这个点上要的阶段`L >= dist[u][L % 2]`。那么这个点到达1号点的时候，就可以是0
//为什么呢，比如u到1的距离是3，此时，u需要一个阶段5的零件，那么u可以走一步回来一步变成3。那么再利用3步，走到1号点。

//需要求每一个点，奇数长度的最短路径，和偶数长度的最短路径，用dist[u][2]来维护
//最短路的方法有很多，此题边权是1，用bfs实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N * 2], ne[N * 2], idx;
int n, m, q;

int dist[N][2];
bool st[N][2];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs()
{
    for (int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = 2e9;
    dist[1][0] = 0;

    queue<int> q;
    q.push(1);

    while (!q.empty())
    {
        int fr = q.front(); q.pop();

        for (int i = h[fr]; i != -1; i = ne[i])
        {
            int j = e[i];

            if (dist[j][1] > dist[fr][0] + 1)
            {
                dist[j][1] = dist[fr][0] + 1;

                if (!st[j][1])
                {
                    st[j][1] = true;
                    q.push(j);
                }
            }

            if (dist[j][0] > dist[fr][1] + 1)
            {
                dist[j][0] = dist[fr][1] + 1;

                if (!st[j][0])
                {
                    st[j][0] = true;
                    q.push(j);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &q);

    memset(h, -1, sizeof h);
    while (m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        add(a, b); add(b, a);
    }

    bfs();
    if (h[1] == -1) dist[1][0] = 2e9;

    while (q--)
    {
        int a, L;
        scanf("%d%d", &a, &L);

        if (L >= dist[a][L % 2]) printf("Yes\n");
        else printf("No\n");
    }

    return 0;
}