B题 奖学金

算法一: 拓扑排序

思路:

对于任给的一个意见(\(a\)同学比\(b\)同学高)转化为: 存在一条由\(a\)到\(b\)的权重为\(1\)的有向边
构建一个图, 经过拓扑排序, 保证图中每一个点在其前驱点入队前不会入队.
对应本题就是:保证每一个同学能够满足所有的不等式。

#include <iostream>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;

int h[N], e[M], ne[M], idx, w[M];

int dist[N];
int din[N];

void add(int a, int b, int v)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = v, h[a] = idx++;
}

int main()
{
    int n, m;
    cin >> n >> m;
    memset (h, -1, sizeof h);
    queue<int> q;


    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(b, a, 1);
        din[a]++;
    }

    for (int i = 1; i <= n; i ++ )
        if (!din[i]){
            q.push(i);
        }
    
    while (q.size()){
        int u = q.front();
        q.pop();

        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];

            if (dist[j] <= dist[u] + w[i])
                dist[j] = dist[u] + w[i];

            din[j]--;

            if (!din[j])
                q.push(j);
        }
    }

    long long ans = 100 * n;

    for (int i = 1; i <= n; i ++ )
        if (din[i]){
            puts("impossible");
            return 0;
        }else
            ans += dist[i];

    cout << ans << endl;

    return 0;
}

算法二: 差分约束

思路:

问题转化为不等式: \(a > b + 1\)
对于每一个不等式， 构建一条\(b\) 到 \(a\)的边, 再构建一个到所有点的虚拟原点.
问题要求最小值, 用\(spfa\)求最长路.

注意: 需要用\(spfa\)判环(该题是判正环), 使用队列可能TLE(本题使用队列被卡), 可将队列换成栈.

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

const int N = 2e5 + 10;
const int M = 2 * N;

int dist[N];
int cnt[N];
int h[N], e[M], ne[M], w[M], idx;
int st[N];

int n, m;

void add(int a, int b, int v)
{
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx++;
}


int spfa()
{
    memset(dist, -1, sizeof dist);
    dist[0] = 0;
    stack<int> q;
    q.push(0);
    st[0] = 1;

    while (q.size()){
        int u = q.top();
        q.pop();
        st[u] = 0;

        for (int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];

            if (dist[j] < dist[u] + w[i]){
                dist[j] = dist[u] + w[i];
                cnt[j] += 1;
                if (cnt[j] > n + 1)
                    return 1;
                if (!st[j]){
                    q.push(j);
                    st[j] = 1;
                }
            }

        }
    }
    return 0;
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a, 1);

    }

    for (int i = 1; i <= n; i ++ )
        add(0, i, 0);

    if (spfa())
        puts("impossible");
    else{

        long long ans = 0;
        for (int i = 1; i <= n; i ++ )
            ans += dist[i];
        ans += 100 * n;
        cout << ans << endl;
    }

    return 0;
}

2021年ACM竞赛班训练（十一）B题 奖学金

原文：https://www.cnblogs.com/lhqwd/p/14854614.html