珂朵莉喊你一声大佬(tarjan求强连通分量并缩点+二分)

思路

• 本题中，每个点最多只有一条入边, 构成一个类似外向树森林的图。不了解外向树的可以搜索基环树(又称环套树)，外向树是基环树的一种，每个结点有且仅有一条入边。又因为本题中的点至多有一条入边,可能没有入边，所以是类似外向树，严格来说不是外向树
• 首先进行tarjan缩点，缩点的作用我认为有两个：①图中唯一可能存在的强连通分量就是环，缩点可以将环变成一个点，方便处理；②进行tarjan缩点之后，强连通分量的编号是$1-scc\mathrm{\_}cnt1-scc\backslash \_cnt$, 那么$1-scc\mathrm{\_}cnt1-scc\backslash \_cnt$就是缩点后的图的拓扑排序的逆序，所以不需要额外进行拓扑排序(拓扑排序的原因在进行二分的时候会讲)
• 进行tarjan算法时，额外计算两个数组：$num[i]num[i]$表示强连通分量$ii$里面所有种类大佬的总数, $kind[i]kind[i]$表示强连通分量$ii$中的大佬种类数。缩点的时候不需要额外建图，只需要维护数组$pre[i]pre[i]$表示强连通分量$ii$的前驱是$pre[i]pre[i]$
• 二分求最少的大佬数量：每次二分时，设每种大佬数量有$xx$个。按照逆拓扑序遍历强连通分量(也就是从叶子节点开始遍历)，每个强连通分量需要的大佬数量是$kind[i]\ast xkind[i]\; *\; x$，比较$num[i]\mathrm{和}kind[i]\ast xnum[i]和kind[i]\; *\; x$的大小，如果不够，首先在前驱里面补，最后再用任意m个大佬补。具体来说，当前结点如果够，就$continuecontinue$; 如果不够，如果有前驱，就将前驱的大佬总数$num+=deltanum\; +=\; delta$($deltadelta$是负数，代表缺少的大佬数量), 如果没有前驱，就将$sum+=-deltasum\; +=\; -delta$, sum最终和m进行比较，如果$sum>msum>m$就说明当前的大佬数量$xx$非法, $returnfalsereturn\backslash \; false$
• 注意num数组要开LL, 每次check函数中要利用num数组的备份来做，不能改变num数组，因为需要进行多次check

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 1e6 + 10, M = 2e9 + 7;
int n, m;
int f[N];
int h[N], e[N], ne[N], idx;
int a[N]; // a[i]: 第i种大佬的数量
int low[N], dfn[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc_cnt, id[N];
int pre[N];         // pre[i]: 连通块i可以由连通块pre[i]得到，即pre[i]->i
int kind[N];        // kind[i]: 连通块i种有几种大佬;
LL num[N], num1[N]; // num[i]: 连通块i中各种大佬加起来的总数, num1是num的备份，在check函数中使用

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

void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        int y;
        scc_cnt++;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            kind[scc_cnt]++;
            num[scc_cnt] += a[y];
        } while (y != u);
    }
}

bool check(int x)
{
    LL sum = 0; // 一共需要补多少个大佬, 最后和m比较, sum > m则代表不合法
    memcpy(num1, num, sizeof num);

    for (int i = 1; i <= scc_cnt; i++)
    {
        LL need = (LL)kind[i] * x;
        LL delta = (LL)num1[i] - need;
        if (delta >= 0)
        {
            continue;
        }
        else
        {
            if (pre[i] != 0) // 如果当前连通块有前驱, 就把当前需要增加的大佬数量让前驱去完成
                num1[pre[i]] += delta;
            else // 如果没有前驱, 就增加需要补充的大佬数量
            {
                sum += -delta;
            }
        }
        if (sum > m)
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i++)
    {
        cin >> f[i];
        if (f[i] != -1 && f[i] != i)
            add(f[i], i);
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }

    for (int u = 1; u <= n; u++)
    {
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            in***], b = id[j];
            if (a != b)
            {
                pre[b] = a;
            }
        }
    }

    int l = 0, r = 1e9, ans = 1;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(mid))
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    cout << ans << '\n';
    return 0;
}