LibreOJ #10095. 「一本通 3.5 练习 3」间谍网络 & Luogu P1262 间谍网络
题面、题解和代码：
/*【题目描述】
由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据，则称 A 可以揭发 B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 n 个间谍，每个间谍分别用 1 到 n 的整数来标识。
请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
【输入】
第一行只有一个整数 n。第二行是整数 p。表示愿意被收买的人数。
接下来的 p 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。
紧跟着一行只有一个整数 r。然后 r 行，每行两个正整数，表示数对 (A，B)，A 间谍掌握 B 间谍的证据。
【输出】
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
【输入样例】
2
1
2 512
2
1 2
2 1
【输出样例】
YES
512
【提示】
1≤n≤3000,1≤p≤n,1≤r≤8000, 每个收买的费用为非负数且不超过 20000。
思路：tarjan缩点（缩点后的图一定是一个有向无环图(DAG)）。
方法：对于每一个可以贿赂且未遍历的点，缩点。
第一问：如果有点未被遍历，输出NO和点编号（从小到大）。
第二问：输出每一个入度为0的点集的最小价格的和。*/
#include<iostream>
#include<vector>
using namespace std;
template<typename t>
inline int min(t& a,t& b)
{
return a<b?a:b;
}
vector<int>edge[3001];
int prize[3001],prizemin[3001];//prize代表价格，prizemin代表点集的最小价格
int dfn[3001],low[3001],sta[3001],ty[3001],num,top,typ;
int du[3001],ans;
inline void tarjan(int x)
{
dfn[x]=low[x]=++num;
sta[++top]=x;
for(register vector<int>::iterator i=edge[x].begin();i!=edge[x].end();++i)
{
register int y=*i;
if(dfn[y])
{
if(!ty[y])
{
low[x]=min(low[x],dfn[y]);
}
}
else
{
tarjan(y);
low[x]=min(low[x],low[y]);
}
}
if(low[x]==dfn[x])
{
ty[x]=++typ;
while(sta[top]!=x)
{
ty[sta[top]]=typ;
prizemin[typ]=min(prizemin[typ],prize[sta[top]]);//计算最小价格
--top;
}
prizemin[typ]=min(prizemin[typ],prize[sta[top]]);//x点的最小价格
--top;
}
return;
}
int main()
{
ios::sync_with_stdio(false);//加速
cin.tie(NULL);
cout.tie(NULL);
register int n,p,r,a,b;
cin>>n>>p;
for(register int i=1;i<=n;++i)//初始化
{
prize[i]=100000;
prizemin[i]=100000;
}
for(int i=0;i<p;++i)
{
cin>>a>>b;
prize[a]=b;
}
cin>>r;
for(register int i=0;i<r;++i)
{
cin>>a>>b;
edge[a].push_back(b);
}
for(register int i=1;i<=n;++i)
{
if(!dfn[i] && prize[i]!=100000)//可以被贿赂且未被遍历
{
tarjan(i);
}
}
for(register int i=1;i<=n;++i)
{
if(!dfn[i])//未被遍历
{
cout<<"NO\n"<<i;
return 0;
}
}
for(register int i=1;i<=n;++i)
{
for(register vector<int>::iterator j=edge[i].begin();j!=edge[i].end();++j)
{
int x=*j;
if(ty[i]!=ty[x])
{
++du[ty[x]];//入度加1
}
}
}
for(register int i=1;i<=typ;++i)
{
if(!du[i])
{
ans+=prizemin[i];//答案加上最小值
}
}
cout<<"YES\n"<<ans;
return 0;
}效率：（LibreOJ）
测试点 #1 Accepted 得分：100 用时：2 ms 内存：252 KiB
测试点 #2 Accepted 得分：100 用时：2 ms 内存：252 KiB
测试点 #3 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #4 Accepted 得分：100 用时：3 ms 内存：252 KiB
测试点 #5 Accepted 得分：100 用时：4 ms 内存：380 KiB
测试点 #6 Accepted 得分：100 用时：5 ms 内存：380 KiB
测试点 #7 Accepted 得分：100 用时：6 ms 内存：380 KiB
测试点 #8 Accepted 得分：100 用时：6 ms 内存：380 KiB
测试点 #9 Accepted 得分：100 用时：6 ms 内存：508 KiB
测试点 #10 Accepted 得分：100 用时：7 ms 内存：508 KiB
测试点 #11 Accepted 得分：100 用时：6 ms 内存：508 KiB
测试点 #12 Accepted 得分：100 用时：3 ms 内存：252 KiB
（Luogu）
用时: 50ms / 内存: 1160KB
测试点信息
1
AC 3ms/780KB
2
AC 5ms/912KB
3
AC 4ms/940KB
4
AC 5ms/832KB
5
AC 3ms/644KB
6
AC 3ms/640KB
7
AC 3ms/776KB
8
AC 2ms/796KB
9
AC 3ms/796KB
10
AC 4ms/916KB
11
AC 5ms/844KB
12
AC 5ms/1044KB
13
AC 5ms/1160KB