题目传送门：https://www.luogu.com.cn/problem/P1262

 

                          P1262 间谍网络

题目

# P1262 间谍网络

## 题目描述

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

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

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

## 输入格式

第一行只有一个整数 $n$。

第二行是整数 $p$。表示愿意被收买的人数，$1\le p\le n$。

接下来的 $p$ 行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过 $20000$。

紧跟着一行只有一个整数 $r$，$1\le r\le8000$。然后 $r$ 行，每行两个正整数，表示数对 $(A, B)$，$A$ 间谍掌握 $B$ 间谍的证据。

## 输出格式

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

## 输入输出样例 #1

### 输入 #1

```
3
2
1 10
2 100
2
1 3
2 3
```

### 输出 #1

```
YES
110
```

## 输入输出样例 #2

### 输入 #2

```
4
2
1 100
4 200
2
1 2
3 4
```

### 输出 #2

```
NO
3
```

思路

Tarjan裸题。

其实我的思路比较直白，但是码量稍大(其实也就20min左右..)

首先的一个显然的结论就是，若我们可以控制所有的间谍，当且仅当缩点后所有入度为0的点上有可以贿赂的间谍。

为什么？因为缩完点后，这是一个dag，所有入度为零的点若没有人的话一定不会被走到。

所以我们如果可以走到的话，最终的答案就是所有入度为0的点的权值加起来。

（如果一个点上有多个可贿赂的间谍，记得取最小值。）

然后我们再看不能控制所有间谍的情况。

显然的一个思路，我们可以就缩点后的图重建一次，然后对每个有间谍的点进行染色，最后剩下的所有点中取最小值即可。

这个过程可能有点考验码力，不过如果tarjan写多点的话其实会发现还是蛮好写的

正解代码

#include <bits/stdc++.h>

using namespace std;

const int N = 8000 + 10;
int n , p , r;
int esp[N] , val[N] ,cnt;
int head[N];

struct Edge {
	int to , nxt;
}e[N];

void add(int u  , int v ) {
	e[++ cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

struct Edge_new{
	int to , nxt;
}e_new[N];

int head_new[N]; 
void add_new(int u ,int v) {
	e_new[++ cnt].to = v;
	e_new[cnt].nxt = head_new[u];
	head_new[u] = cnt;
}

int tot , idx , dfn[N] , low[N] , ins[N] , top , st[N] , wic[N];
int worth[N];
bool flag[N];

vector <int> S[N];

void Tarjan(int now) {
	dfn[now] = low[now] = ++ idx;
	ins[now] = 1; st[++ top] = now;
	for(int i = head[now] ; i ; i = e[i].nxt) {
		int v = e[i].to;
		if(!dfn[v]) {
			Tarjan(v);
			low[now] = min(low[now] , low[v]);
		} else if(ins[v]) low[now] = min(low[now] , dfn[v]);
	}
	if(low[now] == dfn[now]) {
		tot ++;
		int p;
		do {
			p = st[top --];
			if(esp[p]) flag[tot] = true , worth[tot] = min(worth[tot] , val[p]);
			S[tot].push_back(p);
			wic[p] = tot;
			ins[p] = 0;
		}while(p != now);
	}
}

int ind[N];

int vis[N];
void dfs(int now) {
	vis[now] = 1;
	for(int i = head_new[now] ; i ; i = e_new[i].nxt) {
		int v = e_new[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}

int Work() {
	for(int i = 1 ; i <= tot ; ++ i) 
		if(flag[i] && !vis[i]) dfs(i);
	int r = 0x3f3f3f3f;	
	for(int i = 1 ; i <= tot ; ++ i) 
		if(!vis[i]) {
			for(int j = 0 ; j < S[i].size() ; j ++) {
				r = min(r , S[i][j]);
			}
		}
	return r;
}

int main () {
	scanf("%d %d" , &n , &p);
	for(int i = 1 ; i <= n ; ++ i) worth[i] = 0x3f3f3f3f;
	for(int i = 1 ; i <= p ; ++ i) {
		int aa , bb;
		scanf("%d %d" , &aa , &bb);
		esp[aa] = 1; val[aa] = bb;	
	}
	scanf("%d" , &r);
	for(int i = 1 ; i <= r ; ++ i) {
		int u , v; scanf("%d %d" , &u ,&v);
		add(u , v);
	}
	for(int i = 1 ; i <= n ; ++ i) if(!dfn[i]) Tarjan(i);
	cnt = 0;
	for(int i = 1 ; i <= n ; ++ i ) {
		for(int j = head[i] ; j ; j = e[j].nxt) {
			int v = e[j].to;
			if(wic[i] == wic[v]) continue;
			ind[wic[v]] ++;
		}
	}
	int ans = 0 , f = 0; 
	for(int i = 1 ; i <= tot ; ++ i) {
		if(!ind[i] && flag[i]) {
			ans += worth[i];
		} else if(!ind[i]) f = 1;
	}
	if( ! f) {
		printf("YES\n%d\n" , ans);return 0;
	} else {
		for(int i = 1 ; i <= tot ; ++ i) {
			for(int j = 0 ; j < S[i].size() ; j ++) {
				int p = S[i][j];
				for(int k = head[p] ; k ; k = e[k].nxt) {
					int v = e[k].to;
					if(wic[v] == wic[p]) continue;
					add_new(wic[p] , wic[v]);
				}
			}
		}
		printf("NO\n%d\n",Work());	
	}
	return 0;
}