codevs 4093 EZ的间谍网络

时间限制: 10 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

　　我们的神通广大的YJY获得了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。

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

输入描述 Input Description

第一行只有一个整数n。

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

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

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

输出描述 Output Description

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

样例输入 Sample Input

【样例1】

1 10

2 100

1 3

2 3

【样例2】

1 100

4 200

1 2

3 4

样例输出 Sample Output

【样例1】

YES

110

【样例2】

NO<a name="_GoBack"></a>

数据范围及提示 Data Size & Hint

各个测试点1s

友情提示：请先膜拜下万能的YJY再做呦^_^

tarjan缩点

入度为0的是一定可以被控制的

这么写居然不会编译错误。。害得我找了好久

instack[x]-true;

屠龙宝刀点击就送

#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define N 6005

using namespace std;
vector<int>G[N];
bool f,instack[N];
int n,p,r,cnt,tim,top,sumcol,mn[N],mm[N],rd[N],to[N<<1],col[N],sum[N],mc[N],low[N],dfn[N],stack[N],head[N],nextt[N<<1];
inline int min(int a,int b) {return a>b?b:a;}
void tarjan(int x)
{
    low[x]=dfn[x]=++tim;
    stack[++top]=x;
    instack[x]=true;
    for(int i=head[x];i;i=nextt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[x]=min(low[x],low[v]);
        }
        else if(instack[v]) low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x])
    {
        int k;
        sumcol++;
        do
        {
            k=stack[top--];
            instack[k]=false;
            col[k]=sumcol;
            if(mn[k]) mc[sumcol]=min(mc[sumcol],mn[k]);
            mm[sumcol]=min(mm[sumcol],k);
        }while(k!=x);
    }
}
int main(int argc,char *argv[])
{
    scanf("%d",&n);
    scanf("%d",&p);
    for(int num,mnn,i=1;i<=p;++i)
    {
        scanf("%d%d",&num,&mnn);
        mn[num]=mnn;
    }
    memset(mc,0x3f,sizeof(mc));
    memset(mm,0x3f,sizeof(mm));
    scanf("%d",&r);
    for(int a,b;r--;)
    {
        scanf("%d%d",&a,&b);
        nextt[++cnt]=head[a];to[cnt]=b;head[a]=cnt;
    }
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;++i)
    {
        for(int j=head[i];j;j=nextt[j])
        {
            int v=to[j];
            if(col[i]!=col[v])
            {
                for(int k=0;k<G[col[i]].size();++k)
                if(G[col[i]][k]==col[v]) goto flag;
                G[col[i]].push_back(col[v]); 
                rd[col[v]]++;
                flag:;
            }
        }
    }
    int ans=0,ansn=0x7fffffff;
    for(int i=1;i<=sumcol;++i)
    {
        if(!rd[i])
        {
            if(mc[i]==1061109567)
            {
                f=1;
                ansn=min(ansn,mm[i]);
            }
            else ans+=mc[i];
        }
    }
    if(f) printf("NO
%d",ansn);
    else printf("YES
%d
",ans);
    return 0;
}