題面

題意:

給出一個圖，邊權有兩維，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_JUDGEfile("P2387"); #endifn = 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); }

轉載于:https://www.cnblogs.com/cnyali-Tea/p/10459017.html

總結

以上是生活随笔為你收集整理的[P2387魔法森林的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。