P5008 [yLOI2018] 锦鲤抄

为啥感觉这道题作为紫题有点水

给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个有入度的点，获得它的点权并把它和它的出边从图上删去。最多能选择 \(k\) 个点，求最多能获得多少点权。

首先考虑DAG的情况,不难发现,对于DAG上的每一个点,如果它有入度,那么就一定能被选上,自己想一想就能明白.

然后考虑任意情况,直接跑一遍tarjan,转化为一个DAG.对于DAG上的每一个强连通分量,和上面一样.直接考虑每一个强连通分量内部

若一个强连通分量没有入度,那么无论怎么选,都会有一个点选不到,所以直接去掉最小的点就行

若一个强连通分量有入度,那么总有一个方案可以使所有点都被选上.

直接记录下所有可以被选的点,取前 \(k\) 大就行

时间复杂度可以做到 \(O(n+m)\),用nth_element,不过似乎比sort快不了多少

代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<functional>
#include<algorithm>
using namespace std;
const int N = 5e5 + 5, M = 5e6 + 5;

int n, m, k;
int tot, id[N], d[N], f[N];
int w[N], dfn[N], low[N], stk[N], top;
int head[N], ver[M], net[M], idx, scc_cnt;
bool in_stk[N];
vector<int> val[N], tmp;

void add(int a, int b)
{
    net[++idx] = head[a], ver[idx] = b, head[a] = idx;
}

void tarjan(int u)
{
    stk[++top] = u, dfn[u] = low[u] = ++tot;
    in_stk[u] = true;
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u])
    {
        int v;
        scc_cnt++;
        do
        {
            v = stk[top--];
            in_stk[v] = false;
            val[scc_cnt].push_back(w[v]);
            id[v] = scc_cnt;
        } while (u != v);
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int u = 1; u <= n; u++)
    {
        for (int i = head[u]; i; i = net[i])
        {
            int v = ver[i];
            int a = id[u], b = id[v];
            if (a != b)
                d[b]++;                
        }
    }
    for (int i = 1; i <= scc_cnt; i++)
    {
        if (d[i])
            for (int j = 0; j < val[i].size(); j++)
                tmp.push_back(val[i][j]);
        else 
        {
            nth_element(val[i].begin(), val[i].begin() + 1, val[i].end());
            for (int j = 1; j < val[i].size(); j++)
                tmp.push_back(val[i][j]);
        }
    }
    int ans = 0;
    nth_element(tmp.begin(), tmp.begin() + k, tmp.end(), greater<int>());
    for (int i = 0; i < k; i++)
        ans += tmp[i];
    printf("%d", ans);
    return 0;
}