MENU

NOI.AC#95 cycle

NOI.AC#95

二分+dfs SPFA,跑得格外地快= =

#include<cstdio>
#include<vector>
#include<utility>
#include<cstring>
#if _WIN32||__WIN32__||_WIN64||__WIN64__||__CYGWIN__
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_NO_WARNINGS
#define _CRT_DISABLE_PERFCRIT_LOCKS
#endif
#if __unix__
#define fread fread_unlocked
#define fwrite fwrite_unlocked
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
using namespace std;
struct io {
    static const int L = (1 << 23) + 1;
    char ibuf[L], *iS, *iT, obuf[L], *oS, *oT, st[50];
    void putc(char x) { *oS++ = x; }
    char gc() {
        if (iS == iT)iT = (iS = ibuf) + fread(ibuf, 1, L, stdin);
        return *iS++;
    }
    template<class T>T rd() {
        int c = gc(),f=1;
        T x = 0;
        for (; c < 48; c = gc())if(c=='-')f=-1;
        for (; c > 32; c = gc())x = x * 10 + (c & 15);
        return x*f;
    }
    template<class T>void print(T x) {
        if (!x) { *oS++ = '0'; return; }
        int tp = 0;
        for (; x; st[++tp] = x % 10 + 48, x /= 10);
        for (; tp; *oS++ = st[tp--]);
    }
    io() :oS(obuf), oT(obuf + L - 1) {}
    ~io() { fwrite(obuf, 1, oS - obuf, stdout); }
}ip;
int n = ip.rd<int>(), m = ip.rd<int>(), dis[301], l = 3, r = n + 1, mid;
bool vis[301];
vector<pair<int, int> >e[301];
int dfs(int x, int cnt) {
    if (cnt >= mid || dis[x] < 0)return 0;
    vis[x] = 1;
    for (vector<pair<int, int> >::const_iterator it = e[x].begin(); it != e[x].end(); ++it) {
        int v = it->first, w = it->second;
        if (dis[v] <= dis[x] + w) {
            dis[v] = dis[x] + w;
            if (vis[v] || dfs(v, cnt + 1))return 1;
        }
    }
    return vis[x] = 0;
}
inline int judge() {
    for (int i = 1; i <= n; ++i) {
        memset(dis + 1, 0x8f, 4 * n), dis[i] = 0, memset(vis + 1, 0, n);
        if (dfs(i, 0))return 1;
    }
    return 0;
}
int main() {
    for (int i = 1, a, b, c, d; i <= m; ++i) {
        a = ip.rd<int>(), b = ip.rd<int>(), c = ip.rd<int>(), d = ip.rd<int>();
        if (c + d > 0)return ip.print(2), 0;
        e[a].push_back(make_pair(b, c)), e[b].push_back(make_pair(a, d));
    }
    while (l < r)mid = l + r >> 1, judge() ? r = mid : l = mid + 1;
    ip.print(l == n + 1 ? 0 : l);
}