代码实现是不可忽视的能力

懵逼的 题目

传送至 (上市的)Bilibili

扯淡的 题解

胡乱写写…

luogu和LOJ蜜汁T…反正b站和vijos老娘过了…心理AC dafa is good

观察不等式$to > from + cost$, 即最长路的更新过程, 更新后将满足这个不等式

而我们的差分约束: $A - B > x \Rightarrow A > b + x$与最长路更新后的结果一模一样…于是我们就可以利用最长路求这个差分约束的一个解, 如果我们设源点$S$的$dis$为$0$的话就是一个最小解

什么? 你说没有源点? 自己造一个源点向所有的点都连上一条$dis = 0$的边不就好了…反正是求最长路…

你问我最短路…不会最短路的边权肯定有负的啊…$dis = 0$也不会影响什么…吧?

沙茶的 代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0x7fffffff)
#define MAXN (100000 + 5)
#define MAXM (100000 + 5)
#define LL long long
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, MAXN << 5, stdin), S == T) ? EOF : *S++)
char BB[MAXN * 20], *S = BB, *T = BB;
using namespace std;
const int s = 0;
struct edg
{
    int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, dis[MAXN], cnt[MAXN];;
bool inq[MAXN];
inline int read()
{
    register int c = 0, re = 0;
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
    {
        re = (re << 1) + (re << 3) + (c ^ '0');
        c = getchar(); 
    }
    return re;
}
inline void adn(const int from, const int to, const int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
} 
// to >= from + cost
// to - from >= cost
void spfa()
{
    queue<int> q;
    dis[s] =  1;
    q.push(s);
    inq[s] = true;
    ++cnt[s];
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        inq[dq] = false;
        for (int i = g[dq]; i; i = b[i].next)
            if (dis[b[i].to] < dis[dq] + b[i].cost)
            {
                dis[b[i].to] = dis[dq] + b[i].cost;
                if (!inq[b[i].to])
                {
                    ++cnt[b[i].to];
                    if (cnt[b[i].to] > n)
                    {
                        puts("-1");
                        exit(0);
                    }
                    q.push(b[i].to);
                    inq[b[i].to] = true;
                }
            }
    }
}
// to >= from + cost
// to - from >= cost
void init()
{
    n = read();
    int k = read();
//    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; i++)
    {
        int sre = read(), srx = read(), sry = read();
//        scanf("%d%d%d", &sre, &srx, &sry);
        if (sre == 1)
        {
            adn(srx, sry, 0);
            adn(sry, srx, 0);
        }
        else if (sre == 2)
            adn(srx, sry, 1);
        else if (sre == 3)
            adn(sry, srx, 0);
        else if (sre == 4)
            adn(sry, srx, 1);
        else if (sre == 5)
            adn(srx, sry, 0);
    }
}
int main()
{
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
    memset(inq, false, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    init();
    memset(dis, 0, sizeof(dis));
    for (int i = n; i >= 1; i--)
        adn(s, i, 0);
    spfa();
    LL sum = 0;
    for (int i = 1; i <= n; i++)
        sum += dis[i];
    printf("%lld", sum);
    return 0;
}

/*
5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1
*/

By 有些焦虑的 Cansult