思路：
①在 Tarjan 的基础上加一个 belong 记录每个点属于哪个强连通分量。
②存图完成后，暴力地遍历全图，查找是否要间谍不愿受贿。
inline void dfs(int u){ if(vis[u]) return ; vis[u]=true,tot++; for(int i=head[u];i;i=t[i].nex) dfs(t[i].to);}//遍历 遍历完后，看看那个间谍没被搜索过（vis数组记录），就把那个不受贿的间谍抓出来。
③如果所有的间谍都愿意受贿，就继续。可以开一个smon数组，记录每个强连通分量中间谍愿意受贿的最小的钱数。结合belong数组（因为一个强连通分量只要让一个间谍受贿，就能拖出这个强连通分量中所有的间谍。），用ans记录所需总的钱数，输出。
AC代码：
#include#include #include #include #include #include #include #include #include #include using namespace std;#define maxn 3001#define maxm 9000000#define INF 0x3f3f3f3fint n,m,cnt,tot,dfn[maxn],low[maxn],sta[maxn],belong[maxn],rd[maxn],smon[maxn],mon[maxn];//belong记录每个点属于哪个强连通分量，rd记录每个点的入度，smon记录间谍网络中每个连通块的最小受贿的钱，mon记录每个间谍的受贿所需的钱 bool vis[maxn];struct hh{ int nex,to;}t[maxm];int tto=0,head[maxm];//链式前向星inline void add(int nex,int to){ t[++tto].nex=head[nex]; t[tto].to=to; head[nex]=tto;}//存图部分inline void dfs(int u){ if(vis[u]) return ; vis[u]=true,tot++; for(int i=head[u];i;i=t[i].nex) dfs(t[i].to);}//遍历初始图inline int read(){ char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); int xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs;}//快读 inline void tarjan(int u)//tarjan的模板 { dfn[u]=low[u]=++tot; vis[u]=true; sta[++cnt]=u; for(int i=head[u];i;i=t[i].nex) { int v=t[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]) { smon[u]=INF; do { vis[sta[cnt]]=false; belong[sta[cnt]]=u; smon[u]=min(smon[u],mon[sta[cnt]]);//取连通块中间谍受贿的最小值，更新smon cnt--; }while(sta[cnt+1]!=u); }}int main(){ n=read();m=read(); for(int i=1;i<=n;i++) mon[i]=INF;//不受贿的间谍设为一个极大值 for(int i=1;i<=m;i++) { int x,y; x=read();y=read(); mon[x]=y;//读入受贿间谍要的钱 } 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(mon[i]!=INF) dfs(i);//遍历全图，确定是否有间谍不愿被收买 for(int i=1;i<=n;i++) { if(!vis[i])//找到那个不愿被收买的间谍 { printf("NO\n%d",i); return 0;//直接结束程序 } } tot=0; for(int i=1;i<=n;i++) vis[i]=0;//初始化vis for(int i=1;i<=n;i++) if(mon[i]!=INF && !dfn[i]) tarjan(i);//tarjan记录强连通分量数，及每个强连通分量的smon for(int i=1;i<=n;i++) { for(int j=head[i];j;j=t[j].nex) { if(belong[i]!=belong[t[j].to]) rd[belong[t[j].to]]++;//统计每个强连通分量的入度 （找入度为0的点） } } int ans=0; for(int i=1;i<=n;i++) if(belong[i]==i && !rd[i]) ans+=smon[i];//入度为0的点，即为连通块的起点，且smon已经被更新，直接加入答案 printf("YES\n%d",ans);//输出 return 0;}
其实也没有想象中的那么暴力，手写栈+inline后，最慢的一个点都只用了4ms。