信息学奥赛一本通 1517：间谍网络 | 洛谷 P1262 间谍网络

【题目链接】

ybt 1517：间谍网络
洛谷 P1262 间谍网络

【题目考点】

1. 图论：强连通分量 缩点

【解题思路】

每个间谍是一个顶点，如果间谍A可以揭发间谍B，那么从顶点A到顶点B有一条有向边，构成一个有向图。
一个间谍被控制，即被收买或揭发，在图论模型中对应为标记顶点。收买顶点的花费，称为标记顶点的代价。
如果间谍A被控制，且A可以揭发B，那么间谍B也会被控制。在图论模型中就是如果标记了顶点A，且A到B有弧，那么标记顶点B。
现在存在一些初始被标记的顶点（初始被收买的间谍），问能否完成标记所有顶点。如果可以完成，输出收买间谍的最小花费。如果不能完成，输出编号最小的未标记顶点。
将每个强连通分量看作一个顶点，将原图g缩点会形成一个有向无环图sg。以下描述中，“某强连通分量”也指该强连通分量在缩点后形成的顶点。
一个强连通分量中的只要有一个顶点被标记，那么整个强连通分量中的顶点都会被标记，缩点后表示该强连通分量的顶点也会被标记。
遍历原图，对于每个顶点i，$gCos{t}_i$表示标记顶点i的代价，顶点i所在强连通分量为$sc{c}_i$，使用$gCos{t}_i$更新标记$sc{c}_i$的最小代价$sgCos{t}_i$。
如果一个顶点或强连通分量未被标记，则将$gCos{t}_i$或$sgCos{t}_i$设为0。
遍历所有强连通分量，关注入度为0的强连通分量：

• 如果所有入度为0的强连通分量都已被标记，则所有顶点都可以被标记，标记顶点的最小代价为所有入度为0的强连通分量的最小标记代价$sgCost$的加和。
• 如果存在入度为0的强连通分量未被标记，则一定存在顶点未被标记。
  在缩点后的图上，从所有已标记的强连通分量出发进行深搜，把访问到的强连通分量都标记为已访问。
  再按顶点编号从小到大遍历所有顶点，如果顶点i所在的强连通分量是未访问的，则顶点i就是未被标记的编号最小的顶点。

【题解代码】

解法1：强连通分量 缩点

#include <bits/stdc++.h>
using namespace std;
#define N 3005
#define INF 0x3f3f3f3f
int n, scc[N], sn, degIn[N], dfn[N], low[N], ts, gCost[N], sgCost[N], sumCost;
vector<int> g[N], sg[N];//邻接表 g：原图  sg:缩点后的图 
bool inStk[N], allCtrled = true;
stack<int> stk;
bool vis[N];//vis[i]：间谍i能否被收买 
void tarjan(int u)
{int t;dfn[u] = low[u] = ++ts;stk.push(u);inStk[u] = true;for(int v : g[u]){if(dfn[v] == 0){tarjan(v);low[u] = min(low[u], low[v]);}else if(inStk[v])low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){sn++;do{t = stk.top();stk.pop();inStk[t] = false;scc[t] = sn;}while(t != u);}
}
void dfs(int u)
{vis[u] = true;for(int v : sg[u]) if(!vis[v])dfs(v);
}
int main()
{int p, r, a, b;cin >> n >> p;for(int i = 1; i <= p; ++i){cin >> a >> b;gCost[a] = b;//gCost[i]：如为0，i不能被收买。否则gCost[i]表示收买i的费用 }cin >> r;for(int i = 1; i <= r; ++i){cin >> a >> b;g[a].push_back(b);//a掌握b的证据，存在弧<a, b> }for(int i = 1; i <= n; ++i) if(dfn[i] == 0)//tarjan求强连通分量 tarjan(i);for(int u = 1; u <= n; ++u)//生成缩点后的图for(int v : g[u]) if(scc[u] != scc[v]){sg[scc[u]].push_back(scc[v]);degIn[scc[v]]++;//统计入度 }memset(sgCost, 0x3f, sizeof(sgCost));//sgCost[i]：强连通分量i中花费最小的间谍的花费，先把sgCost初始化为最大值for(int i = 1; i <= n; ++i) if(gCost[i] > 0)sgCost[scc[i]] = min(sgCost[scc[i]], gCost[i]);//更新i所在强连通分量中的最小花费 for(int i = 1; i <= sn ;++i) if(degIn[i] == 0){if(sgCost[i] == INF){ allCtrled = false;//allCtrled：是否可以控制所有间谍 break;}elsesumCost += sgCost[i];}if(allCtrled)cout << "YES" << endl << sumCost;else{for(int i = 1; i <= sn; ++i) if(sgCost[i] != INF && !vis[i])//只要强连通分量i中有被收买的间谍dfs(i); cout << "NO" << endl;for(int i = 1; i <= n; ++i) if(!vis[scc[i]])//只要当前i所属的强连通分量没有访问过（被收买），i就是没被收买的编号最小的间谍 {cout << i;break;}}return 0;
}