有大佬嘛求调
  • 板块题目总版
  • 楼主sundyLIUXY
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/28 21:04
  • 上次更新2023/10/23 14:25:15
查看原帖
有大佬嘛求调
706737
sundyLIUXY楼主2023/5/28 21:04

https://www.luogu.com.cn/problem/AT_abc299_e 求调qwq,广搜,不知哪里挂了

#include <bits/stdc++.h>
using namespace std;
#define int long long

long long n, m, k, h[4010], idx, p[4010], d[4010];
bool b[4010], b2[4010], nos;
queue<int> q;
struct EDGE
{
    int to, ne;
} edge[8010];

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

signed main()
{
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%lld%lld", &u, &v);
        add(u, v), add(v, u);
    }
    scanf("%lld", &k);
    for(int i = 1; i <= k; i++)
    {
        while(q.size()) q.pop();
        scanf("%lld%lld", &p[i], &d[i]), q.push(p[i]);
        for(int j = 1; j <= d[i]; j++)
        {
            int now = q.size();
            while(now--)
            {
                int u = q.front();
                //cout << "#" << u << "# ";
                q.pop(), b[u] = 1;
                for(int l = h[u]; l; l = edge[l].ne)
                {
                    int v = edge[l].to;
                    //cout << "->1 " << v << ' ';
                    if(!b[v]) q.push(v);
                }
                //cout << endl;
            }
        }
    }
    //for(int i = 1; i <= n; i++) cout << b[i];
    //cout << endl;
    for(int i = 1; i <= k; i++)
    {
        while(q.size()) q.pop();
        q.push(p[i]);
        for(int j = 1; j <= d[i]; j++)
        {
            int now = q.size();
            while(now--)
            {
                int u = q.front();
                //cout << "#" << u << "# ";
                q.pop(), b2[u] = 1;
                for(int l = h[u]; l; l = edge[l].ne)
                {
                    int v = edge[l].to;
                    if(!b2[v]) q.push(v);
                }
            }
        }
        bool ns = 0;
        while(q.size())
        {
            if(!b[q.front()]) ns = 1;
            //cout << q.front() << ' ';
            q.pop();
        }
        if(!ns) nos = 1;
        //cout << nos << endl;
    }
    if(nos) printf("No");
    else 
    {
        printf("Yes\n");
        for(int i = 1; i <= n; i++) printf("%d", !b[i]);
    }

    return 0;
}

2023/5/28 21:04
加载中...