P1262 间谍网络网页链接P1262 间谍网络题目描述由于外国间谍的大量渗入国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据则称 A 可以揭发 B。有些间谍收受贿赂只要给他们一定数量的美元他们就愿意交出手中掌握的全部情报。所以如果我们能够收买一些间谍的话我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍他手中掌握的情报都将归我们所有这样就有可能逮捕新的间谍掌握新的情报。我们的反间谍机关提供了一份资料包括所有已知的受贿的间谍以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n nn个间谍n nn不超过3000 30003000每个间谍分别用1 11到3000 30003000的整数来标识。请根据这份资料判断我们是否有可能控制全部的间谍如果可以求出我们所需要支付的最少资金。否则输出不能被控制的一个间谍。输入格式第一行只有一个整数n nn。第二行是整数p pp。表示愿意被收买的人数1 ≤ p ≤ n 1\le p\le n1≤p≤n。接下来的p pp行每行有两个整数第一个数是一个愿意被收买的间谍的编号第二个数表示他将会被收买的数额。这个数额不超过20000 2000020000。紧跟着一行只有一个整数r rr1 ≤ r ≤ 8000 1\le r\le80001≤r≤8000。然后r rr行每行两个正整数表示数对( A , B ) (A, B)(A,B)A AA间谍掌握B BB间谍的证据。输出格式如果可以控制所有间谍第一行输出YES并在第二行输出所需要支付的贿金最小值。否则输出NO并在第二行输出不能控制的间谍中编号最小的间谍编号。输入输出样例 #1输入 #13 2 1 10 2 100 2 1 3 2 3输出 #1YES 110输入输出样例 #2输入 #24 2 1 100 4 200 2 1 2 3 4输出 #2NO 3解题思路本题是有向图强连通分量缩点 最小代价覆盖的经典问题。间谍之间的揭发关系构成一张有向图若 A 掌握 B 的证据则控制 A 后即可控制 B。因此只要控制了某个强连通分量中的任意一个间谍整个分量都会被控制。我们需要判断能否控制所有间谍并求出最小收买费用。1. 问题等价转化将间谍视为节点揭发关系视为有向边A → B A \to BA→BA 掌握 B 的证据。若我们收买了一个间谍就能沿着有向边控制所有可达的间谍。整个图可以缩成若干个强连通分量SCC每个 SCC 内部可以互相控制。缩点后得到一个有向无环图DAG。要控制所有间谍必须控制 DAG 中所有入度为 0的 SCC因为它们无法被其他 SCC 控制只能通过收买其中的间谍来直接控制。对于每个入度为 0 的 SCC如果其中至少有一个间谍可以被收买则选择收买费用最小的那个就能控制整个 SCC。如果某个入度为 0 的 SCC 中没有任何间谍可以被收买则无法控制它从而无法控制全部间谍。2. 算法实现Kosaraju 覆盖标记代码采用 Kosaraju 算法求强连通分量并辅以覆盖标记来判断是否所有节点都能从可收买间谍到达。建图读入n nn和可收买间谍的信息用数组val[i]记录收买费用0 表示不可收买。读入r rr条有向边建立正向图g和反向图rg。第一次 DFS正向图遍历所有节点对未访问节点进行 DFS记录完成顺序到栈stk。第二次 DFS反向图按栈的逆序弹出节点对未分配 SCC 的节点在反向图上 DFS得到 SCC 编号col。同时对于每个 SCC记录其中可收买间谍的最小费用mn[cc]初始为极大值。覆盖标记从所有可收买的间谍出发在正向图上进行 DFS标记所有可达节点为cov true。这一步用于检查是否存在无法从任何可收买间谍到达的节点。判断无解遍历所有节点若存在!cov[i]说明该节点无法通过收买任何间谍来间接控制输出NO和该节点编号由于遍历顺序从小到大第一个未覆盖的即为最小编号结束程序。统计最小费用若所有节点都被覆盖则统计缩点后 DAG 中每个 SCC 的入度。遍历所有边若边的两端属于不同 SCC则目标 SCC 的入度加 1。最后对于所有入度为 0 的 SCC累加其mn值即为所需的最小总费用。输出YES和该费用。3. 复杂度分析时间复杂度Kosaraju 算法需要两次 DFS覆盖标记一次 DFS入度统计一次遍历均为O ( n m ) O(n m)O(nm)。n ≤ 3000 n \le 3000n≤3000m ≤ 8000 m \le 8000m≤8000运算量极小。空间复杂度需要存储正向图、反向图、SCC 信息、访问标记等均为O ( n m ) O(n m)O(nm)空间消耗可忽略。总结通过强连通分量缩点将问题转化为 DAG 上入度为 0 的分量的最小代价覆盖。利用覆盖标记提前判断无解情况并确保所有入度为 0 的分量都有可收买的间谍。最终累加这些分量的最小收买费用即为答案。该方法思路清晰是解决有向图控制问题的标准套路。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100005;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,k,id,cost,u,v,cc,ans;ll val[N],col[N],deg[N],mn[N];vectorllg[N],rg[N],stk;boolvis[N],cov[N];voidf1(ll u){vis[u]1;for(ll i0;i(ll)g[u].size();i)if(!vis[g[u][i]])f1(g[u][i]);stk.push_back(u);}voidf2(ll u){col[u]cc;if(val[u])mn[cc]min(mn[cc],val[u]);for(ll i0;i(ll)rg[u].size();i)if(!col[rg[u][i]])f2(rg[u][i]);}voidkos(){for(ll i1;in;i)if(!vis[i])f1(i);for(ll i(ll)stk.size()-1;i0;i--)if(!col[stk[i]]){cc;f2(stk[i]);}}voidf3(ll u,ll fa){cov[u]1;for(ll i0;i(ll)g[u].size();i){if(cov[g[u][i]])continue;f3(g[u][i],u);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(mn,0x3f,sizeof(mn));cinnk;for(ll i1;ik;i){cinidcost;val[id]cost;}cinm;for(ll i1;im;i){cinuv;g[u].push_back(v);rg[v].push_back(u);}kos();for(ll i1;in;i){if(!cov[i]val[i])f3(i,0);}for(ll i1;in;i){if(!cov[i]){coutNO\ni;return0;}}for(ll i1;in;i){for(ll j0;j(ll)g[i].size();j){if(col[i]!col[g[i][j]])deg[col[g[i][j]]];}}for(ll i1;icc;i){if(!deg[i])ansmn[i];}coutYES\nans;return0;} 
长河君 · 2026/10/15 9:37:20 · 阅读 1.2k P1262 间谍网络【洛谷算法习题】
P1262 间谍网络网页链接P1262 间谍网络题目描述由于外国间谍的大量渗入国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据则称 A 可以揭发 B。有些间谍收受贿赂只要给他们一定数量的美元他们就愿意交出手中掌握的全部情报。所以如果我们能够收买一些间谍的话我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍他手中掌握的情报都将归我们所有这样就有可能逮捕新的间谍掌握新的情报。我们的反间谍机关提供了一份资料包括所有已知的受贿的间谍以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n nn个间谍n nn不超过3000 30003000每个间谍分别用1 11到3000 30003000的整数来标识。请根据这份资料判断我们是否有可能控制全部的间谍如果可以求出我们所需要支付的最少资金。否则输出不能被控制的一个间谍。输入格式第一行只有一个整数n nn。第二行是整数p pp。表示愿意被收买的人数1 ≤ p ≤ n 1\le p\le n1≤p≤n。接下来的p pp行每行有两个整数第一个数是一个愿意被收买的间谍的编号第二个数表示他将会被收买的数额。这个数额不超过20000 2000020000。紧跟着一行只有一个整数r rr1 ≤ r ≤ 8000 1\le r\le80001≤r≤8000。然后r rr行每行两个正整数表示数对( A , B ) (A, B)(A,B)A AA间谍掌握B BB间谍的证据。输出格式如果可以控制所有间谍第一行输出YES并在第二行输出所需要支付的贿金最小值。否则输出NO并在第二行输出不能控制的间谍中编号最小的间谍编号。输入输出样例 #1输入 #13 2 1 10 2 100 2 1 3 2 3输出 #1YES 110输入输出样例 #2输入 #24 2 1 100 4 200 2 1 2 3 4输出 #2NO 3解题思路本题是有向图强连通分量缩点 最小代价覆盖的经典问题。间谍之间的揭发关系构成一张有向图若 A 掌握 B 的证据则控制 A 后即可控制 B。因此只要控制了某个强连通分量中的任意一个间谍整个分量都会被控制。我们需要判断能否控制所有间谍并求出最小收买费用。1. 问题等价转化将间谍视为节点揭发关系视为有向边A → B A \to BA→BA 掌握 B 的证据。若我们收买了一个间谍就能沿着有向边控制所有可达的间谍。整个图可以缩成若干个强连通分量SCC每个 SCC 内部可以互相控制。缩点后得到一个有向无环图DAG。要控制所有间谍必须控制 DAG 中所有入度为 0的 SCC因为它们无法被其他 SCC 控制只能通过收买其中的间谍来直接控制。对于每个入度为 0 的 SCC如果其中至少有一个间谍可以被收买则选择收买费用最小的那个就能控制整个 SCC。如果某个入度为 0 的 SCC 中没有任何间谍可以被收买则无法控制它从而无法控制全部间谍。2. 算法实现Kosaraju 覆盖标记代码采用 Kosaraju 算法求强连通分量并辅以覆盖标记来判断是否所有节点都能从可收买间谍到达。建图读入n nn和可收买间谍的信息用数组val[i]记录收买费用0 表示不可收买。读入r rr条有向边建立正向图g和反向图rg。第一次 DFS正向图遍历所有节点对未访问节点进行 DFS记录完成顺序到栈stk。第二次 DFS反向图按栈的逆序弹出节点对未分配 SCC 的节点在反向图上 DFS得到 SCC 编号col。同时对于每个 SCC记录其中可收买间谍的最小费用mn[cc]初始为极大值。覆盖标记从所有可收买的间谍出发在正向图上进行 DFS标记所有可达节点为cov true。这一步用于检查是否存在无法从任何可收买间谍到达的节点。判断无解遍历所有节点若存在!cov[i]说明该节点无法通过收买任何间谍来间接控制输出NO和该节点编号由于遍历顺序从小到大第一个未覆盖的即为最小编号结束程序。统计最小费用若所有节点都被覆盖则统计缩点后 DAG 中每个 SCC 的入度。遍历所有边若边的两端属于不同 SCC则目标 SCC 的入度加 1。最后对于所有入度为 0 的 SCC累加其mn值即为所需的最小总费用。输出YES和该费用。3. 复杂度分析时间复杂度Kosaraju 算法需要两次 DFS覆盖标记一次 DFS入度统计一次遍历均为O ( n m ) O(n m)O(nm)。n ≤ 3000 n \le 3000n≤3000m ≤ 8000 m \le 8000m≤8000运算量极小。空间复杂度需要存储正向图、反向图、SCC 信息、访问标记等均为O ( n m ) O(n m)O(nm)空间消耗可忽略。总结通过强连通分量缩点将问题转化为 DAG 上入度为 0 的分量的最小代价覆盖。利用覆盖标记提前判断无解情况并确保所有入度为 0 的分量都有可收买的间谍。最终累加这些分量的最小收买费用即为答案。该方法思路清晰是解决有向图控制问题的标准套路。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100005;constll INF1e18;constll M1e610;constll mod1e97;ll n,m,k,id,cost,u,v,cc,ans;ll val[N],col[N],deg[N],mn[N];vectorllg[N],rg[N],stk;boolvis[N],cov[N];voidf1(ll u){vis[u]1;for(ll i0;i(ll)g[u].size();i)if(!vis[g[u][i]])f1(g[u][i]);stk.push_back(u);}voidf2(ll u){col[u]cc;if(val[u])mn[cc]min(mn[cc],val[u]);for(ll i0;i(ll)rg[u].size();i)if(!col[rg[u][i]])f2(rg[u][i]);}voidkos(){for(ll i1;in;i)if(!vis[i])f1(i);for(ll i(ll)stk.size()-1;i0;i--)if(!col[stk[i]]){cc;f2(stk[i]);}}voidf3(ll u,ll fa){cov[u]1;for(ll i0;i(ll)g[u].size();i){if(cov[g[u][i]])continue;f3(g[u][i],u);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);memset(mn,0x3f,sizeof(mn));cinnk;for(ll i1;ik;i){cinidcost;val[id]cost;}cinm;for(ll i1;im;i){cinuv;g[u].push_back(v);rg[v].push_back(u);}kos();for(ll i1;in;i){if(!cov[i]val[i])f3(i,0);}for(ll i1;in;i){if(!cov[i]){coutNO\ni;return0;}}for(ll i1;in;i){for(ll j0;j(ll)g[i].size();j){if(col[i]!col[g[i][j]])deg[col[g[i][j]]];}}for(ll i1;icc;i){if(!deg[i])ansmn[i];}coutYES\nans;return0;}