【洛谷P1262】 間諜網(wǎng)絡(luò)

題目描述

由于外國間諜的大量滲入，國家安全正處于高度的危機(jī)之中。如果A間諜手中掌握著關(guān)于B間諜的犯罪證據(jù)，則稱A可以揭發(fā)B。有些間諜收受賄賂，只要給他們一定數(shù)量的美元，他們就愿意交出手中掌握的全部情報(bào)。所以，如果我們能夠收買一些間諜的話，我們就可能控制間諜網(wǎng)中的每一分子。因?yàn)橐坏┪覀兇读艘粋€(gè)間諜，他手中掌握的情報(bào)都將歸我們所有，這樣就有可能逮捕新的間諜，掌握新的情報(bào)。

我們的反間諜機(jī)關(guān)提供了一份資料，包括所有已知的受賄的間諜，以及他們?cè)敢馐帐艿木唧w數(shù)額。同時(shí)我們還知道哪些間諜手中具體掌握了哪些間諜的資料。假設(shè)總共有n個(gè)間諜(n不超過3000)，每個(gè)間諜分別用1到3000的整數(shù)來標(biāo)識(shí)。

請(qǐng)根據(jù)這份資料，判斷我們是否有可能控制全部的間諜，如果可以，求出我們所需要支付的最少資金。否則，輸出不能被控制的一個(gè)間諜。

一個(gè)環(huán)內(nèi)的點(diǎn)當(dāng)做一個(gè)點(diǎn)，進(jìn)行有向圖縮點(diǎn)，縮點(diǎn)之后的點(diǎn)權(quán)就是該點(diǎn)包括的點(diǎn)的點(diǎn)權(quán)最小值。

之后重新建圖，對(duì)于每個(gè)點(diǎn)如果他的點(diǎn)權(quán)不是無限大，那么就可以從他開始擴(kuò)展，dfn就可以解決。不過有一點(diǎn)問題，就是如果可以遍歷所有點(diǎn)，那么我們是需要輸出最小代價(jià)的。

那么嘗試hack一下現(xiàn)在的做法。

可以發(fā)現(xiàn)，確實(shí)會(huì)有地方多計(jì)算了點(diǎn)權(quán)。

比如下面這個(gè)圖。

按照當(dāng)前做法，1號(hào)點(diǎn)的點(diǎn)權(quán)10也會(huì)被計(jì)算到答案里，但是我們只需要5號(hào)點(diǎn)的點(diǎn)權(quán)20就可以了。

所以就有了一個(gè)優(yōu)化，就是統(tǒng)計(jì)重新建圖之后每個(gè)點(diǎn)的入度，然后從入度為零的點(diǎn)開始遍歷。

之后再去從入度不為零的點(diǎn)遍歷。

code：

#include <iostream> #include <cstdio> #include <cstring>using namespace std;const int wx=50017;inline int read(){int sum=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}return sum*f; }int tot,st[wx],top,col,n,p,m; int head[wx],h[wx],num,Num; int dfn[wx],low[wx],belong[wx],size[wx],a[wx],v[wx],vis[wx]; int in[wx];struct e{int nxt,to; }edge[wx*2];void add(int from,int to){edge[++num].nxt=head[from];edge[num].to=to;head[from]=num; }void Tarjan(int u){dfn[u]=low[u]=++tot;st[++top]=u;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(!belong[v]){low[u]=min(low[u],dfn[v]);}}if(low[u]==dfn[u]){belong[u]=++col;size[col]++;while(st[top]!=u){belong[st[top]]=col;size[col]++;top--;}top--;} }struct node{int nxt,to; }e[wx*2];void Add(int from,int to){e[++Num].nxt=h[from];e[Num].to=to;h[from]=Num; }void dfs(int u){vis[u]=1;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(vis[v])continue;dfs(v);} }int main(){n=read(); p=read();memset(a,0x3f,sizeof a);memset(v,0x3f,sizeof v);for(int i=1;i<=p;i++){int x; x=read(); a[x]=read();}m=read();for(int i=1;i<=m;i++){int x,y;x=read(); y=read();add(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);for(int i=1;i<=n;i++)v[belong[i]]=min(v[belong[i]],a[i]);for(int u=1;u<=n;u++){for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(belong[v]!=belong[u])in[belong[v]]++,Add(belong[u],belong[v]);}}int ans=0;for(int i=1;i<=col;i++){if(v[i]!=0x3f3f3f3f&&vis[i]==0&&in[i]==0){if(i==1)vis[i]=1;ans+=v[i];dfs(i);}}for(int i=1;i<=col;i++){if(v[i]!=0x3f3f3f3f&&vis[i]==0){if(i==1)vis[i]=1;ans+=v[i];dfs(i);}}for(int i=1;i<=n;i++){if(!vis[belong[i]]){puts("NO");printf("%d\n",i); return 0;}}puts("YES");printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wangxiaodai/p/9826762.html

總結(jié)

以上是生活随笔為你收集整理的缩点【洛谷P1262】 间谍网络的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。