luogu P3651 展翅翱翔之时 (はばたきのとき)

20 Jul 2017

Reading time ~1 minute

Description

船が往くよミライへ旅立とう

船只启航朝未来展开旅途

青い空笑ってる（なにがしたい?）

湛蓝天空露出微笑（想做些什么?）

ヒカリになろうミライを照らしたい

化作光芒吧想就此照亮未来

輝きは心からあふれ出してもっと先の景色望むんだ

光辉自内心满溢而出愿能望见更加前方的景色

Ah!やっと手にしたミライチケットかざして…！

Ah!挥舞起终于得手的未来门票…！

我们Aqours，终于闪闪发亮了！

2月25和26日，将是我们登上横滨ARENA演唱的日子！

而且，还要在全日本、甚至全世界的好多影院进行转播呢！

转播好像还是通过中继卫星传输的呢！

未来ずら！

不过，好像中继卫星上，出了一些问题呢……

我们的中继卫星一共有N颗，编号成1到N。不过，好像一个中继卫星可以且仅可以单向地从另一颗中继卫星那儿接收数据。

第i颗卫星现在已经被设定到了从第Ai颗卫星 (称为接收源) 那儿接受数据。

不过这些中继卫星的接收源是可以修改的，只不过每次修改要花一定的资金呢。

听说要达成中继的话，这些卫星之间必须两两之间能够互相（直接或间接）通信才行啊。

虽然鞠莉家里很有钱，可是这么大的花费，也得提前准备一下呢。

所以，你能帮我们算算这样子一共最少要花多少钱吗？

Input

第一行1个整数N。

接下来N行，每行2个整数Ai,Ci，表示初始时，第i个中继卫星从第Ai颗卫星处接收数据，以及该卫星调整接收源的所需花费。

Output

输出一个整数，表示鞠莉所需准备的最小的花费。

Sample Input

2 2

1 6

1 3

3 1

Sample Output

HINT

10% N<=10

40% N<=15

70% N<=3000

100% 2<=N<=100000, 1<=Ci<=10^9

Solution

这题很好啊~~虽然比赛时没AC~~

题意:1 ~ n 全弄成一个环需要的最少代价

原图可能有多个环此时需要拆开

可能环上连着其他的点

对于这些点只有两种情况:

对环上连着其他非环上点的点A，把它在环上的边破开。
把点A之外的点所连的边破开，同时把非环上点与环连的边破开

贪心的找对一个点连多个边的情况贪心保留最大的然后在枚举一下环上的点判一下是采取1情况好还是2情况好

官方题解:

我们把这种每个点入度（或者出度）为1的点称为有向环套树。显然，给出的图是一个环套树森林。我们讨论单个环套树的情况。

如果要两两可以互相交互，那么就是形成强连通。

只有一种结构可以达成：环。

所以说，我们需要找找出每个环套树的最长链。

首先找出环，然后环上的树上有多个孩子的点贪心保留权值大的点，这样变成了外向链。

然后枚举环上的每个点，把这个环破开，然后计算最长的链（你可以想象一下“6”这个数字，对就是这个意思）。

森林可能不连通，所以分别处理。最后复杂度是 $O(N)$

#include <cstdio>
#include <algorithm>

#define MAXN 111111

typedef long long LL;

int n, pd;
int a[MAXN];
LL b[MAXN];
LL f[MAXN], g[MAXN];
int huan[MAXN], d[MAXN], c[MAXN];
LL ans;

int main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d%lld", &a[i], &b[i]);
    for(int i = 1; i <= n; i++) {
        if(c[i]) continue;
        int j = i;
        while(!c[j]) {
            c[j] = i;
            j = a[j];
        }
//        printf("%d")
        if(i == c[j]) { //DEBUG i == c[j] not i == j eg:此处if里为找环  对于图： 1->2->3->4->5->3 如果从1开始 则最后停在3 而3->4->5为环  如果判断i==j则出错
            while(!huan[j]) {
                huan[j] = 1;
                j = a[j];
            }
        }
        pd++;
    }
    if(pd != 1) {
        for(int i = 1; i <= n; i++) {
            ans += b[i];
            f[a[i]] = std::max(f[a[i]], b[i]);
            if(!huan[i]) g[a[i]] = std::max(g[a[i]], b[i]);
        }
//        for(int i)
        for(int i = 1; i <= n; i++) ans -= f[i]/*, printf("huan[%d] = %d \n", i, huan[i])*/;
//        printf(">>> %lld\n", ans);
        for(int i = 1; i <= n; i++) {
            if(!huan[i]) continue;
            int j = i;
            LL tmp = 200000000000LL;
            while(!d[j]) {
                d[j] = 1;
                huan[j] = 0;
                j = a[j];
                tmp = std::min(tmp, f[j] - g[j]);
            }
            huan[j] = 0;
            ans += tmp;
//            printf(">>> %lld  %d \n", tmp, i);
        }
    }
    printf("%lld\n", ans);
    return 0;

}