C++——NOIP模拟题——间谍网络

由于外国间谍的大量渗入，国家安全正处于高度危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍接受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。

我们的反间谍机关提供了一份资料，包括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有 n 个间谍（ n 不超过 3000），每个间谍分别用 1 到 3000 的整数来标识。 

请根据这份资料，判断我们是否可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。

一行只有一个整数 n 。 
第二行是整数 p。表示愿意被收买的人数，1<=p<=n。 
接下来的 p 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过 20000。
紧跟着一行只有一个整数 r，1<=r<=8000。然后 r 行，每行两个正整数，表示数对（A，B），A 间谍掌握B间谍的证据。

如果可以控制所有间谍，第一行输出 YES ，并在第二行输出所需要支付的贿金最小值。否则输出 NO ，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

输入

2 
1 
2 512 
2 
1 2 
2 1

输出

YES 
512

输入

4 
2 
1 100 
4 200 
2 
1 2 
3 4

输出

NO 
3

输入

5 
1 
4 5435 
4 
1 2 
2 3 
3 1 
5 2

输出

NO 
1

解题报告：

很明显，这道题与节点的度有关。如果一个点的入度为0，则我们必然要贿赂他。但是如果单纯的考虑度就错了。我们忽略了一种入度全部大于0的情况——环。样例就是一个例子。这时如果我们再拓扑找环再去找最小值，我们就会花大量时间（毕竟边很多）。这时就要用到Tarjan缩点。

Tarjan是一种很高效的求解有向图的强连通分量的算法，但是它的主要应用之一是缩点，也就是把整个强连通分量的一定信息集中到一个点上，将其构成一个新图。由于所有强连通分量的并集是所有点的并集，所以整个图的相应性质不变。

我们把图G转化成一个由代表强连通分量的点构成的G’。我们只需记录该分量中最小的节点权值。然后在G’中找到入度为0的点，枚举是否能被贿赂，如果不能则输出NO，否则累加，到最后输出。

#include<cstdio>
#include<iostream>
bool b[3001][3001];
int v[3001],f[3001],a[3001][3001];
int va[3001],du[3001],mc[3001],rd[3001],dfn[3001],low[3001],stack[3001];
int n,m,p,x,y,num,deep,nd,minn=1e9,tot;
inline int readint()
{
    int i=0,f=1;
    char ch;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0' && ch<='9';ch=getchar())
        i=(i<<3)+(i<<1)+ch-'0';
    return i*f;
}
inline void put(int x)  
{  
    int num=0;char c[15];
    while(x) c[++num]=(x%10)+48,x/=10;
    while(num) putchar(c[num--]);
}
inline void zoom(int x)
{
	int list[3001],d=0,l=0,mini=1e9,mint=1e9;
	while(stack[num]!=x)
	{
		++l;
		list[l]=stack[num];
		f[stack[num]]=false;
		--num;
	}
	f[stack[num]]=false;
	++l;
	list[l]=stack[num];
	--num;
	for(int i=1;i<=l;++i)
	{
		mint=std::min(list[i],mint);
		d+=rd[list[i]];
		if(va[list[i]]>0&&va[list[i]]<mini) mini=va[list[i]];
	}
	for(int i=1;i<=l;++i)
		for(int j=1;j<=l;++j)
			if(i!=j&&b[list[i]][list[j]]) --d;
	if(!d&&mini==1e9) minn=mint;
	++nd;
	du[nd]=d;
	mc[nd]=mini;
}
inline void dfs(int x)
{
	low[x]=dfn[x]=++deep;
	stack[++num]=x;
	f[x]=true;
	for(int i=1;i<=a[x][0];++i)
		if(!v[a[x][i]])
		{
			v[a[x][i]]=true;
			dfs(a[x][i]);
			low[x]=std::min(low[x],low[a[x][i]]);
		}
		else if(f[a[x][i]]) low[x]=std::min(low[x],dfn[a[x][i]]);
	if(low[x]==dfn[x]) zoom(x);
}
inline void get()
{
	if(minn!=1e9)
	{
		puts("NO");
		put(minn);
	}
	else
	{
		for(int i=1;i<=nd;++i) if(!du[i]) tot+=mc[i];
		puts("YES");
		put(tot);
	}
}
int main()
{
	int i; 
	freopen("net.in","r",stdin);
	n=readint();
	p=readint();
	for(i=1;i<=p;++i) x=readint(),va[x]=readint();
	m=readint();
	for(i=1;i<=m;++i)
	{
		x=readint();
		y=readint();
		++a[x][0];
		a[x][a[x][0]]=y;
		b[x][y]=true;
		++rd[y];
	}
	for(i=1;i<=n;++i) if(!v[i]) dfs(i);
	get();
	return 0;
}