M_sea

洛谷1262 间谍网络
Luogu分析显然,对于一个强联通分量,只需收买一个人就可以控制所有人。显然,收买价格最小的人。然后考虑缩点,将每...
扫描右侧二维码阅读全文
23
2018/10

洛谷1262 间谍网络

Luogu

分析

显然,对于一个强联通分量,只需收买一个人就可以控制所有人。显然,收买价格最小的人。

然后考虑缩点,将每个强联通分量的权设为内部最小的价格。

缩完点后这张图就变成了一个DAG。收买入度为0的点即可。

此外,若有一个不能被收买的入度为0的点,则无解。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

struct Edge {
    int v,nxt;
    Edge() { this->v=this->nxt=0; }
};

int x[8010],y[8010];
Edge e[8010];
int head[3010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int val[3010];
int dfn[3010],low[3010];
int sta[3010],top=0;
bool in_stack[3010];
int dfs_clock=0;

int tot=0;
int belong[3010];
int sum[3010];

inline void Tarjan(int u) {
    low[u]=dfn[u]=++dfs_clock;
    sta[++top]=u; in_stack[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (in_stack[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) {
        ++tot; int now;
        sum[tot]=2147483647;
        while (1) {
            now=sta[top--];
            belong[now]=tot;
            in_stack[now]=0;
            sum[tot]=min(sum[tot],val[now]);
            if (now==u) break;
        }
    }
}

int ind[3010];

int main() {
    n=read(); int tmpn=read();
    memset(val,0x7f,sizeof(val));
    int INF=val[0];
    for (re int i=1;i<=tmpn;i++) {
        int id=read();
        val[id]=read();
    }
    m=read();
    for (re int i=1;i<=m;i++) {
        x[i]=read(),y[i]=read();
        addEdge(x[i],y[i]);
        ind[y[i]]++;
    }
    for (re int i=1;i<=n;i++)
        if (val[i]==INF&&!ind[i]) {
            printf("NO\n%d\n",i);
            return 0;
        }
    for (re int i=1;i<=n;i++)
        if (!dfn[i]) Tarjan(i);
    memset(ind,0,sizeof(ind));
    for (re int i=1;i<=m;i++)
        if (belong[x[i]]!=belong[y[i]]) ind[belong[y[i]]]++;
    int ans=0;
    for (re int i=1;i<=tot;i++)
        if (!ind[i]) ans+=sum[i];
    printf("YES\n%d\n",ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 52 PM

发表评论