NEFU OJ Problem1487 时空乱流题解

时空乱流

• Problem:E

• Time Limit:1500ms

• Memory Limit:65535K

Description

星际飞行员Alice在一次航行中遭遇了时空乱流，时空乱流将导致Alice乘坐的飞船在n个位面之间穿梭。
星际宇航局管理员Bob收到了Alice的求救信号，决定在某些位面上设立监测站，当Alice进入某个已经设立监测站的位面后，她会立即被拯救。
由于不同位面情况不同，设立监测站的花费也不相同。在第i个位面设立监测站，所需花费为Ci。
时空乱流已经被星际宇航局完全勘测，每个位面都有通往某个位面的通道，如果第i个位面没有监测站，Alice会前往第Ai个位面。（若Ai=i则会停留在当前位面）
Bob并不知道Alice的初始位置，他必须考虑所有可能的情况，并使用尽可能少的花费，确保能从时空乱流中救出Alice。
你能帮Bob计算出至少要花费多少，才能确保能救出Alice吗？`

Input

第一行一个整数T，表示有T组测试数据。
每组测试数据，第一行一个整数n (1≤n≤200000)，表示有n个位面。
第二行n个整数Ci(1≤Ci≤10000)，表示在第i个位面设立监测站的花费Ci。
第三行n个整数Ai(1≤Ai≤n)，表示第i个位面通往第Ai个位面。

Output

每组数据输出一个整数，表示最小花费。

Sample Input

3
5
1 2 3 2 10
1 3 4 3 3
4
1 10 2 10
2 4 2 2
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

Sample Output

3
10
2

Hint

输入数据较多，请使用scanf/printf

Source

AotoriChiaki

思路

根据题干，可以建出有向图，例如：

首先分析对于图中所有环，可以缩为一个点，该点的权重等于环上最小权重点

→

然后进行以下分析：

• 如果不在树根建站，则没有任何节点指向树根，则树根处未收录，必须额外在树根建站，所以树根必建站。
• 由于每个连通分量中的每个点都会指向树根，如果在树根建站，即可满足该联通分量每个点被收录。

所以在环缩点后每个树的树根建站即可满足题中条件。

如何实现？

对于缩点前的图：

• 每个点成为树根的条件为入度=0，所以如果有点满足入度为0则可以直接建站。
• 每个环都会被缩成点，所以针对每个环如果环上的点均满足入度为1（环上的点产生的入度），即可在该环上的最小值点建站

使用并查集完成环的查找和记录

在建图时同时维护一个并查集，如果某边的两端点已经在同一个并查集中（图中红色边），则说明此处有环，只进行记录而不进行并查集合并，可以保证每个环只记录一次。并且这样建成的图是一个树，后续只需要以该边的两端点分别为起点和终点进行dfs即可找到该环的路径。

代码如下文章来源地址https://www.toymoban.com/news/detail-746389.html

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+1, INF = 1e9;
const bool _debug = 0;

int c[N], fa[N]; //花费, 并查集父节点
pair<int, int> rnd[N];//环
vector<int> rod[N];//存边

int n;

void Init()
{
    for (int i = 1; i <= n; i ++)
        fa[i] = i;
}
int Find(int x)
{
    if(x == fa[x])
        return x;
    return fa[x] = Find(fa[x]);
}

void Dfs(int t, int goal, stack<int> &path)
{
    if(t == goal || path.top() == goal)
        return;
    if(_debug)cout << "当前 :" << t << endl;
    for (int i = 0; i < rod[t].size(); i ++)
    {
        int x = rod[t][i];
        path.push(x);
        if(_debug)cout << x << " 入栈" << endl;
        Dfs(x,goal,path);
        if(path.top() == goal)
            return;
        if(_debug)cout << path.top() << " 出栈" << endl;
        path.pop();
    }
}

int MinCost(pair<int, int> r)
{
    stack<int> path;
    path.push(r.first);
    Dfs(r.first, r.second, path);
    int res = INF;

    if(_debug)cout << "路径: ";
    while(!path.empty())
    {
        if(_debug)cout << path.top() << " ";
        res = min(res, c[path.top()]);
        path.pop();
    }
    if(_debug)cout << " 最小边： " << res << endl;
    return res;
}

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        //输入n 以及 花费
        int res = 0, rCnt = 0;
        scanf("%d", &n);

        for (int i = 1; i <= n; i ++)
            rod[i].clear();

        Init();
        for (int i = 1; i <= n; i ++)
            scanf("%d", &c[i]);

        //输入边（顺便找环）
        for (int i = 1; i <= n; i ++)
        {
            int inp;
            scanf("%d", &inp);

            if(inp == i)
            {
                //根节点直接加
                res += c[i];
                if(_debug)printf("res = %d\n", res);
                continue;
            }
            if(Find(i) == Find(inp))
            {
                //存环
                rnd[rCnt].first = i;
                rnd[rCnt].second = inp;
                if(_debug)printf("环：%d %d\n", i, inp);
                rCnt++;
                continue;
            }
            //存边、 合并
            rod[inp].push_back(i);
            fa[i] = inp;
        }

        //遍历环
        for(int i = 0; i < rCnt; i ++)
            res += MinCost(rnd[i]);

        printf("%d\n", res);

    }
    return 0;
}

到了这里，关于NEFU OJ Problem1487 时空乱流题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！