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

佚名 5年前 (2019-05-09) 随笔 1056人围观抢沙发百度已收录

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

我们正向建边求出所有下级（包括自己）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;
}