题目：https://www.luogu.org/problemnew/show/P1262
首先，一个强连通分量里有一个点被控制则所有点都被控制，所以先 tarjan 缩点，记一下每个连通块中能被收买的人的最小价钱，和整个连通块的点的最小 id；
然后如果有入度为0的点不能被收买，则输出 NO，找最小 id 时注意要找它指向的所有点，又不包括中间可以被收买的；
否则就是 YES，花费就是入度为0的点的最小代价之和。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int const xn=3005,xm=8005,inf=0x3f3f3f3f; int n,m,hd[xn],ct,to[xm],nxt[xm],fr[xm],dfn[xn],low[xn],tim,sta[xn],top; int deg[xn],col[xn],cr,hd2[xn],ct2,to2[xm],nxt2[xm],p,w[xn],ans,mn[xn],mi[xn]; bool vis[xn]; void add(int x,int y){to[++ct]=y; fr[ct]=x; nxt[ct]=hd[x]; hd[x]=ct;} void add2(int x,int y){to2[++ct2]=y; nxt2[ct2]=hd2[x]; hd2[x]=ct2;} int rd() { int ret=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=0; ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘)ret=(ret<<3)+(ret<<1)+ch-‘0‘,ch=getchar(); return f?ret:-ret; } void tarjan(int x) { dfn[x]=low[x]=++tim; vis[x]=1; sta[++top]=x; for(int i=hd[x],u;i;i=nxt[i]) { if(!dfn[u=to[i]])tarjan(u),low[x]=min(low[x],low[u]); else if(vis[u])low[x]=min(low[x],dfn[u]); } if(dfn[x]==low[x]) { int y; cr++; mn[cr]=inf; mi[cr]=inf; while((y=sta[top])!=x) col[y]=cr,vis[y]=0,top--,mn[cr]=min(mn[cr],w[y]),mi[cr]=min(mi[cr],y); col[x]=cr; vis[x]=0; top--; mn[cr]=min(mn[cr],w[x]); mi[cr]=min(mi[cr],x); } } int find(int x) { int ret=mi[x]; for(int i=hd2[x];i;i=nxt2[i]) { if(mn[to2[i]]!=inf)break;//! ret=min(ret,find(to2[i])); } return ret; } int main() { n=rd(); p=rd(); memset(w,0x3f,sizeof w); for(int i=1,id;i<=p;i++)id=rd(),w[id]=rd(); m=rd(); for(int i=1,x,y;i<=m;i++) { x=rd(); y=rd(); add(x,y); } //add(x=rd(),y=rd()),printf("add(%d,%d)\n",x,y); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1,u,v;i<=ct;i++) if((u=col[fr[i]])!=(v=col[to[i]]))add2(u,v),deg[v]++; bool fl=0; int id=inf; for(int i=1;i<=cr;i++) { if(deg[i])continue; if(mn[i]==inf)fl=1,id=min(id,find(i)); else ans+=mn[i]; } if(fl)printf("NO\n%d\n",id); else printf("YES\n%d\n",ans); return 0; }
原文：https://www.cnblogs.com/Zinn/p/9705793.html