显然可以把所有间谍的关系建一个图
如果A间谍手中掌握着关于B间谍的犯罪证据，那就从A连一条边到B
如果贿赂了一个间谍，那么整个联通块的间谍肯定都被控制
那就先把图缩成DAG
如果控制了一个块，那么这个块后面所有的块都能被控制
为了控制所有块，一定要贿赂没有入度的块，因为它不能被其它块控制到
那就Tarjan然后贿赂所有入度为0的块，答案就是总花费
要注意判断是否能控制所有块
如果一个块不能被贿赂，并且没有块可以控制它，那么它就不能被控制
那么我们缩点的时候可以只从能被贿赂的间谍开始缩
全部缩完后如果有间谍不处于任何联通块，那么ta就不能被控制
for一遍就好了
至于控制一个块的花费就是最便宜的那个间谍，Tarjan时可以一起处理
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=3007,M=2e5+7; int n,m,t; int val[N]; int fir[N],from[M],to[M],cnt; inline void add(int &a,int &b) { from[++cnt]=fir[a]; fir[a]=cnt; to[cnt]=b; } //Tarjan模板 int dfn[N],low[N],be[N],st[M],cnt2,_top,dfn_clock,miv[N];//miv[i]是块i的最小费用 void Tarjan(int x) { dfn[x]=low[x]=++dfn_clock; st[++_top]=x; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(!dfn[v]) Tarjan(v),low[x]=min(low[x],low[v]); else if(!be[v]) low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { cnt2++; while(st[_top]!=x) { miv[cnt2]=min(miv[cnt2],val[st[_top]]); be[st[_top--]]=cnt2; } miv[cnt2]=min(miv[cnt2],val[st[_top]]); be[st[_top--]]=cnt2; } } int du[N]; int main() { memset(val,0x7f,sizeof(val)); memset(miv,0x7f,sizeof(miv));//初始都不能贿赂 int a,b; cin>>n>>m; for(int i=1;i<=m;i++) { a=read(); b=read(); val[a]=b; } cin>>t; for(int i=1;i<=t;i++) { a=read(); b=read(); add(a,b); } for(int i=1;i<=n;i++) if(!dfn[i]&&val[i]!=val[0]) Tarjan(i);//只从能被贿赂的间谍开始缩点 for(int i=1;i<=n;i++) if(!be[i]) { printf("NO %d",i);//找到的第一个间谍就是编号最小的间谍 return 0; } printf("YES "); for(int i=1;i<=n;i++) for(int j=fir[i];j;j=from[j]) if(be[i]!=be[to[j]]) du[be[to[j]]]++;//算一波入度 int ans=0; for(int i=1;i<=cnt2;i++) if(!du[i]) ans+=miv[i];//所有入度为0的块都要贿赂 printf("%d",ans); return 0; }