洛谷题单指南-连通性问题-P1262 间谍网络

原题链接：https://www.luogu.com.cn/problem/P1262

题意解读：有向图，有部分点有权值-即收买代价，计算选择最小的收买成本的点，可以使得扩散到所有的点。

解题思路：

如果是DAG，问题就好办，这些点必须是入度为0的点。

因此，对于有向图，可以通过强联通分量进行缩点，形成DAG，实际不必真进行缩点，只需计算scc的入度即可。

tarjan中根据每一个可收买的点的数额更新对应的强联通分量的最小收买数额。

对于每一个入度为0的scc，只要最小收买数额不是INF，就累加答案。

如何判断不可行呢？

可以从所有能收买且没有遍历过的节点开始执行tarjan找强联通分量，最终从1枚举哪些节点没有被遍历过(dfn为0)，第一个即最小的无法收买的节点。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 3005, M = 8005, INF = 0x3f3f3f3f;
int w[N]; //节点被收买的金额
int head[N], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], wscc[N], minscc[N], cnt; //节点对应的scc；scc中节点的最小的控制成本；scc中无法控制的最小节点
int in[N]; //强联通分量的入度
int n, p, m;

void add(int a, int b)
{
    to[++idx] = b;
    nxt[idx] = head[a];
    head[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[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(vis[v]) low[u] = min(low[u], dfn[v]);
    }

    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            wscc[cnt] = min(wscc[cnt], w[t]);
            if(w[t] == INF) //无法控制的节点
                minscc[cnt] = min(minscc[cnt], t); //更新scc中无法控制的最小节点
            if(t == u) break;
        }
    }
}

int main()
{
    memset(w, 0x3f, sizeof(w));
    memset(wscc, 0x3f, sizeof(wscc));
    memset(minscc, 0x3f, sizeof(minscc));
    cin >> n >> p;
    for(int i = 1; i <= p; i++)
    {
        int x, y;
        cin >> x >> y;
        w[x] = y;
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i] && w[i] != INF) //i能够被贿赂才一i为起点找scc
            tarjan(i);

    for(int i = 1; i <= n; i++)
    {
        if(!dfn[i]) //存在未被访问过的节点，即不能被控制的间谍
        {
            cout << "NO\n" << i; 
            return 0;
        }
    }

    //计算入度,将连通分量中无法控制的最小节点号进行递推传导
    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]) in[scc[v]]++;
        }
    }

    int ans = 0;
    for(int i = 1; i <= cnt; i++)
        if(in[i] == 0) 
            ans += wscc[i];

    cout << "YES\n" << ans;

    return 0;
}