题目分析

差分约束 这里做个简单介绍：形如\(x_i - x_j >= d\)的不等式，可以联想到我们求最短路时\(d_v <= d_u + len\)，则上式可以变形为\(x_i >= x_j + d\)即连一条j->i的长度为d的边并跑最长路，dis[i]则是满足条件的最小解（因为上面等式采用的>=号，所以求出的时最小解，同理当变形为\(x_j <= x_i - d\) 采用<= 时求出的是最大解）。

转差分约束

这道题也是经典的差分约束，只是要注意几个问题：

spfa判负环无解
输入矛盾条件时直接无解

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

using namespace std;

const int N = 1e6 + 5;

typedef long long ll;

const ll OO = 0x3f3f3f3f;

int times[N];

int n, k;

ll dis[N];

int ecnt, adj[N], go[N << 2], nxt[N << 2], len[N << 2];

bool vst[N];

inline void addEdge(int u, int v, int l){

    nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v, len[ecnt] = l;

}

inline int read(){

    int i = 0, f = 1;char ch = getchar();

    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

    if(ch == '-') ch = getchar(), f = -1;

    for(; ch >= '0' && ch <= '9'; ch = getchar())

        i = (i << 3) + (i << 1) + (ch - '0');

    return i * f;

}

inline void wr(ll x){

    if(x < 0) putchar('-'), x = -x;

    if(x > 9) wr(x / 10);

    putchar(x % 10 + '0');

}

inline bool spfa(){

    static int que[N], qn;

    for(int i = 1; i <= n; i++) dis[i] = -OO;

    dis[0] = 0;

    que[qn = 1] = 0;

    vst[0] = true;

    for(int ql = 1; ql <= qn; ql++){

        int u = que[ql];

        vst[u] = false;

        times[u]++;

        if(times[u] == n) return false;

        for(int e = adj[u]; e; e = nxt[e]){

            int v = go[e];

            if(dis[v] < dis[u] + len[e]){

                dis[v] = dis[u] + len[e];

                if(!vst[v]) vst[v] = true, que[++qn] = v;

            }

        }

    }

    return true;

}

int main(){

    n = read(), k = read();

    for(int i = n; i >= 1; i--) addEdge(0, i, 1);

    for(int i = 1; i <= k; i++){

        int x = read(), a = read(), b = read();

        switch(x){

            case 1:{

                if(a != b){

                    addEdge(a, b, 0);

                    addEdge(b, a, 0);

                }

                break;

            }

            case 2:{

                if(a == b){

                    printf("-1");

                    return 0;

                }

                addEdge(a, b, 1);

                break;

            }

            case 3:{

                if(a != b)

                    addEdge(b, a, 0);

                break;

            }

            case 4:{

                if(a == b){

                    printf("-1");

                    return 0;

                }

                addEdge(b, a, 1);

                break;

            }

            case 5:{

                if(a != b)

                    addEdge(a, b, 0);

                break;

            }

            default: break;

        }

    }

    if(!spfa()){

        printf("-1");

        return 0;

    }

    ll ans = 0;

    for(int i = 1; i <= n; i++){

        ans += dis[i];

    }

    wr(ans);

    return 0;

}

巴特西

BZOJ 2330 - 差分约束系统

题目分析

code

最新文章

热门文章