题面

题意:

给出一个图，边权有两维，a与b. 求1到n的一条路径使得路径经过的边的最大的a与b的和最小，输出最小之和。

\(Solution:\)

如果做过这题，那么就显得很简单了很好想了。

又是想让路径上最大的边权尽可能小，于是就想到先对 b 从小到大 Kruscal 加边，然后维护链上 a 的最大边，如果当前 link(u,v) 成环了，假设之前 u 到 v 路径上最大边是 x->y , 如果 x->y.a > u->v.a 就 cut(x,y),link(u,v).

\(Source\)

#include <set>

#include <cmath>

#include <cctype>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <assert.h>

#include <algorithm>

using namespace std;

#define fir first

#define sec second

#define pb push_back

#define mp make_pair

#define LL long long

#define INF (0x3f3f3f3f)

#define mem(a, b) memset(a, b, sizeof (a))

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define ____ debug("go")

#define Debug(x) cout << #x << " = " << x << endl

#define tralve(i, x) for (register int i = head[x]; i; i = nxt[i])

#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))

#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

namespace io {

    static char buf[1<<21], *pos = buf, *end = buf;

    inline char getc()

    { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }

    inline int rint() {

        register int x = 0, f = 1;register char c;

        while (!isdigit(c = getc())) if (c == '-') f = -1;

        while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));

        return x * f;

    }

    inline LL rLL() {

        register LL x = 0, f = 1; register char c;

        while (!isdigit(c = getc())) if (c == '-') f = -1;

        while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));

        return x * f;

    }

    inline void rstr(char *str) {

        while (isspace(*str = getc()));

        while (!isspace(*++str = getc()))

            if (*str == EOF) break;

        *str = '\0';

    }

    template<typename T>

        inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }

    template<typename T>

        inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }

}

using namespace io;

const int N = 2e5 + 1;

int n, m, Fa[N];

struct Edge { int u, v, a, b; } E[N];

bool operator<(Edge a, Edge b) { return a.b < b.b; }

namespace LCT {

#define ls (ch[x][0])

#define rs (ch[x][1])

#define chk(x) (ch[fa[x]][1] == x)

    int top, stk[N];

    int ch[N][2], fa[N], mxid[N], id[N], rev[N];

    void init(int x, int y) {

        if (x > n) mxid[x] = id[x] = y;

    }

    bool irt(int x) {

        return x != ch[fa[x]][0] && x != ch[fa[x]][1];

    }

    void pu(int x) {

        mxid[x] = id[x];

        if (ls && E[mxid[x]].a < E[mxid[ls]].a) mxid[x] = mxid[ls];

        if (rs && E[mxid[x]].a < E[mxid[rs]].a) mxid[x] = mxid[rs];

    }

    void pd(int x) {

        if (rev[x]) {

            swap(ch[ls][0], ch[ls][1]); rev[ls] ^= 1;

            swap(ch[rs][0], ch[rs][1]); rev[rs] ^= 1;

            rev[x] = 0;

        }

    }

    void rot(int x) {

        int y = fa[x], z = fa[y], k = chk(x), tmp = ch[x][k ^ 1];

        ch[y][k] = tmp, fa[tmp] = y;

        if (!irt(y)) ch[z][chk(y)] = x; fa[x] = z;

        ch[x][k ^ 1] = y, fa[y] = x;

        pu(y); pu(x);

    }

    void splay(int x) {

        stk[top = 1] = x; for (int i = x; !irt(i); i = fa[i]) stk[++top] = fa[i];

        while (top) pd(stk[top--]);

        while (!irt(x)) {

            int y = fa[x], z = fa[y];

            if (!irt(y))

                if (chk(x) == chk(y)) rot(y);

                else rot(x);

            rot(x);

        }

    }

    void access(int x) {

        for (int y = 0; x; x = fa[y = x]) splay(x), ch[x][1] = y, pu(x);

    }

    int findroot(int x) {

        access(x); splay(x); pd(x); while (ch[x][0]) x = ch[x][0], pd(x); splay(x); return x;

    }

    void makeroot(int x) {

        access(x); splay(x); swap(ls, rs); rev[x] ^= 1;

    }

    void split(int x, int y) {

        makeroot(x); access(y); splay(y);

    }

    void link(int x, int y) {

        makeroot(x); fa[x] = y;

    }

    void cut(int x, int y) {

        split(x, y); ch[y][0] = fa[x] = 0;

    }

}

int find(int x) {

    return Fa[x] == x ? x : Fa[x] == find(Fa[x]);

}

void merge(int x, int y) {

    Fa[find(x)] = find(y);

}

int main() {

#ifndef ONLINE_JUDGE

    file("P2387");

#endif

    n = rint(), m = rint();

    For (i, 1, m) {

        E[i].u = rint(), E[i].v = rint(), E[i].a = rint(), E[i].b = rint();

    }

    sort(E + 1, E + 1 + m);

    For (i, 1, n + m) Fa[i] = i;

    For (i, n + 1, m + n) LCT::init(i, i - n);

    int ans = INF;

    For (i, 1, m) {

        //____;

        int u = E[i].u, v = E[i].v;

        if (LCT::findroot(u) == LCT::findroot(v)) {

            LCT::split(u, v);

            int Maxid = LCT::mxid[v];

            if (E[i].a < E[Maxid].a) {

                LCT::cut(E[Maxid].u, Maxid + n); LCT::cut(Maxid + n, E[Maxid].v);

                LCT::link(u, i + n); LCT::link(i + n, v);

            }

        } else {

            LCT::link(u, i + n); LCT::link(i + n, v);

        }

        if (LCT::findroot(1) == LCT::findroot(n)) {

            LCT::split(1, n); int Maxid = LCT::mxid[n];

            chkmin(ans, E[i].b + E[Maxid].a);

        }

    }

    printf("%d\n", ans == INF ? -1 : ans);

}

巴特西

[P2387魔法森林

题面

题意:

\(Solution:\)

\(Source\)

最新文章

热门文章