间谍网络

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3302 字
Tarjan缩点取入度零分量最小代价
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1517
// 题意：n 个间谍，一部分可被收买（各有价钱），有若干揭发关系，问能否控制全部间谍，能则输出最小花费，否则输出无法控制的最小编号间谍。
// 思路：Tarjan 缩点后，若每个入度为 0 的分量内都有可收买者，答案为各入度 0 分量的最小收买价之和；否则从可收买分量出发做可达性标记，找最小未覆盖间谍编号。
// 1. 缩点 DAG 上入度为 0 的分量必须直接收买，其余分量都能由它们顺边推出来。
// 2. 无解时答案不是某个入度 0 分量的最小编号，而是所有无法到达分量中的最小间谍编号。
// 复杂度：O(n + r) 时间 / O(n + r) 空间
// 易错点：收买价取分量内的最小值，不是求和，同一分量内收买一人即可控制全分量。
// 易错点：找最小编号间谍要按间谍编号从小到大扫，不能按分量编号扫。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
const int MAXR = 8005;
const int INF = 0x3f3f3f3f;
int head[MAXN], to[MAXR], nxt[MAXR], ecnt;
int head2[MAXN], to2[MAXR], nxt2[MAXR], ecnt2;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], scnt;
bool instk[MAXN];
int price[MAXN];
int mincost[MAXN];
int indeg[MAXN];
bool reach[MAXN];
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            if(x == u) break;
        }
    }
}
int main(){
    int n;
    if(!(cin >> n)) return 0;
    for(int i = 1; i <= n; i++){
        price[i] = INF;
    }
    int p;
    cin >> p;
    for(int i = 0; i < p; i++){
        int a, b;
        cin >> a >> b;
        if(b < price[a]) price[a] = b;
    }
    int r;
    cin >> r;
    for(int i = 0; i < r; i++){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int i = 1; i <= scnt; i++){
        mincost[i] = INF;
    }
    for(int i = 1; i <= n; i++){
        if(price[i] < mincost[scc[i]]) mincost[scc[i]] = price[i];
    }
    for(int u = 1; u <= n; u++){
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(scc[u] != scc[v]){
                indeg[scc[v]]++;
                to2[++ecnt2] = scc[v];
                nxt2[ecnt2] = head2[scc[u]];
                head2[scc[u]] = ecnt2;
            }
        }
    }
    bool ok = true;
    long long ans = 0;
    for(int i = 1; i <= scnt; i++){
        if(!indeg[i]){
            if(mincost[i] >= INF){
                ok = false;
                break;
            }
            ans += mincost[i];
        }
    }
    if(ok){
        cout << "YES" << "\n";
        cout << ans << "\n";
        return 0;
    }
    queue<int> q;
    for(int i = 1; i <= scnt; i++){
        if(mincost[i] < INF){
            reach[i] = true;
            q.push(i);
        }
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = head2[u]; i; i = nxt2[i]){
            int v = to2[i];
            if(!reach[v]){
                reach[v] = true;
                q.push(v);
            }
        }
    }
    int who = n + 1;
    for(int i = 1; i <= n; i++){
        if(!reach[scc[i]]){
            who = i;
            break;
        }
    }
    cout << "NO" << "\n";
    cout << who << "\n";
    return 0;
}
间谍网络

正文

一本通·提高篇的其它内容
