间谍网络（强连通分量缩点）

原题见洛谷。

分析

首先这是有向图，又是一个举报一团，自然联想到缩点。

于是先缩点，记录每个缩的点的入度，其中是否有可买的间谍以及最低价格多少。

然后对于入度为0的缩点一定要在里面买一个间谍，如果入度为0又没有可买的间谍，flag=1，但是不要急着退出，把所有的缩点检查一遍。每买通一个就做一遍dfs标记哪些缩点被掌握。

如果flag=0，输出花费。flag=1，扫一遍所有的点（不是缩点）如果这个点属于的分量既没有被掌握，又没有可买的间谍，输出这个点，退出。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3005;
const int MAXM=8005;
const int INF=1000000;
int N,M,np=0,last[MAXN],val[MAXN];
int np2=0,last2[MAXN],rd[MAXN],cd[MAXN],buy[MAXN],have[MAXN];
int dfs_clock=0,top=0,scc=0,size[MAXN],belong[MAXN],stk[MAXN],dfn[MAXN],low[MAXN];
struct edge{int to,pre;};
edge E[MAXM],E2[MAXM];

char c;
void scan(int &x)
{
	for(c=getchar();c<'0'||c>'9';c=getchar());
	for(x=0;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';
}

void addedge(int u,int v)
{
	E[++np]=(edge){v,last[u]};
	last[u]=np;
}

void addedge2(int u,int v)
{
	E2[++np2]=(edge){v,last2[u]};
	last2[u]=np2;
}

void tarjan(int i)
{
	dfn[i]=low[i]=++dfs_clock;
	stk[++top]=i;
	for(int p=last[i];p;p=E[p].pre)
	{
		int j=E[p].to;
		if(dfn[j])
		{
			if(!belong[j]) low[i]=min(low[i],dfn[j]);
			continue;
		}
		tarjan(j);
		low[i]=min(low[i],low[j]);
	}
	if(low[i]==dfn[i])
	{
		scc++;
		while(1)
		{
			int x=stk[top--];
			belong[x]=scc;
			size[scc]++;
			buy[scc]=min(buy[scc],val[x]);
			if(x==i) break;
		}
	}
}

void dfs(int i)
{
	if(have[i]) return;
	have[i]=1;
	for(int p=last2[i];p;p=E2[p].pre)
	{
		int j=E2[p].to;
		dfs(j);
	}
}

void suodian()
{
	int i,p,u,v;
	for(i=1;i<=N;i++)
	{
		u=belong[i];
		for(p=last[i];p;p=E[p].pre)
		{
			v=belong[E[p].to];
			if(u==v) continue;
			addedge2(u,v);
			cd[u]++; rd[v]++;
		}
	}
}

void solve_NO()
{
	puts("NO");
	for(int i=1;i<=N;i++)
	{
		if(!have[belong[i]]&&buy[belong[i]]==INF)
		{
			cout<<i;
			return;
		}
	}
}

int main()
{
	int i,u,v,w;
	scan(N);scan(M);
	fill(val+1,val+N+1,INF);
	fill(buy+1,buy+N+1,INF);
	for(i=1;i<=M;i++)
	{
		scan(u);
		scan(val[u]);
	}
	scan(M);
	for(i=1;i<=M;i++)
	{
		scan(u);scan(v);
		addedge(u,v);
	}
	for(i=1;i<=N;i++) if(!dfn[i]) tarjan(i);
	suodian();
	
	int cost=0,flag=0;
	for(i=1;i<=scc;i++)
	{
		if(rd[i]==0)
		{
			if(buy[i]==INF) flag=1;
			else
			{
				cost+=buy[i];
				dfs(i);
			}
		}
	}
	if(flag) solve_NO();
	else puts("YES"),cout<<cost;
	return 0;
}