MENU

洛谷P3275/BZOJ2330 [SCOI2011]糖果

洛谷P3275

BZOJ2330

差分约束,边表示$v$需比$u$多$w$,跑最长路。

#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    template<class T = int>T rd() {
        int c = *iS++;
        T x = 0;
        for(; c < 48; c = *iS++);
        for(; c > 32; c = *iS++)x = x * 10 + (c & 15);
        return x;
    }
    template<class T>void print(T x) {
        if(!x) { *oS++ = '0'; return; }
        if(x < 0)*oS++ = '-', x = -x;
        int tp = 0;
        for(; x; st[tp++] = x % 10 + 48, x /= 10);
        for(--tp; ~tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) { iT = (iS = ibuf) + fread(ibuf, 1, L, stdin); }
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int N = ip.rd(), K = ip.rd(), inq[100001], dis[100001], cnt[100001];
std::vector<std::pair<int, int>> e[100001];
std::queue<int> q;
bool spfa() {
    for(int i = 1; i <= N; ++i)cnt[i] = dis[i] = 1, q.push(i);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto i : e[u]) {
            int v = i.first, w = i.second;
            inq[v] = 1;
            if(dis[v] >= dis[u] + w)continue;
            dis[v] = dis[u] + w;
            if((++cnt[v]) >= N)return 1;
            if(inq[v])inq[v] = 0, q.push(v);
        }
    }
    return 0;
}
int main() {
    while(K--) {
        int X = ip.rd(), A = ip.rd(), B = ip.rd();
        switch(X) {
            case 1:e[A].emplace_back(B, 0), e[B].emplace_back(A, 0); break;
            case 2:
                if(A==B)return ip.print(-1), 0;
                e[A].emplace_back(B, 1); break;
            case 3:e[B].emplace_back(A, 0); break;
            case 4:
                if(A == B)return ip.print(-1), 0;
                e[B].emplace_back(A, 1); break;
            case 5:e[A].emplace_back(B, 0);
        }
    }
    if(spfa())return ip.print(-1), 0;
    long long ans = 0;
    for(int i = 1; i <= N; ++i)ans += dis[i];
    ip.print(ans);
}