Gym 101128A Promotions（思维 + dfs）题解

题意：给一有向图，如果A指向B，则A是B的上级。一直i要升职那么他的上级必须都升职。现在给你一个升职人数的区间[a, b]，问你升职a人时几个人必被升职，b时几个人必升职，b时几个人没有可能被升职。

思路：打比赛的时候一直想怎么做才能一个dfs直接打出一个节点的所有子节点数，发现总是弄不出来。结果这道题直接暴力搜索每个点的儿子就行了。

我们正向建边求出所有下级（包括自己）son，反向建边求出所有上级（包括自己）fa，那么显然如果n - son < a时，也就是说剩下的人都升职都不够a人，那我肯定升职。如果fa > b时，显然我要升职至少要fa，但是b < fa，那我就不可能升职。

这题也太暴力了，这谁下得了手。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long longll;

using namespace std;

const int maxn = 5000 + 10;

const int MOD = 1e9 + 7;

const int INF = 0x3f3f3f3f;

vector<int> G[maxn], g[maxn];

int son[maxn], fa[maxn];

bool vis[maxn];

int dfs1(int u){

    vis[u] = true;

    int ret = 1;

    for(int i = 0; i < G[u].size(); i++){

        int v = G[u][i];

        if(!vis[v])

            ret += dfs1(v);

    }

    return ret;

}

int dfs2(int u){

    vis[u] = true;

    int ret = 1;

    for(int i = 0; i < g[u].size(); i++){

        int v = g[u][i];

        if(!vis[v])

            ret += dfs2(v);

    }

    return ret;

}

int main(){

    int a, b, n, m;

    scanf("%d%d%d%d", &a, &b, &n, &m);

    for(int i = 0; i < n; i++){

        G[i].clear();

        g[i].clear();

    }

    for(int i = 1; i <= m; i++){

        int u, v;

        scanf("%d%d", &u, &v);

        G[u].push_back(v);  //正

        g[v].push_back(u);  //反

    }

    int ans1 = 0, ans2 = 0, ans3 = 0;

    for(int i = 0; i < n; i++){

        memset(vis, false, sizeof(vis));

        son[i] = dfs1(i);

        memset(vis, false, sizeof(vis));

        fa[i] = dfs2(i);

        if(n - son[i] < a) ans1++;

        if(n - son[i] < b) ans2++;

        if(fa[i] > b) ans3++;

    }

    printf("%d\n%d\n%d\n", ans1, ans2, ans3);

    return 0;

}

巴特西

Gym 101128A Promotions（思维 + dfs）题解

最新文章

热门文章