AcWing 1192. 奖金 [一题三解]

题目传送门

一、三种方法总结

• 边权无限制 差分约束 (\(spfa\)) \(O(n*m)\)
  判断正环：一共\(1\)(超级源点)+\(n\),按\(BellmanFord\)思想，应该最多\(n\)次入队列，结果入队列的数次大于等于\(n+1\),就是有正环

• 边权非负 \(targan\) \(O(n+m)\)
  判断正环：同一个强连通分量内的边的权值只能为\(0\)，否则存在正环

• 边权大于\(0\)，拓扑排序 \(O(n+m)\)
  判断正环：拓扑序列中点的数量是不是等于 \(1\)(超级源点)+\(n\) 来决定是不是拓扑图

二、拓扑排序+递推极值

#include 
using namespace std;
const int N = 10010, M = 30010;

int din[N];  //记录每个节点入度
int dist[N]; //记录每个节点距离起点的最小值
int n, m;
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
vector path;
bool topsort() {
    queue q;
    for (int i = 0; i <= n; i++)
        if (!din[i]) q.push(i);

    while (q.size()) {
        int t = q.front();
        q.pop();
        path.push_back(t);
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            //删去t --> j这条边，相当于j节点入度 - 1
            din[j]--;
            if (din[j] == 0) q.push(j);
        }
    }
    return path.size() == n + 1; //加上虚拟源点
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        add(b, a, 1); /**  a >= b + 1 */
        din[a]++;
    }

    //建一个超级源点0号点
    for (int i = 1; i <= n; ++i) { /** a >= xo + 100 */
        add(0, i, 100);
        din[i]++;
    }

    memset(dist, -0x3f, sizeof dist);

    if (topsort()) {
        dist[0] = 0;
        //根据拓扑序列求一遍最长路
        for (int i = 0; i <= n; ++i) {
            int j = path[i]; //队列中0 ~ n这个序列就是拓扑序
            //枚举节点i所有邻接的节点，找出最大的转移
            for (int k = h[j]; ~k; k = ne[k])
                if (dist[e[k]] < dist[j] + w[k])
                    dist[e[k]] = dist[j] + w[k];
        }
        int res = 0;
        for (int i = 1; i <= n; i++) res += dist[i];
        cout << res << endl;
    } else
        puts("Poor Xed");
    return 0;
}

三、差分约束(spfa求最长路+判断正环)

#include 
using namespace std;
const int N = 10010, M = 30010;
int din[N];  //记录每个节点入度
int dist[N]; //记录每个节点距离起点的最小值
int cnt[N];  // cnt[i]记录以节点i为终点的路径的边数
bool st[N];
queue q;
int n, m;
//邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa() {
    memset(dist, -0x3f, sizeof dist);
    q.push(0);
    st[0] = true;
    dist[0] = 0;

    while (q.size()) {
        int t = q.front();
        q.pop();
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] < dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                //判断是不是存在正环
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n + 1) return false;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        add(b, a, 1); /**  a >= b + 1 */
    }

    //建一个超级源点0号点
    for (int i = 1; i <= n; ++i) /** a >= xo + 100 */
        add(0, i, 100);

    if (spfa()) {
        int res = 0;
        for (int i = 1; i <= n; ++i) res += dist[i];
        cout << res << endl;
    } else
        puts("Poor Xed");
    return 0;
}

四、强连通分量缩点之后递推求最长路

#include 
using namespace std;
const int N = 10010, M = 60010;

int dnt[N], low[N];
bool in_sta[N]; //记录是否在栈中
int dist[N];    //记录强连通分量距离起点的距离
stack sta;
int id[N];       //记录每个节点的强连通分量的编号
int scc_size[N]; //记录强连通分量的节点个数
int timestamp;
int scc_cnt; //记录强连通分量的编号
int n, m;

int h[N], hs[N], ne[M], e[M], w[M], idx; // hs[u]为强连通分量建的图的表头
void add(int h[], int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void tarjan(int u) {
    low[u] = dnt[u] = ++timestamp;
    sta.push(u);
    in_sta[u] = true;

    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dnt[j]) {
            tarjan(j);
            //有可能存在反向边遍历回祖宗节点
            low[u] = min(low[u], low[j]);
        } else if (in_sta[j])
            //有可能存在横向边和遍历回之前遍历过的节点
            low[u] = min(low[u], dnt[j]);
    }

    if (low[u] == dnt[u]) {
        int y;
        ++scc_cnt;
        do {
            y = sta.top();
            sta.pop();
            id[y] = scc_cnt;
            in_sta[y] = false;
            scc_size[scc_cnt]++;
        } while (y != u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    memset(hs, -1, sizeof hs);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        add(h, b, a, 1); /**  a >= b + 1 */
    }

    //建一个超级源点0号点
    for (int i = 1; i <= n; ++i) /** a >= xo + 100 */
        add(h, 0, i, 100);

    for (int i = 0; i <= n; ++i)
        if (!dnt[i]) tarjan(i);

    //缩点(枚举图中所有每两个节点，来建图)
    bool success = true;
    for (int i = 0; i <= n; ++i) {
        for (int j = h[i]; ~j; j = ne[j]) {
            int k = e[j];

            int a = id[i], b = id[k];
            if (a == b) {
                if (w[j]) { //同一个强连通分量内的边的权值只能为正数，否则存在正环
                    success = false;
                    break;
                }
            } else
                add(hs, a, b, w[j]);
        }
        if (!success) break;
    }

    if (!success)
        puts("Poor Xed");
    else {
        dist[0] = 0;
        //递推求出新建的图中的最长路(按照拓扑序来递推，scc_cnt ~ 1这个顺序符合拓扑序)
        for (int i = scc_cnt; i >= 1; i--) {
            //枚举i邻接的所有的边，找出最大的状态转移
            for (int j = hs[i]; ~j; j = ne[j]) {
                int k = e[j];
                dist[k] = max(dist[k], dist[i] + w[j]);
            }
        }
        int res = 0;
        for (int i = 1; i <= scc_cnt; ++i) res += (scc_size[i] * dist[i]);
        cout << res << endl;
    }
    return 0;
}