真是一道好题呀~~~~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 %d",ans);return 0;} 75 printf("YES "); 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 }
$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];