思路

这道题中，图的遍历起点必然是可控制的，如果起点不可控制，答案肯定是NO,NO的情况只需要从1~n找到第一个没被遍历过的数输出就可以了。
因此，我们记录下每个节点的入度，那么就相当于从图中所有入度为0（且可以控制）的点开始拓扑排序，并记录访问节点即可。
但是题目不保证是有向无环图，因此我们需要对环进行缩点处理。这个环有可能是途中的环，也有可能称为一个起点。
对于中途的环，缩点之后我们并不需要知道这个点的花费，因为他们都可以从起点开始被控制。
不确定起点的环，我们可以随意从一个点出发tarjan遍历，然后将该连通分量所需支付金额替换成环中最小的支付金额即可。（可在退栈中实现）

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3005;

struct E //存边 
{
    int next, to;
} e[maxn << 2];

int n, m, p, r,id, a, b, ans; 
int ct[maxn],st[maxn], ru[maxn];
//ct为雇佣花费，st标记环的起点，ru为入度 
int cnt, head[maxn]; //用于存图 
int dfn[maxn], low[maxn], vis[maxn], bel[maxn], idx;
//用于tarjan，dfn为访问时间，low为可回溯的最早时间
//vis为可访问标记，bel记录每个点所属连通分量,idx为时间戳 
int stk[maxn], top;
//用于栈，存储连通分量 

void addedge(int from, int to)
{
    e[++cnt].next = head[from];
    e[cnt].to = to;
    head[from] = cnt;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++idx;
    vis[x] = 1;
    stk[++top] = x;

    for (int i = head[x]; i; i = e[i].next)
    {
        int to = e[i].to;

        if (!dfn[to])
        {
            tarjan(to); //遍历下一个节点
            low[x] = min(low[x], low[to]); //最早访问时间
        }
        else if (vis[to])
        {
            low[x] = min(low[x], dfn[to]);
        }
    }

    if (dfn[x] == low[x])
    {
        int y;

        while (y = stk[top--])
        {
            bel[y] = x;
            vis[y] = 0;

            if (st[y]) //缩点操作
            {
                if (ct[x])
                {
                    ct[x] = min(ct[x], ct[y]);    //如果都能买，只需要买最小的
                }
                else
                {
                    ct[x] = ct[y];    //否则先买能买的
                }
            }

            if (x == y)
            {
                break;
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0); //读入优化 
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cin >> p;
    for (int i = 1; i <= p; i++)
    {
        cin >> id >> ct[id]; 
    }
    cin >> r;
    for (int i = 1; i <= r; i++)
    {
        cin >> a >> b;
        addedge(a, b);
        ru[b]++; //记录入度 
    }
    for (int i = 1; i <= n; i++)
    {
        if (!ru[i] && ct[i]) //入度为0并且可支付必作为起点
        {
            ans += ct[i]; //答案加上
            tarjan(i);   //开始遍历
        }
    }
    for (int i = 1; i <= n; i++)
    {     //可能有成环的情况
        if (!dfn[i] && ct[i]) //没有遍历过并且可以被收买
        {
            st[i] = 1; //环的起点
            tarjan(i);   //开始遍历
        }
    }
    for (int i = 1; i <= n; i++)
    { //还是有节点没被访问到，那么不能控制所有间谍
        if (!dfn[i])
        {
            cout << "NO" << endl;
            cout << i << endl;
            return 0;
        }
    }
    for (int i = 1; i <= n; i++)
    {    
        if (st[i])
        {//可以控制所有的间谍，答案加上环的费用 
            ans += ct[i];
        }
    }
    cout << "YES" << endl;
    cout << ans << endl;
    return 0;
}