[ZJOI2008] 骑士

小灰灰 2021-12-19 04:59 251阅读 0赞

[题目链接][Link 1]

**题目大意**

**　　**Z国要组织一支骑士团要参加一场战斗，每位骑士有一定的战斗力，同时每位骑士也有一个最厌恶的骑士（不是自己）。

要求选出一只骑士团，团中没有存在矛盾的两人（不存在一个骑士与他最厌恶的骑士一同被选入骑士团的情况），同时骑士团拥有最强战斗力。

**分析**

由于每位骑士只有一个厌恶的骑士，所以我们考虑连一条被厌恶骑士指向该骑士的有向边。这样就会形成若干个连通块，每个连通块均为基环树，且不存在指向环的边。

然后对于每个连通块，先找到环的位置，然后删去环的一条边（形成树形结构），删去的边上的两点记作a和b，以不选用a骑士和不选用b骑士分别做一次树形dp，得到最大战斗力。将每个连通块的最大战斗力相加，得到答案。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    using namespace std;
    #define ll long long
    #define inf 0x7fffffff
    #define N 1000005
    
    int n, m, a, b;
    int val[N], vis[N], fa[N];
    ll ans, f[N][2];
    vector<int> g[N];
    
    ll maxx(ll p, ll q) {
        if (p > q) return p;
        return q;
    }
    
    void find(int x) {
        vis[x] = 1; a = x;
        while(!vis[fa[a]]) {
            a = fa[a];
            vis[a] = 1;
        }
        b = fa[a];
    }
    
    void dfs(int x) {
        vis[x] = 1;
        if (x != a && x != b) f[x][0] = 0, f[x][1] = val[x];
        for (int i = 0; i < g[x].size(); i++) {
            int to = g[x][i];
            if (to == a) continue;
            dfs(to);
            f[x][0] += maxx(f[to][0], f[to][1]);
            f[x][1] += f[to][0];
        }
    }
    
    int main() {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", val + i, &m);
            g[m].push_back(i); fa[i] = m;
        }
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                ll now = 0;
                find(i);
                f[a][0] = 0; f[a][1] = val[a];
                f[b][0] = f[b][1] = 0;
                dfs(a);
                now = maxx(f[a][0], f[a][1]);
                f[a][0] = f[a][1] = 0;
                f[b][0] = 0; f[b][1] = val[b];
                dfs(a);
                now = maxx(now, f[a][0]);
                ans += now;
            }
        printf("%lld\n", ans);
    
        return 0;
    }

转载于:https://www.cnblogs.com/Pedesis/p/10919226.html

[Link 1]: https://www.luogu.org/problemnew/show/P2607
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/8e4b4bc7f48f46b6aa369110c73a9795.png