tarjan缩点后找入度为零的强连通分量，加上它的sum即可

但注意到还有NO的可能，

所以大致有两种方法：

1.tarjan之前先来一遍bfs

2.tarjan内加一个数组维护最小编号

貌似前者比较好写qwq

1 #include
      
         2 #include
       
          3 using namespace std;  4 const int N=3010,M=6020;  5 const int novis=-1,nowvis=1,over=0;  6 int value[N],sum[N],flag[N],vis[N],que[M],n;  7 int head[M],next[M],to[M],size;  8 int low[N],dfn[N],color[N],in[N],sig,cnt,top;  9 void bfs(int),uni(int,int),tarjan(),dfs(int),rebuild(); 10 int min(int,int); 11 int main(){ 12     int x,y,p,r,tmp,ans; 13     ans=size=0; 14     memset(vis,0,sizeof(vis)); 15     memset(sum,0,sizeof(sum)); 16     memset(flag,0,sizeof(flag)); 17     memset(in,0,sizeof(in)); 18     scanf("%d %d",&n,&p); 19     for (int i=1;i<=n;i++) 20         value[i]=10000001;//初始化最大值便于后面sum取min 21     for (int i=1;i<=p;i++){ 22         scanf("%d %d",&x,&y); 23         value[x]=y; 24         flag[x]=1; 25     }   26     scanf("%d",&r); 27     for (int i=1;i<=r;i++){ 28         scanf("%d %d",&x,&y); 29         uni(x,y); 30     } 31     for (int i=1;i<=n;i++) 32         if (!vis[i]) bfs(i); 33     for (int i=1;i<=n;i++) 34         if (!vis[i]&&!flag[i]){ 35             printf("NO\n%d",i); 36             return 0; 37         } 38     tarjan();  39     for (int i=1;i<=cnt;i++) 40         if (!in[i]) ans+=sum[i]; 41     printf("YES\n%d",ans); 42     return 0; 43 } 44 void uni(int x,int y){ 45     size++; 46     next[size]=head[x]; 47     head[x]=size; 48     to[size]=y; 49 } 50 void bfs(int x){ 51     int r,l,u,v; 52     l=0;r=1;que[1]=x; 53     while (l<=r){ 54         u=que[++l]; 55         for (int e=head[u];e;e=next[e]){ 56             v=to[e]; 57             if (!vis[v]) que[++r]=v; 58             vis[v]=1; 59         } 60     } 61 } 62 void tarjan(){ 63     memset(flag,novis,sizeof(flag)); 64     sig=cnt=top=0; 65     for (int i=1;i<=n;i++) 66         if (flag[i]==novis) dfs(i); 67     rebuild(); 68 } 69 void dfs(int x){ 70     que[++top]=x; 71     flag[x]=nowvis; 72     low[x]=dfn[x]=++sig; 73     for (int e=head[x];e;e=next[e]){ 74         int y=to[e]; 75         if (flag[y]==novis){ 76             dfs(y); 77             low[x]=min(low[x],low[y]); 78         } 79         else if (flag[y]==nowvis) 80             low[x]=min(low[x],dfn[y]); 81     } 82     if (low[x]==dfn[x]){ 83         cnt++;int t; 84         if (!sum[cnt]) sum[cnt]=20001;  85         do{ 86             t=que[top--]; 87             flag[t]=over; 88             color[t]=cnt; 89             sum[cnt]=min(sum[cnt],value[t]); 90         }while (t!=x); 91     } 92 } 93 void rebuild(){
    //入度   94     for (int u=1;u<=n;u++) 95         for (int e=head[u];e;e=next[e]){ 96             int v=to[e]; 97             if (color[u]!=color[v])  98                 in[color[v]]++; 99         }100 }101 int min(int x,int y){102     return x