洛谷 1262 间谍网络 Tarjan 图论

#洛谷 1262 图论 tarjan

并不感觉把这道题目放在图的遍历中很合适，虽然思路比较简单但是代码还是有点多的，，

将可收买的间谍的cost值设为它的价格，不可购买的设为inf，按照控制关系连图，Tarjan缩点，得到的新图中，入度为0的点是必须购买的，如果这些点中存在inf，则不成立



#include <cstdio>

#include <algorithm>

#include <cstring>

const int inf = 0x3f3f3f3f;

const int maxn = (3000 + 500) * 2;

const int maxm =  50000;

int dfn[maxn], low[maxn], vis[maxn];

int sta[maxn];

int stackTop = 0;

int tim = 0;

int cost[maxn];

int costNew[maxn];

int from[maxn];

int cur = 0;

int indo[maxn];

int outdo[maxn];

int n, p, r;

int x, y;

int last[maxm], other[maxm], pre[maxm];

int totEdge = 0;

void add(int x, int y) {

    totEdge++;

    pre[totEdge] = last[x];

    last[x] = totEdge;

    other[totEdge] = y;

}

void tarjan(int x) {

    tim++;

    dfn[x] = low[x] = tim;

    vis[x] = 1;

    stackTop++;

    sta[stackTop] = x;

    for (int p = last[x]; p; p = pre[p]) {

        int q = other[p];

        if (!dfn[q]) {

            tarjan(q);

            low[x] = std :: min(low[x], low[q]);

        } else if (vis[q]) {

            low[x] = std :: min(low[x], dfn[q]);

        }

    }

    if (dfn[x] == low[x]) {

        cur++;

        costNew[cur] = inf;

        while (sta[stackTop] != x) {

            vis[sta[stackTop]] = 0;

            from[sta[stackTop]] = cur;

            costNew[cur] = std :: min(costNew[cur], cost[sta[stackTop]]);

            stackTop--;

        }

        vis[x] = 0;

        from[x] = cur;

        costNew[cur] = std :: min(costNew[cur], cost[x]);

        stackTop--;

    }

}

int main () {

    scanf("%d", &n);

    scanf("%d", &p);

    for (int i = 1; i <= p; i++) {

        scanf("%d", &x);

        scanf("%d", &cost[x]);

    }

    for (int i = 1; i <= n; i++)

        if (cost[i] == 0) cost[i] = inf;

    scanf("%d", &r);

    while (r--) {

        scanf("%d %d", &x, &y);

        add(x, y);

    }

    for (int i = 1; i <= n; i++) {

        if (!dfn[i]) tarjan(i);

    }

    for (int i = 1; i <= n; i++)

        for (int j = last[i]; j; j = pre[j]) {

            int q = other[j];

            if (from[i] != from[q]) {

                indo[from[q]]++;

                outdo[from[i]]++;

            }

        }

    long long ans = 0;

    bool flag = 0;

    for (int i = 1; i <= cur; i++) {

        if (indo[i] == 0) {

            if (costNew[i] == inf) {

                flag = 1;

                break;

            } else {

                ans += costNew[i];

            }

        }

    }

    if (!flag) {

        printf("YES\n%lld\n", ans);

    } else {

        printf("NO\n");

        for (int i = 1; i <= n; i++) {

            if (indo[from[i]] == 0 && costNew[from[i]] == inf) {

                printf("%d", i);

                break;

            }

        }

    }

    return 0;

}

巴特西

洛谷 1262 间谍网络 Tarjan 图论

最新文章

热门文章