P1262 间谍网络

题目描述

由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果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，并在第二行输出不能控制的间谍中，编号最小的间谍编号。

输入输出样例

输入样例#1：复制

输出样例#1：复制

YES
110

输入样例#2：复制

输出样例#2：复制

NO
3

//tarjan缩点
//记录每个缩点内的点的编号最小值scc_id[],缩点内收买一个间谍的最小化费scc_w[],以及当前缩点内是不是有可以收买的间谍flag[]
//记录每个缩点的入度，如果一个缩点既没有入度而且它的flag[]==0，那么这个缩点内的不能被逮捕，则输出所有这样的缩点中scc_id[]最小的
//否则，就把那些入度为0的点的scc_w[]相加，就是ans
//本来以为要跑topsort的，但是写topsort的时候发现不知道如何转移，然后画图，发现不用topsort ⊙﹏⊙
 
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;

const int N=3e3+5;
const int M=8e3+5;
const int INF=599518803;

int n,p,m,ans;
int id[N],w[N];
int dfn[N],low[N],tim;
int belong[N];
bool instack[N];
bool flag[N];
int rudu[N];
int scc_w[N],scc_id[N],num_scc;
int head[N],num_edge;
struct Edge
{
    int u,v,nxt;
}edge[M],edg[M];
stack<int> sta;
queue<int> que;

int read()
{
    char c=getchar();int num=0;
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        num=num*10+c-'0';
    return num;
}

void add_edge(int u,int v)
{
    edge[++num_edge].u=u;
    edge[num_edge].v=v;
    edge[num_edge].nxt=head[u];
    head[u]=num_edge;
}

void add_edg(int u,int v)
{
    edg[++num_edge].u=u;
    edg[num_edge].v=v;
    edg[num_edge].nxt=head[u];
    head[u]=num_edge;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    instack[u]=1;
    sta.push(u);
    for(int i=head[u],v;i;i=edge[i].nxt)
    {
        v=edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
            if(instack[v])
                low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int tmp;
        ++num_scc;
        scc_w[num_scc]=scc_id[num_scc]=INF;
        do
        {
            tmp=sta.top();
            sta.pop();
            instack[tmp]=0;
            belong[tmp]=num_scc;
            flag[num_scc]|=w[tmp]!=1061109567;
            scc_w[num_scc]=min(scc_w[num_scc],w[tmp]);
            scc_id[num_scc]=min(scc_id[num_scc],tmp);
        }while(tmp!=u);
    }
}

void topsort()
{
    for(int i=1;i<=num_scc;++i)
        if(!rudu[i])
        {
            ans+=scc_w[i];
        }
//            que.push(i);
//    int now;
//    while(!que.empty())
//    {
//        now=que.front(),que.pop();
//        for(int i=head[now];i;i=edg[i].nxt)
//        {
//            
//        }
//    }
}

int main()
{
    memset(w,0x3f,sizeof(w));
    n=read(),p=read();
    for(int i=1;i<=p;++i)
        id[i]=read(),w[id[i]]=read();
//    for(int i=1;i<=n;++i)
//        printf("%d ",w[i]);
//        cout<<endl;
    m=read();
    for(int i=1,u,v;i<=m;++i)
    {
        u=read(),v=read();
        add_edge(u,v);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    memset(head,0,sizeof(head)),num_edge=0;
    for(int i=1;i<=m;++i)
    {
        if(belong[edge[i].u]!=belong[edge[i].v])
        {
            add_edg(belong[edge[i].u],belong[edge[i].v]);
            ++rudu[belong[edge[i].v]];
        }
    }
    ans=INF;
    for(int i=1;i<=num_scc;++i)
        if(!flag[i]&&!rudu[i])
        {
            ans=min(ans,scc_id[i]);
        }
    if(ans!=INF)
    {
        puts("NO");
        printf("%d",ans);
        return 0;
    }
    ans=0;
    topsort();
    puts("YES");
    printf("%d",ans);
    return 0;
}