间谍网络 Editional

第一次用写题解qwqqwq

首先求出是否有点不能被访问 若有则显然这个间谍不能被控制

然后就是强连通分量问题 对于一个强连通分量我们贪心的选取其中花费最小的点统计答案

最终答案为入度为的点的花费和

不得不说代码量还挺大...

有一点要注意 边的数量应该是而不是和n同样大小，分的大多数是边表没开够吧...

边表写法为链式前向星，相比vector有肉眼可见的常数优势

Code:

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int MAXN = 3000 + 10;
struct node { int to, next; }edge[MAXN << 1];
int head[MAXN], n, r, p, money[MAXN], ans, cnt;
bool vis[MAXN];
queue<int> q;
stack<int> S;

inline void addedge(int u, int v) {
    edge[++cnt].to = v; edge[cnt].next = head[u];
    head[u] = cnt;
}

void bfs() {
    while(!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = true;
        for(int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            if(!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    for(int i = 1; i <= n; ++i) if(!vis[i]) {
        puts("NO");
        printf("%d\n", i);
        exit(0);
    }
}
int pre[MAXN], lowlink[MAXN], sccno[MAXN],scc_cnt, dfs_clock, in0[MAXN], best[MAXN];
void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    S.push(u);
    for(int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if(!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if(!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);
    }
    if(lowlink[u] == pre[u]) {
        scc_cnt++;
        if(!best[scc_cnt]) best[scc_cnt] = inf;
        for(;;) {
            int x = S.top(); S.pop();
            best[scc_cnt] = min(best[scc_cnt], money[x]);
            sccno[x] = scc_cnt;
            if(x == u) break;
        }
    }
}

void tarjan() { 
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof(sccno));
    memset(pre, 0, sizeof(pre));
    memset(best, 0, sizeof(best));
    for(int i = 1; i <= n; ++i) if(!pre[i]) dfs(i); 
}

void work() {
    for(int i = 1; i <= scc_cnt; ++i) in0[i] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = head[i]; j; j = edge[j].next) {
            int v = edge[j].to;
            if(sccno[i] != sccno[v]) in0[sccno[v]] = 0;
        }
    for(int i = 1; i <= scc_cnt; ++i) if(in0[i]) ans += best[i];
}

int main() {
    cin >> n >> p;
    memset(money, inf, sizeof(money));
    for(int i = 1, x, y; i <= p; ++i) {
        cin >> x >> y;
        money[x] = y;
        q.push(x);
    }
    cin >> r;
    for(int i = 1, u, v; i <= r; ++i) {
        cin >> u >> v;
        addedge(u, v);
    }
    bfs();
    tarjan();
    work();
    puts("YES"); printf("%d\n", ans);
    return 0;
}