题目大意：给出一个张有向图，和N个点的价值（买了这个点后，以这个点出发的所能遍及的点都会被染色）

问至少要花费多少钱去买点，才能使得这张图的所有点都被染色
如果不能所有的点都染色，输出不能染色点的最小值

解题思路：先求出所有的强连通分量，接着求出每个强连通分量内所有点的最少价值，因为同一个强连通分量内的点只需要购买一个就可以全部染色了
接着缩点，用桥连接起来，形成一张新的图(以下所说的点都是强连通分量的缩点)
找出所有入度为0的点，因为入度为0的点是无法通过别的点进行染色的，所以只能买入度为0的点

#include 
   
     #include 
    
      #define N 3010 #define M 8010 #define INF 0x3f3f3f3f #define min(a,b) ((a) < (b) ? (a) : (b)) struct Edge{ int from, to, next; }E[M]; int n, tot, p, m, dfs_clock, scc_cnt, top; int head[N], cost[N], pre[N], sccno[N], stack[N], lowlink[N], in[N], value[N]; void AddEdge(int u, int v) { E[tot].to = v; E[tot].from = u; E[tot].next = head[u]; head[u] = tot++; } void init() { memset(cost, 0x3f, sizeof(cost)); scanf(%d, &p); int No, money; for (int i = 0; i < p; i++) { scanf(%d%d, &No, &money); cost[No] = money; } scanf(%d, &m); memset(head, -1, sizeof(head)); tot = 0; int u, v; for (int i = 0; i < m; i++) { scanf(%d%d, &u, &v); AddEdge(u, v); } } void dfs(int u) { pre[u] = lowlink[u] = ++dfs_clock; stack[++top] = u; int v; for (int i = head[u]; i != -1; i = E[i].next) { v = E[i].to; if (!pre[v]) { dfs(v); lowlink[u] = min(lowlink[u], lowlink[v]); } else if (!sccno[v]) { lowlink[u] = min(lowlink[u], pre[v]); } } if (lowlink[u] == pre[u]) { scc_cnt++; while (1) { v = stack[top--]; sccno[v] = scc_cnt; if (v == u) break; } } } void solve() { memset(pre, 0, sizeof(pre)); memset(sccno, 0, sizeof(sccno)); dfs_clock = scc_cnt = top = 0; for (int i = 1; i <= n; i++) if (!pre[i]) dfs(i); for (int i = 1; i <= scc_cnt; i++) { value[i] = INF; in[i] = 1; } for (int i = 1; i <= n; i++) { value[sccno[i]] = min(value[sccno[i]], cost[i]); } int u, v, minid; for (int i = 0; i < tot; i++) { u = sccno[E[i].from]; v = sccno[E[i].to]; if (u != v) { in[v] = 0; } } bool flag = false; for (int i = 1; i <= n; i++) { u = sccno[i]; if (in[u] && value[u] == INF) { minid = i; flag = true; break; } } if (flag) { printf(NO %d , minid); return ; } int ans = 0; for (int i = 1; i <= scc_cnt; i++) { if (in[i]) ans += value[i]; } printf(YES %d , ans); } int main() { while (scanf(%d, &n) != EOF) { init(); solve(); } return 0; } 
    
   

?