【题解】洛谷P1262 间谍网络 （强连通分量缩点）

洛谷P1262：https://www.luogu.org/problemnew/show/P1262

思路

一看题目就知道是强连通分量缩点

当图中有强连通分量时 将其缩点 

我们可以用dfn数组判断是否可以达到所有人都可以控制

到最后图中可能有如下2种情况

First 整个图为一个强连通分量 ans即是能贿赂的最小值

Second 当图中有链时 贿赂链的第一个人即可取得最小值

代码

#include<iostream> #include<cstring> using namespace std; #define maxn 3010 #define INF 1e9+7 int n,r,p,top,num,cnt,col,ans; int money[maxn],h[maxn*10],de[maxn],st[maxn],dfn[maxn],low[maxn],co[maxn],minn[maxn]; bool vis[maxn]; struct Edge { int to; int next; }e[maxn*20]; void add(int u,int v) { e[++cnt].to=v; e[cnt].next=h[u]; h[u]=cnt; } void read() { cin>>n>>p; for(int i=1;i<=n;i++) minn[i]=money[i]=INF;//初始化 for(int i=1;i<=p;i++) { int x,y; cin>>x>>y; money[x]=y; } cin>>r; for(int i=1;i<=r;i++) { int x,y; cin>>x>>y; add(x,y); } } void Tarjan(int u) { dfn[u]=low[u]=++num; st[++top]=u; vis[u]=1; for(int i=h[u];i;i=e[i].next) { int v=e[i].to; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } else if(vis[v]) { low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]) { col++; while(st[top+1]!=u) { co[st[top]]=col; vis[st[top]]=0; minn[col]=min(minn[col],money[st[top]]);//计算每个强连通分量中的最小花费 top--; } } } int main() { read(); for(int i=1;i<=n;i++) if(!dfn[i]&&money[i]!=INF) Tarjan(i);//能被贿赂的人才可以缩点 for(int i=1;i<=n;i++) if(!dfn[i])//如果dfn为0说明没有被控制 { cout<<"NO"<<endl<<i; return 0; } for(int i=1;i<=n;i++)//统计入度 for(int j=h[i];j;j=e[j].next) if(co[i]!=co[e[j].to]) de[co[e[j].to]]++; for(int i=1;i<=col;i++)//如果入度为0 即是一条链 if(!de[i]) ans+=minn[i]; cout<<"YES"<<endl<<ans; } View Code

 

转载于:https://www.cnblogs.com/BrokenString/p/9708932.html