luogu1262间谍网络

发表于 2017-07-18 分类于题解

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

请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。否则，输出不能被控制的一个间谍。 ### 非正解去年看到这道题时，第一想法：哇拓扑排序啊。结果。。。。。居然有55分。 ### 正解如果有环怎么办？把环缩成一个点就好了。

初始每个间谍看作一个点，每个“a可以揭发b”看作一条从a到b的有向边。每个点的权值是\(\infty\)（如果它对应的间谍不能被收买）或它对应间谍被收买需要的金额。跑Tarjan缩点。缩成后每个点的权值为这个点对应原强连通分量上点权值的最小值。对于每个入度为0的点，如果它的权值都不为\(\infty\)则可以，答案为它们的权值和。否则不行，如何求不能被控制间谍中序号的最小值呢? 对于每个点，如果可以被控制，染成颜色1。如果一个点点权不为\(\infty\)，则它和它后面的点都要染成1。从小到大考虑每个间谍，如果他对应点对应缩点后的那个点没被染成1，那么答案就是它的序号。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define up(a,b,c) for(int a(b),end##a(c);a<=end##a;++a) 
using namespace std;
int a[10000],dfn[10000],low[10000],beg[10000],to[20000],lst[20000];
int n,s,ins[10000],stk[10000],top,col[10000],c,qz[10000];//col[i]表示i对应强连通分量中点的序号
void Tarjan(int x){//求强连通分量
    dfn[x]=low[x]=++s;
    stk[++top]=x;
    int t;
    ins[x]=1;
    for(int i=beg[x];i;i=lst[i]){
        t=to[i];
        
        if(!dfn[t]){Tarjan(t);low[x]=min(low[x],low[t]);}
        else if(ins[t])low[x]=min(low[x],dfn[t]);
    }
    if(dfn[x]==low[x]){
        ++c;
        qz[c]=0x3f3f3f3f;
        while(stk[top]!=x){
            col[stk[top]]=c;
            qz[c]=min(qz[c],a[stk[top]]);
            ins[stk[top]]=0;
            --top;
        }
        col[stk[top]]=c;
        qz[c]=min(qz[c],a[stk[top]]);
        ins[stk[top]]=0;
        --top;
    }
}
int beg1[10000],to1[20000],lst1[20000],rd[10000],cd[10000],e;
void add_edge(int x,int y){
    ++cd[x];++rd[y];
    to1[++e]=y;
    lst1[e]=beg1[x];
    beg1[x]=e;
}
void SD(){
    up(i,1,n){
        for(int j=beg[i];j;j=lst[j]){
            if(col[to[j]]!=col[i]){
                add_edge(col[i],col[to[j]]);
            }
        }
    }
}
int can[10000];
void keng(int x){
    if(can[x])return;
    can[x]=1;
    for(int i=beg1[x];i;i=lst1[i]){
        keng(to1[i]);
    }
}
int main(){
    scanf("%d",&n);
    up(i,1,n)a[i]=0x3f3f3f3f;
    int p;
    scanf("%d",&p);
    up(i,1,p){
        int s;
        scanf("%d",&s);
        scanf("%d",a+s);
    }
    scanf("%d",&p);
    up(i,1,p){
        int s,t;
        scanf("%d%d",&s,&t);
        to[i]=t;
        lst[i]=beg[s];
        beg[s]=i;
    }
    up(i,1,n)if(!dfn[i])Tarjan(i);
    SD();
    int sum=0,no=0;
    up(i,1,c){
        if(rd[i]==0){
            if(qz[i]==0x3f3f3f3f)
                no=1;
            else {sum+=qz[i];}}
        if(qz[i]!=0x3f3f3f3f)keng(i);}//不管可不可以都计算一遍。
    if(no){
        printf("NO\n");
        up(i,1,n){
            if(can[col[i]]==0){
                printf("%d\n",i);
                return 0;
            }
        }
    }
    else{printf("YES\n%d\n",sum);}
    return 0;
}