FZU 強連通分量縮點 + 入度為零最小代價

題目大意

• 有向圖 N 點，每點有購買成本（部分點無成本 = 不可購買）。
• 購買一點後，其可達點全部「染色」。
• 求最小總成本使所有點染色；若不可能，輸出不可染色點中編號最小者。

解法：SCC 縮點 + DAG 入度為零

1. Tarjan/Kosaraju 求強連通分量（SCC），同一 SCC 內任意點相互可達，只需購買成本最小的點。
2. 縮點得 DAG，每個 SCC 節點權重 = 內部最小成本（若全不可購買則權重 = INF）。
3. DAG 中入度為 0 的節點無法被其他節點染色，必須直接購買。
    若某入度 0 節點權重 = INF → 無解，輸出該 SCC 內最小原始編號。
    否則答案 = 所有入度 0 節點權重之和。

完整代碼

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 3010, MAXM = 8010;
struct Edge { int to, next; } E[MAXM];
int head[MAXN], ecnt;
void addEdge(int u, int v) { E[ecnt] = {v, head[u]}; head[u] = ecnt++; }

int N, P, M;
int cost[MAXN];
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx, sccCnt;
int sccId[MAXN], inDeg[MAXN], sccMinCost[MAXN];
bool inStk[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u; inStk[u] = true;
    for (int e = head[u]; ~e; e = E[e].next) {
        int v = E[e].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (inStk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++sccCnt;
        int v;
        do {
            v = stk[top--];
            sccId[v] = sccCnt;
            inStk[v] = false;
            sccMinCost[sccCnt] = min(sccMinCost[sccCnt], cost[v]);
        } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> N) {
        fill(head, head+N+1, -1); ecnt = 0;
        fill(cost, cost+N+1, INF);
        cin >> P;
        for (int i=0;i> id >> c; cost[id] = c; }
        cin >> M;
        for (int i=0;i> u >> v; addEdge(u,v); }
        fill(dfn, dfn+N+1, 0); fill(inStk, inStk+N+1, false);
        fill(sccMinCost, sccMinCost+N+1, INF);
        idx = top = sccCnt = 0;
        for (int i=1;i<=N;++i) if (!dfn[i]) tarjan(i);
        fill(inDeg, inDeg+sccCnt+1, 0);
        for (int u=1; u<=N; ++u)
            for (int e=head[u]; ~e; e=E[e].next) {
                int v = E[e].to;
                if (sccId[u] != sccId[v]) ++inDeg[sccId[v]];
            }
        bool ok = true; int minId = INF, ans = 0;
        for (int i=1; i<=sccCnt; ++i) {
            if (inDeg[i] == 0) {
                if (sccMinCost[i] == INF) { ok = false; }
                else ans += sccMinCost[i];
            }
        }
        if (!ok) {
            for (int i=1; i<=N; ++i)
                if (inDeg[sccId[i]] == 0 && cost[i] == INF) { minId = i; break; }
            cout << "NO " << minId << "\n";
        } else {
            cout << "YES " << ans << "\n";
        }
    }
    return 0;
}

複雜度

• Tarjan O(N+M)。
• 縮點統計 O(N+M)。
• 總體線性，N ≤ 3000, M ≤ 8000 極快。