Rockdu's Blog

题目描述

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。

输入输出格式

输入格式：

输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。 其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。 注意数据中可能包含重边与自环。

输出格式：

输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不 含引号）。

输入输出样例

4 5 
1 2 19 1 
2 3 8 12 
2 4 12 15 
1 3 17 8 
3 4 1 17

32

3 1 
1 2 1 1

-1

说明

* 解释1

如果小 E 走路径 1→2→4，需要携带 19+15=34 个守护精灵； 如果小 E 走路径 1→3→4，需要携带 17+17=34 个守护精灵； 如果小 E 走路径 1→2→3→4，需要携带 19+17=36 个守护精灵； 如果小 E 走路径 1→3→2→4，需要携带 17+15=32 个守护精灵。 综上所述，小 E 最少需要携带 32 个守护精灵。

* 解释2

小 E 无法从 1 号节点到达 3 号节点，故输出-1。

第一次LCT写的那么顺，改了数组大小就A了！撒花纪念~

可以容易看出最小生成树，但是单次最小生成树只能保证A最大或者B最大呀！怎么办呢……考虑用A做最小生成树一边做Kruscal一边维护答案。每加入一条边考虑如何才能最优的移除一条边使得答案尽可能小。因为加入一条边后如果已经联通一定形成环，我们只需要查询环上B值最大的边删去即可保证答案的最优性。那么能支持加边删边，维护树上最大值的数据结构就只有LCT了。下面是代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define EDGE(x) ((x) + n)
#define ORG(x) ((x) - n)
using namespace std;
const int maxn = 1e5 + 5;

int val[150005];
namespace LCT {
	const int L = 0, R = 1;
	struct node {
		int ch[2], fa, size, rv, mx, mpos;
	}tree[maxn << 1];
	int cnt;
	#define isrt(x) (tree[tree[x].fa].ch[R] != x && tree[tree[x].fa].ch[L] != x)
	void init(int n) {
		for(register int i = 1; i <= n; ++i) tree[i].size = 1, tree[i].mpos = i;
	}
	int *lc, *rc;
	void push_up(int rt) {
		lc = &tree[rt].ch[L], rc = &tree[rt].ch[R];
		tree[rt].size = tree[*lc].size + tree[*rc].size + 1;
		if(tree[*lc].mx < tree[*rc].mx) tree[rt].mpos = tree[*rc].mpos, tree[rt].mx = tree[*rc].mx;
		else tree[rt].mpos = tree[*lc].mpos, tree[rt].mx = tree[*lc].mx;
		if(tree[rt].mx < val[rt]) tree[rt].mpos = rt, tree[rt].mx = val[rt];
	}
	void push_down(int rt) {
		if(tree[rt].rv) {
			lc = &tree[rt].ch[L], rc = &tree[rt].ch[R];
			tree[*lc].rv ^= 1, tree[*rc].rv ^= 1;
			swap(*lc, *rc), tree[rt].rv = 0;
		}
	}
	void rotate(int rt) {
		int p = tree[rt].fa, a = tree[p].fa;
		int r = tree[p].ch[R] == rt, l = r ^ 1;
		if(!isrt(p)) tree[a].ch[tree[a].ch[R] == p] = rt;
		tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[l]].fa = p;
		tree[p].ch[r] = tree[rt].ch[l], tree[rt].ch[l] = p;
		push_up(p), push_up(rt);
	}
	void splay(int rt, int y) {
		int des = tree[y].fa;
		while(tree[rt].fa != des) {
			int p = tree[rt].fa, a = tree[p].fa;
			push_down(a), push_down(p), push_down(rt);
			if(p != y) if((tree[a].ch[R] == p) ^ (tree[p].ch[R] == rt)) rotate(rt);
					else rotate(p);
			rotate(rt);
		}
	}
	int findrt(int x) {while(!isrt(x)) x = tree[x].fa; return x;}
	void change(int x, int y) {
		int u = findrt(x);
		splay(x, u), push_down(x), tree[x].ch[R] = y;
		push_up(x);
	}
	int access(int x) {
		for(change(x, 0); tree[x].fa; x = tree[x].fa) change(tree[x].fa, x);
		int u = x;while(push_down(x), tree[x].ch[L]) x = tree[x].ch[L];
		return splay(x, u), x;
	}
	void makeroot(int x) {tree[access(x)].rv ^= 1;}
	void link(int x, int y) {tree[y = access(y)].rv ^= 1, tree[y].fa = x;}
	void cut(int x, int y) {change(x, 0), change(y, 0), tree[tree[x].fa == y ? x : y].fa = 0;}
	int query(int x, int y) {return makeroot(x), tree[access(y)].mpos;}
}

namespace DSU {
	int fa[maxn];
	void init(int n) {for(register int i = 1; i <= n; ++i) fa[i] = i;}
	int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
	void combine(int x, int y) {fa[find(x)] = find(y);}
}

struct edge {
	int u, v, a, b;
}e[maxn << 1];
int head[maxn], cnt, n, m, u, v, a, b, ans = 0x3f3f3f3f;
bool cmp(const edge & a, const edge & b) {return a.a < b.a;}

int main() {
	scanf("%d%d", &n, &m), LCT::init(n + m), DSU::init(n);
	for(register int i = 1; i <= m; ++i)
		scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].a, &e[i].b);
	sort(e + 1, e + m + 1, cmp);
	for(register int i = 1; i <= m; ++i) val[EDGE(i)] = e[i].b;
	for(register int i = 1; i <= m; ++i) {
		u = e[i].u, v = e[i].v, a = e[i].a, b = e[i].b;
		if(DSU::find(u) != DSU::find(v))
			DSU::combine(u, v), LCT::link(u, EDGE(i)), LCT::link(EDGE(i), v);
		else {
			int pe = LCT::query(u, v);
			if(val[pe] > b) {
				LCT::cut(pe, e[ORG(pe)].v);
				LCT::cut(pe, e[ORG(pe)].u);
				LCT::link(EDGE(i), e[i].u), LCT::link(EDGE(i), e[i].v);
			}
		}
		if(DSU::find(1) == DSU::find(n)) 
			ans = min(ans, e[i].a + val[LCT::query(1, n)]);
	}
	printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
	return 0;
}