缩点

缩点

缩点就是把有向图里的一个强连通分量当成是一个点来处理，因为一个强连通分量里的点都可以互相到达，所以把他们当成一个点，权值为所有点权值之和，这样就可以把一个有向图缩成一个DAG(有向无环图)。注意强连通分量之间的边。

P3387 【模板】缩点

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e4+5, maxm = 1e5+5;
int n, m;
int val[maxn];
struct edge{
    int from, to, next;
}e[maxm];
int head[maxn], tot;
int dfn[maxn], low[maxn], num, vis[maxn];
stack<int> sta;

vector<int> G[maxn];
int val2[maxn], dp[maxn];
int getDP(int u){
    if (dp[u]!=-1)  return dp[u];
    dp[u] = val2[u];
    int tmp = 0;
    for (int i=0; i<G[u].size(); i++)
        tmp = max(tmp, getDP(G[u][i]));
    dp[u] += tmp;
    return dp[u];
}

void Tarjan(int u){
    dfn[u] = low[u] = ++num;
    sta.push(u);    vis[u] = 1;
    for (int i=head[u]; i; i=e[i].next){
        if (!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u] = min(low[u], low[e[i].to]);
        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);
    }
    if (low[u]==dfn[u]){
        while (sta.top()!=u){
            vis[sta.top()] = 0;
            low[sta.top()] = low[u];
            sta.pop();
        }
        vis[sta.top()] = 0;
        sta.pop();
    }
    return;
}
inline void add(int from, int to){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
    head[from] = tot;
}
int main(){
    int from, to;
    scanf ("%d %d", &n, &m);
    for (int i=1; i<=n; i++)    scanf ("%d", val+i);
    for (int i=1; i<=m; i++){
        scanf ("%d %d", &from, &to);
        add(from, to);
    }
    for (int i=1; i<=n; i++)    if (!dfn[i])
        Tarjan(i);
    for (int i=1; i<=tot; i++)  if (low[e[i].from] != low[e[i].to])
        G[low[e[i].from]].push_back(low[e[i].to]);
    for (int i=1; i<=n; i++)    val2[low[i]] += val[i];
    memset (dp, -1, sizeof dp);
    int ans = 0;
    for (int i=1; i<=n; i++)
        ans = max(ans, getDP(i));
    printf ("%d", ans);
    return 0;
}

P3627 [APIO2009]抢掠计划

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 5e5+5;
struct edge{
    int from, to, next;
}e[maxn];
int n, m, tot, S, P;
int head[maxn], val[maxn], isbar[maxn];
int dfn[maxn], low[maxn], num, vis[maxn];
stack<int> sta;

vector<int> G[maxn];
int dp[maxn];
int getDP(int u){
    if (dp[u]!=-1)  return dp[u];
    int tmp = 0;
    for (int i=0; i<G[u].size(); i++){
        tmp = max(tmp, getDP(G[u][i]));
    }
    if (tmp || isbar[u])    dp[u] = val[u] + tmp;
    else    dp[u] = 0;
    return dp[u];
}

void Tarjan(int u){
    dfn[u] = low[u] = ++num;
    sta.push(u);    vis[u] = 1;
    for (int i=head[u]; i; i=e[i].next){
        if (!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u] = min(low[u], low[e[i].to]);
        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);
    }
    if (low[u]==dfn[u]){
        while (sta.top()!=u){
            vis[sta.top()] = 0;
            low[sta.top()] = low[u];
            sta.pop();
        }
        vis[sta.top()] = 0;
        sta.pop();
    }
    return;
}

inline void add(int from, int to){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
    head[from] = tot;
    return;
}
inline int read(){
    int x=0;    char ch = getchar();
    while (ch<'0' || ch>'9')    ch = getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x;
}
int main(){
    int from, to;
    n = read(), m = read();
    for (int i=1; i<=m; i++){
        from = read(), to = read();
        add(from, to);
    }
    for (int i=1; i<=n; i++)    if (!dfn[i])
        Tarjan(i);
    for (int i=1; i<=tot; i++)    if (low[e[i].from] != low[e[i].to]){
        G[low[e[i].from]].push_back(low[e[i].to]);
    }
    for (int i=1; i<=n; i++){
        val[low[i]] += read();
    }
    S = read(), P = read();
    for (int i=1; i<=P; i++){
        isbar[low[read()]] = 1;
    }
    memset(dp, -1, sizeof dp);
    printf ("%d", getDP(low[S]));
    return 0;
}

P2002 消息扩散

#include <cstdio>
#include <algorithm>
#include <stack>
#include <cstring>
using namespace std;
const int maxn = 5e5+5;
struct edge{
    int from, to, next;
}e[maxn];
int n, m, tot;
int head[maxn];
int dfn[maxn], low[maxn], num, vis[maxn];
int in[maxn];
stack<int> sta;

void Tarjan(int u){
    dfn[u] = low[u] = ++num;
    sta.push(u);    vis[u] = 1;
    for (int i=head[u]; i; i=e[i].next){
        if (!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u] = min(low[u], low[e[i].to]);
        }else if (vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]);
    }
    if (low[u]==dfn[u]){
        while (sta.top()!=u){
            vis[sta.top()] = 0;
            low[sta.top()] = low[u];
            sta.pop();
        }
        vis[sta.top()] = 0;
        sta.pop();
    }
    return;
}

inline void add(int from, int to){
    tot++;
    e[tot].from = from, e[tot].to = to, e[tot].next = head[from];
    head[from] = tot;
    return;
}
inline int read(){
    int x=0;    char ch = getchar();
    while (ch<'0' || ch>'9')    ch = getchar();
    while (ch>='0' && ch<='9'){
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x;
}
int main(){
    int from, to;
    n = read(), m = read();
    for (int i=1; i<=m; i++){
        from = read(), to = read();
        if (from==to)   continue;
        add(from, to);
    }
    for (int i=1; i<=n; i++)    if (!dfn[i])
        Tarjan(i);
    int ans = 0;
    for (int i=1; i<=n; i++)    vis[low[i]] = 1;
    for (int i=1; i<=m; i++)    if (low[e[i].from]!=low[e[i].to]){
        in[low[e[i].to]]++;
    }
    for (int i=1; i<=n; i++)    if (vis[i] && !in[i])
        ans++;
    printf ("%d", ans);
    return 0;
}