P1262 间谍网络（Tarjan 求强连通分量）

雨点打透心脏的1/2处 2022-12-31 01:29 135阅读 0赞

题目传送门：[https://www.luogu.com.cn/problem/P1262][https_www.luogu.com.cn_problem_P1262]

## 题意 ##

题意转换成图的角度理解，给出初始可以访问的节点  D i D\_i Di 以及访问这些节点需要的代价  W i W\_i Wi，然后给出一张节点从  1 1 1 到  N N N 编号的**有向图**，求能否通过这些初始节点访问整张图。如果可以则输出 YES 和最小的代价，否则输出 NO 和编号最小的不能访问的节点。

注意：假如通过  D 1 D\_1 D1 访问到  D 2 D\_2 D2, 并不需要支付  W 2 W\_2 W2 的代价。

## 思路 ##

其实这是一道 Tarjan 求有向图强连通分量的模板题，大致求解步骤如下：

*  利用所有初始能访问的点跑 Tarjan 去求图的强连通分量（得到强连通分量的时候可以顺便求访问该连通分量最小代价）；
 *  通过遍历点判断是否能访问整张图，如果遇到没有访问编号不能则输出 NO 和节点编号；
 *  我们将每个强连通分量都视作一个点（术语称 “缩点” ），然后统计各个强连通分量的入度；
 *  所有入度为 0 的点（强连通分量）访问的最小代价之和，即为我们要的答案。

Q: 为什么是入度为 0 呢？  
A: 因为入度非零的点，是可以通过其他点访问，我们没有必要在此花费多余的代价。

## 参考代码 ##

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    const int maxn = 1e4;
    const int inf = 0x3f3f3f3f;
    struct Edge { 
        int v, next;
    } e[maxn];
    int head[maxn];
    
    // dfn[i]表示i节点被访问的时间戳
    // low[i]表示i及其子节点能回溯到的最小时间戳
    int dfn[maxn], low[maxn], Time;
    
    // belong[i] 表示i点所属的连通分量
    // sccSize[i] 表示连通分量i的大小，i的取值范围为[0,scc)
    // scc 表示连通分量的个数
    int belong[maxn], sccSize[maxn], scc;
    int Stack[maxn], top; // 数组模拟栈
    bool inStack[maxn];   // 点是否在栈中
    int n, p, r;
    
    // w[i] 表示通过i点开始访问消耗的代价，如果不能访问，则值为inf
    // in[i] 表示连通分量i的入度
    // minCost[i] 表示访问连通分量i所需要的最小代价
    int w[maxn], in[maxn], minCost[maxn];
    
    void addEdge(int u, int v, int i) { 
        e[i].v = v;
        e[i].next = head[u];
        head[u] = i;
    }
    
    // main 函数中调用一次能求出u能访问到的所有连通分量
    void Tarjan(int u) { 
        int v;
        dfn[u] = low[u] = ++Time;
        Stack[++top] = u;
        inStack[u] = true;
        for (int i = head[u]; i; i = e[i].next) { 
            v = e[i].v;
            if (!dfn[v]) { 
                Tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) { 
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) { 
            scc++;
            do { 
                v = Stack[top--];
                belong[v] = scc;
                sccSize[scc]++;
                inStack[v] = false;
                minCost[scc] = min(minCost[scc], w[v]); // 求能访问该连通分量的最小代价
            } while (u != v);
        }
    }
    
    int main()
    { 
        scanf("%d", &n);
        scanf("%d", &p);
        memset(w, inf, sizeof(w));
        memset(minCost, inf, sizeof(minCost));
        for (int i = 0; i < p; i++) { 
            int t, tw;
            scanf("%d %d", &t, &tw);
            w[t] = tw;
        }
    
        scanf("%d", &r);
        for (int i = 1; i <= r; i++) { 
            int u, v;
            scanf("%d %d", &u, &v);
            addEdge(u, v, i);
        }
    
        for (int i = 1; i <= n; i++) { 
        	// 该点没有被访问过，且该点初始能通过付出一定代价访问
            if (!dfn[i] && w[i] != inf) { 
                Tarjan(i);
            }
        }
    
        for (int i = 1; i <= n; i++) { 
        	// 如果还有点没有访问过，说明不能遍历整张图
            if (!dfn[i]) { 
                printf("NO\n");
                printf("%d", i);
                return 0;
            }
        }
        for (int i = 1; i <= n; i++) { 
            for (int j = head[i]; j; j = e[j].next) { 
                int v = e[j].v;
                // 如果i能到v，而且它们属于不同的连通分量，则说明该边给v所属连通分量贡献了一个入度
                if (belong[i] != belong[v]) { 
                    in[belong[v]]++; // 统计各连通分量的入度
                }
            }
        }
    
        int ans = 0;
        for (int i = 1; i <= scc; i++) { 
        	// 如果入度为 0， 
            if (!in[i]) { 
                ans += minCost[i];
            }
        }
        printf("YES\n");
        printf("%d", ans);
        return 0;
    }

[https_www.luogu.com.cn_problem_P1262]: https://www.luogu.com.cn/problem/P1262