G - Outing(tarjan缩点+依赖背包)

这是个的依赖背包问题。我们由一个点 i 向他得依赖点 a[i]建边，我们会建成一个可能存在环的图，我们不难发现，对于图中的每一个联通分量来说最多只有一个环，而且在缩点后，这个环必然是这棵树的祖先结点。什么只有一个环？，根据本题题意，每一个点最多有一个依赖点，所以每一个点的出度为1，如果联通分量中出现了环，那么环中每一个点的出边必然指向环内的一个点，不会指向环外的点，所以这个环在缩点后出度必然为0。如果该连通分量中存在两个环，那么这两个环因为都没有出度，所以不可能出现由一个环出发走到另一个环的可能，因为所有结点的出度为1，该联通分量的的任意一个结点都有只有一个路径可走，假设路径A能走到第一个环，B能走到第二个环，路径A和路径B之间必然不连通，所以这两个环必然位于两个联通分量之中。

tarjan缩点之后，我们根据缩点后的图用并查集来合并同一联通分量的点，并且统计这个联通分量中祖先结点的大小（如果有环的话这个祖先结点的大小就是环的大小）。此时我们边可以将这题转化为分组背包问题，每一个联通分量便是分成了一组，每一组内的祖先结点大小即为该组中最小的选择数量，最大数量为整个联通分量的大小。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <queue>
#include <bitset>
#include <vector>
#include <map>
#define int long long
#define endl 'n'
#define lowbit(x) x &(-x)
#define mh(x) memset(x, -1, sizeof h)
#define debug(x) cerr << #x << "=" << x << endl;
#define brk exit(0);
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * N;
const int mod = 998244353;
const double esp = 1e-6;
const double pi = acos(-1);
typedef pair<int, int> PII;
typedef long long ll;
int a[N];
vector<int> g[N];
int dfn[N], low[N], id[N], Size[N], timestamp, scc_cnt;
int stk[N], top;
bool in_stk[N];
int f[N];
int p[N];
map<int, pair<int, int>> mp;
void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = true;
    for (auto j : g[u])
    {
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j])
        {
            low[u] = min(low[u], low[j]);
        }
    }
    if (dfn[u] == low[u])
    {
        int y;
        ++scc_cnt;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt]++;
        } while (y != u);
    }
}
int find(int x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
signed main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        g[i].push_back(a[i]);//建图
    }
    for (int i = 1; i <= n; i++)
    {
        if (!dfn[i])
            tarjan(i);
    }
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1; i <= n; i++)//并查集合并连通分量
    {
        int x = id[i], y = id[a[i]];
        if (find(x) !=find(y))
        {
            p[find(x)] = p[find(y)];
        }
    }
    for (int i = 1; i <= scc_cnt; i++)//统计该组的大小和最小选择人数
    {
        mp[find(i)].first = max(mp[find(i)].first, Size[i]);
        mp[find(i)].second += Size[i];
    }
    for (auto t : mp)//分组背包
    {
        for (int i = m; i >= 0; i--)
        {
            for (int j = t.second.first; j <= t.second.second; j++)
            {
                if (i >= j)
                    f[i] = max(f[i], f[i - j] + j);
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

最后

以上就是瘦瘦大神为你收集整理的G - Outing(tarjan缩点+依赖背包)的全部内容，希望文章能够帮你解决G - Outing(tarjan缩点+依赖背包)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。