D. Mouse Hunt

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--D. Mouse Hunt

题解

中档题,题意大概是一只老鼠与一群房间,每个房间老鼠会往某个特定的房间跑,求最少的可以抓到老鼠的陷阱费用。
枚举每个最终的环即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;

int dfn[maxn], low[maxn], scccnt = 0, sccindex = 0, belong[maxn];

bool instack[maxn];
stack<int>sta;
vector<int>G[maxn];

void tarjan(int v) {
    dfn[v] = low[v] = ++sccindex;
    sta.push(v); instack[v] = true; int j;
    for (auto i = G[v].begin(); i != G[v].end(); i++) {
        int j = *i;
        if (!dfn[j]) {
            tarjan(j);
            low[v] = min(low[v], low[j]);
        }
        else if (instack[j] && dfn[j]<low[v])
            low[v] = dfn[j];
    }
    if (low[v] == dfn[v]) {
        scccnt++;
        do {
            j = sta.top(); instack[j] = false;
            sta.pop(); belong[j] = scccnt;
        } while (j != v);
    }
}

int outdegree[maxn], c[maxn];
int minn[maxn], size1[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++)cin >> c[i];
    long long ans = 0;
    for (i = 1; i <= n; i++) {
        cin >> j;
        G[i].push_back(j); outdegree[i]++;
        if (j == i)ans += c[i];
    }
    for (i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    for (i = 1; i <= n; i++)
        size1[belong[i]]++;
    memset(minn, 0x3f, sizeof(minn));
    for (i = 1; i <= n; i++) {
        if (size1[belong[i]] <= 1)continue;
        minn[belong[i]] = min(minn[belong[i]], c[i]);
    }
    for (i = 1; i <= n; i++) {
        if (minn[i] != 0x3f3f3f3f)
            ans += minn[i];
    }
    cout << ans << endl;

    return 0;
}

标签: dfs and similar, graphs

添加新评论