P1262 间谍网络

1、思路

阅读题目，发现有些间谍可以是被前面的点更新，也就是说，在一开始的时候，把能贿赂的人员从小到达排个序，再使用bfs算法，把他们能到达的人员的贿赂价钱设置为0。

有解的情况：

首先如果有环，我把环内的最少价钱的那一位买下，则整个环的间谍都被我买下。

首先把所有能被贿赂的根据bfs，依次把所有能到达的变为0

缩点之后，所有的都变为除了最小的那个，其他的都变为0，因此整个间谍网络只需要10就能买下。

但是对于如下情况

从小到大开始，依次是5，10，20，30。5能到达的点只有本身，不够，还要买下前面的环，而这个环10就能买下，因此如果有从X单向到Y,且X和Y都能买下，我们只需要买X。同理,尽管20比10更大，但是它还是需要买。否则无法买下所有的网络。因此，我们只需要买下缩点后入度为0的点就行。如果，如果入度为0的点不能被买下，那它就是无解。

有一个无法被遍历到，因此无解

无解的情况。

按能被贿赂的人员从小到大排序，依次处理每个能被贿赂的人员，如果能够被贿赂或者能够被更小的贿赂价钱到达，则打上一个标记，从小到大枚举所有人员，出现第一个标记则无解，输出该人员。

2、代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 6100, M = 11100;
struct PT //从小到大存储叛徒的价钱 
{
	int id,val;
	bool operator < (const PT &t)const 
	{
		return val < t.val;
	}
}pt[N];

int h[N],e[M],ne[M],idx;
int stk[N],top,timestamp;
bool st[N];
int dfn[N],low[N],id[N],Size[N],cnt;
int n,p,r;
int Value[N];
bool st1[N];
int din[N];
void add(int a,int b)
{
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void bfs(int x)// 将能到达的都置为0 
{

	if(st1[x]) return;
	st1[x] =true;
	int Q[N],tt = 1,hh = 0;
	Q[0] = x;
	while(hh!=tt)
	{
		int t = Q[hh++];
		for(int i = h[t];~i;i = ne[i])
		{
			int j = e[i];
			if(!st1[j])
			{
				st1[j] = true; 
				Q[tt++] = j;
				Value[j] = 0;
			}
		}
	}
}
void tarjan(int u) // 标准的tarjan算法 
{
	low[u] = dfn[u] = ++timestamp;
	stk[++top] = u;
	st[u] = true;
	for(int i = h[u];~i;i = ne[i])
	{
		int j = e[i];
		if(!dfn[j]) 
		{
			tarjan(j);
			low[u] = min(low[u],low[j]);
		}
		else if(st[j]) low[u] = min(low[u],dfn[j]);
	}
	if(low[u] == dfn[u])
	{
		++cnt;
		int y;
		do{
			y =  stk[top--];
			st[y] = false;
			id[y] = cnt;
			Size[cnt] += Value[y];
		}while(y!=u);
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%d",&p);
	memset(h,-1,sizeof h);
	memset(Value,0x3f,sizeof Value);
	for(int i = 1;i<=p;i++)
	{
		scanf("%d%d",&pt[i].id,&pt[i].val);
		Value[pt[i].id] = pt[i].val;	
	}
	sort(pt+1,pt+p+1);
	
	scanf("%d",&r);
	for(int i = 1;i<=r;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add(a,b);
	}
	for(int i = 1;i<=p;i++)
		bfs(pt[i].id);
			
	for(int i = 1;i<=n;i++)
	{
		if(!st1[i])
		{
			cout<<"NO"<<endl;
			cout<<i<<endl;
			return 0;
		}
	}
	for(int i = 1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i = 1;i<=n;i++)
	{
		for(int j = h[i];~j;j = ne[j])
		{
			int k = e[j];
			int a = id[i],b = id[k];
			if(a!=b)din[b]++;
		}
	}
	int sum = 0;
	for(int i = cnt;i;i--)
	{
		 if(!din[i])sum += Size[i];
	}

	cout<<"YES"<<endl;
	cout<<sum<<endl;
	return 0;
}