洛谷 P1262 间谍网络

题目描述 Description

由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。假设总共有n个间谍(n不超过3000)，每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。
输入输出格式 Input/output

输入格式：

第一行只有一个整数n。
第二行是整数p。表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。然后r行，每行两个正整数，表示数对(A, B)，A间谍掌握B间谍的证据。

输出格式：

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

输入样例：

【样例1】
3
2
1 10
2 100
2
1 3
2 3
【样例2】
4
2
1 100
4 200
2
1 2
3 4

输出样例：

【样例1】
YES
110
【样例2】
NO
3

今天刚刚做了一道叫做上白泽慧音的题，于是就被这道题坑了……
如果一个间谍被贿赂了，那么他所知道的所有间谍就都被发现了，那么被发现的这些间谍知道的间谍也就被发现了（这其中的方法还是不要知道的比较好o(>﹏<)o）
一个可以贿赂的间谍是可以被另一个已被发现的间谍供出来的，因此，间谍与间谍之间的关系就构成了一个环，也就是强连通分量
要想获取整个这个强连通分量，仅贿赂其中可以贿赂的用钱最少的那个即可
那么整个强连通分量的价值就变成了这其中可被贿赂的间谍中花钱最少的那个费用

接下来就可以缩点了！
我们预先处理出整张图上的强连通分量，对于每一个强连通分量处理出它的价值，将整个强连通分量缩成一个点，重新建图
这里有一个小小的技巧，重新建图的时候，处理每个缩完后的点的入度，如果入度为0，那么就证明这个点是必须要花钱买的，那么把它加上，反之，如果入度不为0，就不要处理，因为之前花钱的那个点一定会得到该点的信息的
这样，就可以处理出最小花费了

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=233333;
struct doubi{
    int f,t;
}edge[maxn];
int next[maxn],first[maxn],tot;
int pre[maxn];
int scc_cnt;
int tong[maxn];
int vlaue[maxn];
int scc_num[maxn];
int n,m;
stack<int> q;
void build(int f,int t){
    edge[++tot].f=f;
    edge[tot].t=t;
    next[tot]=first[f];
    first[f]=tot;
}
bool vis[maxn];
void dfs(int u)
{
    for(int i=first[u];i;i=next[i]){
        int v=edge[i].t;
        if(!vis[v]){
            vis[v]=1;
            dfs(v);
        }
    }
}
bool check()
{
    for(int i=1;i<=n;i++){
        if(tong[i]){
            vis[i]=1;
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            return false;
        }
    }
    return true;
}
int cnt;
int Dfs(int u)
{
    int lowu=pre[u]=++cnt;
    q.push(u);
    for(int i=first[u];i;i=next[i]){
        int v=edge[i].t;
        if(!pre[v]){
            int lowv=Dfs(v);
            lowu=min(lowu,lowv);
        }
        else if(!scc_num[v]){
            lowu=min(lowu,pre[v]);
        }
    }
    if(lowu==pre[u]){
        scc_cnt++;
        while(10>2){
            int v=q.top();
            q.pop();
            scc_num[v]=scc_cnt;
            if(u==v){
                break;
            }
        }
    }
    return lowu;
}
bool rudu[maxn];
struct faq{
    int f,t;
}newedge[maxn];
int newnext[maxn],newfirst[maxn],newtot;
bool pd[maxn];
bool fuckcy[maxn];
void getvlaue()
{
    memset(vlaue,63,sizeof(vlaue));
    for(int i=1;i<=n;i++){
        if(tong[i]) fuckcy[scc_num[i]]=1;
    }
    for(int i=1;i<=scc_cnt;i++){
        for(int k=1;k<=n;k++){
            if(fuckcy[i]&&scc_num[k]==i&&tong[k]){
                vlaue[i]=min(vlaue[i],tong[k]);
            }
            else if(!fuckcy[i]){
                vlaue[i]=0;
            }
        }
    }
}
void build_new(int f,int t)
{
    newedge[++newtot].f=f;
    newedge[newtot].t=t;
    newnext[newtot]=newfirst[f];
    newfirst[f]=newtot; 
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        tong[a]=b;
    }
    int r;
    cin>>r;
    for(int i=1;i<=r;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        build(a,b);
    }
    if(check()){
        cout<<"YES"<<endl;
        for(int i=1;i<=n;i++){
            if(!pre[i]){
                Dfs(i);
            }
        }
        getvlaue();
        for(int i=1;i<=scc_cnt;i++){
            for(int j=1;j<=n;j++){
                if(scc_num[j]==i){
                    for(int k=first[j];k;k=next[k]){
                        int v=edge[k].t;
                        if(scc_num[v]!=i){
                            build_new(i,scc_num[v]);
                            rudu[scc_num[v]]=1;
                        }
                    }
                }
            }
        }
        int ans=0;
        for(int i=1;i<=scc_cnt;i++){
            if(!rudu[i]){
                ans+=vlaue[i];
            }
        }
        cout<<ans<<endl;
    }
    else{
        cout<<"NO"<<endl;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                cout<<i<<endl;
                break;
            }
        }
    }
    return 0;   
}