Luogu P1262 间谍网络 【强连通分量/缩点】By cellur925

题目传送门

真是一道好题呀~~~~qwq

知道这题是tarjan，但是想了很久怎么用上强连通分量。因为样例们...它显然并不是一个强联通分量！

（被样例迷惑的最好例子）

然后...就没有然后了...感觉自己被欺骗了。脑补了一些别的做法，向题解低头。

 

---

 

$Sol$

这个时候我们其实需要一些冷静分析。分情况讨论。

• 判断无解性。什么时候无解？当存在一个间谍既不能被收买也没有被其他间谍掌握自己的资料，则无解。我们在主函数进行tarjan操作时，是从能被收买的间谍开始找环的。那么最后递归结束，当存在间谍没被访问($!dfn[i]$)，那么问题无解。
• 那么有解的情况呢？这时条件等价于所有的间谍都能直接或间接地被收买或被掌握。这时分两种情况：正如我思考时，分有环和无环两种情况。没还，资金就需要给那个没有入度的间谍；有环，我们就把资金给那个在环里资金最小的间谍（因为在一个强联通分量中，所以一个点可达另一个节点，这个环就解决了，我们肯定想要给资金需要少的。这部分处理可在tarjan中顺便求出）。有环的情况我们通常对它进行缩点，成为一个有向无环图，也就变成了无环的情况。
• 小结。缩点->DAG这是比较套路的东西了，大多数时候我们其实不用新建一个图，而都是在统计入度（这种场合较多）。
• 结论。还是我太弱了qwq。

---

 

$Code$

1 #include<cstdio> 2 #include<algorithm> 3 #include<stack> 4 #include<cstring> 5 #define maxn 4000 6 7 using namespace std; 8 9 int n,p,tot,r,dfs_clock,scc_cnt,ans; 10 int head[maxn],val[maxn],rdu[maxn],dfn[maxn],low[maxn],scc[maxn],price[maxn]; 11 bool buy[maxn]; 12 struct node{ 13 int to,next; 14 }edge[maxn*2]; 15 stack<int>s; 16 17 void add(int x,int y) 18 { 19 edge[++tot].to=y; 20 edge[tot].next=head[x]; 21 head[x]=tot; 22 } 23 24 void tarjan(int u) 25 { 26 dfn[u]=low[u]=++dfs_clock; 27 s.push(u); 28 for(int i=head[u];i;i=edge[i].next) 29 { 30 int v=edge[i].to; 31 if(!dfn[v]) 32 { 33 tarjan(v); 34 low[u]=min(low[u],low[v]); 35 } 36 else if(!scc[v]) low[u]=min(low[u],dfn[v]); 37 } 38 if(dfn[u]==low[u]) 39 { 40 scc_cnt++; 41 while(1) 42 { 43 int x=s.top();s.pop(); 44 scc[x]=scc_cnt; 45 val[scc_cnt]=min(val[scc_cnt],price[x]); 46 if(x==u) break; 47 } 48 } 49 } 50 51 int main() 52 { 53 scanf("%d%d",&n,&p); 54 memset(price,127,sizeof(price)); 55 memset(val,127,sizeof(val)); 56 for(int i=1;i<=p;i++) 57 { 58 int x=0; 59 scanf("%d",&x); 60 buy[x]=1; 61 scanf("%d",&price[x]); 62 } 63 scanf("%d",&r); 64 for(int i=1;i<=r;i++) 65 { 66 int x=0,y=0; 67 scanf("%d%d",&x,&y); 68 add(x,y); 69 } 70 for(int i=1;i<=n;i++) 71 if(!dfn[i]&&buy[i]) tarjan(i); 72 for(int i=1;i<=n;i++) 73 if(!dfn[i]){ans=i;break;} 74 if(ans) {printf("NO\n%d",ans);return 0;} 75 printf("YES\n"); 76 for(int x=1;x<=n;x++) 77 for(int i=head[x];i;i=edge[i].next) 78 { 79 int y=edge[i].to; 80 if(scc[x]==scc[y]) continue; 81 rdu[scc[y]]++; 82 } 83 for(int i=1;i<=scc_cnt;i++) 84 if(rdu[i]==0) ans+=val[i]; 85 printf("%d",ans); 86 return 0; 87 } View Code

---

$Warning$

那个最后缩点的时候这个地方比较容易写错。最后是在$scc_cnt$上进行操作的。

for(int x=1;x<=n;x++)for(int i=head[x];i;i=edge[i].next){int y=edge[i].to;if(scc[x]==scc[y]) continue;rdu[scc[y]]++;}for(int i=1;i<=scc_cnt;i++)if(rdu[i]==0) ans+=val[i];

 

转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9733577.html

总结

以上是生活随笔为你收集整理的Luogu P1262 间谍网络 【强连通分量/缩点】By cellur925的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。