题解 P1262 【间谍网络】

· · 题解

思路楼上前辈们已经说的很清楚了，这里来补充一种不用BFS直接求强连通的写法，主要思路就是在tarjan中统计一个强连通分量最小费用的同时统计出该强连通分量中编号最小的点，当情况为NO时只要输出所有不能购买且入度为0的强连通分量中编号最小的点的最小值就行了~


#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

int n,p;

int buy[3001],pre[3001]={0},lowlink[3001],sccno[3001]={0},cost[3001]={0};
int sccrd[3001]={0},scclow[3001];

vector <int> e[3001];

int dfs_clock=0,scc_cnt=0;

stack <int> s;

void dfs(int x)
{
    pre[x]=lowlink[x]=++dfs_clock;//tarjan模板，不叨叨。。
    s.push(x);
    for(int i=0;i<e[x].size();i++)
    {
        int u=e[x][i];
        if(!pre[u])
        {
            dfs(u);
            lowlink[x]=min(lowlink[x],lowlink[u]);
        }
        else if(!sccno[u])
        {
            lowlink[x]=min(lowlink[x],pre[u]);
        } 
    }
    if(lowlink[x]==pre[x])
    {
        ++scc_cnt;
        while(1)
        {
            int t=s.top();s.pop();
            sccno[t]=scc_cnt;
            if(buy[t]!=-1)cost[scc_cnt]=min(cost[scc_cnt],buy[t]);//这里统计该强连通分量的最小购买费用
            scclow[scc_cnt]=min(scclow[scc_cnt],t);//这里统计该强连通分量中编号最小的点
            if(t==x)break;
        }
    }
}

int main()
{
    memset(buy,-1,sizeof(buy));
    memset(cost,0x7f,sizeof(cost));
    memset(scclow,0x7f,sizeof(scclow));
    int pd=cost[0];
    scanf("%d%d",&n,&p);
    for(int i=1;i<=p;i++)
    {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        buy[t1]=t2;
    }
    int r;
    scanf("%d",&r);
    for(int i=1;i<=r;i++)
    {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        e[t1].push_back(t2);
    }
    for(int i=1;i<=n;i++)
    {
        if(!pre[i])
        {
            dfs(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<e[i].size();j++)
        {
            if(sccno[i]!=sccno[e[i][j]])
            {
                sccrd[sccno[e[i][j]]]++;
            }
        }
    }
    int ans=0,b=1,ans2=pd;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!sccrd[i])
        {
            if(cost[i]!=pd)ans+=cost[i];//显然当某个强连通分量的最小购买费用等于初始值时，该强连通分量无法被购买
            else
            {
                b=0;
                ans2=min(ans2,scclow[i]);
            }
        }
    }
    if(b)printf("YES\n%d",ans);
    else printf("NO\n%d",ans2);
    return 0;
}