题解 P1262 【间谍网络】

· · 题解

可以看出此题有两种情况:

一是有的罪犯既不能贿赂他也没有罪犯能揭发他，那么此题无解，我们在遍历时打上标记，然后从小到大枚举，只要遇见没有标记的就输出然后退出即可

二是所有的罪犯都能直接或间接地被能贿赂的罪犯揭发。很明显，也有两种情况，一是没有环，那么资金就是贿赂那个没有入度的罪犯，二是有环，那么资金就是那个环里罪犯所需资金最小的。我们想，如果我们把环里的罪犯缩成一个点，那么全都是前者的情况了

至于如何缩点欢迎来看我的博客

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
struct ss{
    int next,to;
};ss data[200010];
const int inf=1e9+7;
int n,q,timeclock,p,top,cnt,ans,r;
int dfn[200010],low[200010],stack[200010],instack[200010],next[200010],head[200010];
int belong[200010],money[200010],sum[200010],size[200010],rd[200010];
void add(int a,int b)
{
    data[++p].next=head[a];
    data[p].to=b;
    head[a]=p;
}
void tarjan(int a)           //标准的tarjan代码 
{
    dfn[a]=low[a]=++timeclock;
    instack[a]=1;
    stack[++top]=a;
    for(int i=head[a];i;i=data[i].next)
    {
        int v=data[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[a]=min(low[a],low[v]);
        }
        else
        if(instack[v])
        low[a]=min(low[a],dfn[v]);
    }
    if(dfn[a]==low[a])
    {
        cnt++;
        while(stack[top+1]!=a)
        {
            belong[stack[top]]=cnt;
            instack[stack[top]]=0;
            size[cnt]++;
            sum[cnt]=min(sum[cnt],money[stack[top]]);
            top--;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    money[i]=1e9+7;        //记得赋初值哦 
    for(int i=1;i<=n;i++)
    sum[i]=1e9;
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int u,mo;
        scanf("%d%d",&u,&mo);
        money[u]=mo;
    }
    scanf("%d",&r);
    for(int i=1;i<=r;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i]&&money[i]!=inf)  //如果他能够被贿赂就以他为起点找环 
    tarjan(i);
    for(int i=1;i<=n;i++)      //在这里我们用dfn数组来判断它是否被遍历过 
    if(!dfn[i])
    {
        printf("NO\n");
        printf("%d\n",i);
        return 0;
    }

    for(int i=1;i<=n;i++)
    for(int j=head[i];j;j=data[j].next)
    if(belong[i]!=belong[data[j].to])
    {
        rd[belong[data[j].to]]++;   //记录入度 
    }
    printf("YES\n");
    for(int i=1;i<=cnt;i++)
    {
       if(!rd[i])
       { 
           ans+=sum[i];
       }
    }
    printf("%d\n",ans);
    return 0;
}