Loading...

洛谷P1262 间谍网络

check评论:0 条 remove_red_eye浏览量:426 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-07-30

该题目并不需要强连通分量,用一种类似并查集的思想即可,看它的祖先是否受贿即可判断它,很简单就不细说了
code:

#include <bits/stdc++.h> 
using namespace std;
const int maxn=3010;
const int maxr=8010;
int n,p,r,ans;
int a,b;
int head[maxn],cnt;
int fa[maxn],finds[maxn];
struct edge
{
    int next,to;
}e[maxr];
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct nate
{
    int s,v;
}d[maxn];
bool cmp(const nate&x,const nate&y)
{
    return x.v<y.v;
}
void dfs(int k,int s)
{
    if(fa[k]) 
    {
        finds[fa[k]]--;
    }
    fa[k]=s;
    finds[s]++;
    for(int i=head[k];i;i=e[i].next)
    {
        int v=e[i].to;
        if(fa[v]!=s) 
        {
            dfs(v,s);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=p;i++)
    {
        scanf("%d%d",&a,&b);
        d[i].s=a;
        d[i].v=b;
    }
    sort(d+1,d+p+1,cmp);
    scanf("%d",&r);
    for(int i=1;i<=r;i++)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    for(int i=1;i<=p;i++)
    {
        int u=d[i].s;
        if(fa[u]) 
        {
            for(int j=head[u];j;j=e[j].next)
            {
                int v=e[j].to;
                if(!fa[v])
                {
                    dfs(v,i);
                    break;
                }
            }    
        }
        else 
        {
            dfs(u,i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(!fa[i])
        {
            printf("NO\n%d\n",i);
            return 0;
        }
    }
    for(int i=1;i<=p;i++) 
    {
        if(finds[i]) 
        {
            ans+=d[i].v;
        }
    }
    printf("YES\n%d\n",ans);
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名