Tarjan板子 93pts, RE on #6,救救孩子吧
查看原帖
Tarjan板子 93pts, RE on #6,救救孩子吧
235561
samzhangjy楼主2023/8/2 15:37

rt,#6 输入感觉有点奇怪:

2
1
2 512
2
1 2
2 1


最后一行是一个奇怪的字符(clion里打开显示 SUB,现在在洛谷上编辑区是个红点,预览里是空的)

输出:

YES
512

本地测试通过,不知道为什么洛谷上 RE。

代码:

//  P1262 间谍网络

#include<bits/stdc++.h>
using namespace std;
const int N = 3010, M = 8010;

int n, m, p;

class Graph {
private:
    vector<int> G[N];

public:
    int inDegree[N];
    void addEdge(int u, int v) {
        G[u].push_back(v);
        inDegree[v]++;
    }

    vector<int> operator[](int idx) {
        return G[idx];
    }
};

class Node {
public:
    int id;
    bool canBuy;
    int cost;
};

vector<Node> nodes;

int dfn[N], low[N], color[N], idx = 0, sccCnt = 0;
bool isBuyable[N];
int minCost[N], minId[N];
stack<int> s;

void tarjan(int u, Graph& G) {
    dfn[u] = low[u] = ++idx;
    s.push(u);
    for (auto v : G[u]) {
        if (!dfn[v]) {
            tarjan(v, G);
            low[u] = min(low[u], low[v]);
        } else if (!color[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        while (!s.empty()) {
            int x = s.top();
            s.pop();
            color[x] = sccCnt;
            minId[sccCnt] = min(minId[sccCnt], x);
            if (nodes[x].canBuy) {
                isBuyable[sccCnt] = 1;
                minCost[sccCnt] = min(minCost[sccCnt], nodes[x].cost);
            }
            if (x == u) break;
        }
    }
}

int main() {
    memset(minCost, 0x3f, sizeof(minCost));
    memset(minId, 0x3f, sizeof(minId));
    Graph G, reG;
    scanf("%d%d", &n, &p);
    for (int i = 1; i <= n; i++) {
        nodes.push_back(Node{i, 0, 0});
    }
    for (int i = 1; i <= p; i++) {
        int id, x;
        scanf("%d%d", &id, &x);
        nodes[id].canBuy = 1, nodes[id].cost = x;
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.addEdge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (nodes[i].canBuy && !dfn[i]) tarjan(i, G);
    }
    bool valid = 1;
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            valid = 0;
            printf("NO\n%d\n", i);
            break;
        }
    }
    if (!valid) return 0;
    printf("YES\n");
    for (int i = 1; i <= n; i++) {
        for (auto v : G[i]) {
            if (color[i] != color[v]) {
                reG.addEdge(color[i], color[v]);
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= sccCnt; i++) {
        if (reG.inDegree[i]) continue;
        ans += minCost[i];
    }
    printf("%lld\n", ans);
    return 0;
}

thx!

2023/8/2 15:37
加载中...