欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOI2014魔法森林题解报告

程序员文章站 2022-06-22 21:08:25
...

题目描述

为了得到书法大家的真传,小 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”(不 含引号)。

输入输出样例

输入样例#1:
4 5 
1 2 19 1 
2 3 8 12 
2 4 12 15 
1 3 17 8 
3 4 1 17 
输出样例#1:
32
输入样例#2:
3 1 
1 2 1 1 
输出样例#2:
-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。

NOI2014魔法森林题解报告



题解

刚学完link cut tree,找题刷刷

这道题要满足两种权值和最小,我们难以同时兼顾,我们就先令a最小并维护b最小。

这就成了维护动态最小生成树


将边按a的大小升序排序,不断加边,这样子当前a的路径最大权值如果改变,那么一定是刚加入的边的权值

证明:

1、若路径经过新加入的边,由于新加入的边比之前加入的边权值都大,所以最大权值是新加入的边

2、若路径不经过新加入的边,那么这条路径之前一定被计算过,不妨令之前算出a0+b0,如今算出a1+b0,由升序得a1>a0,所以新算的路径不会被考虑,不影响结果


如此以来,我们按a升序加入,同时维护b的最小生成树【也就是当边为N-1条之后,没加入一条边就删去一条b权值最大的边,动态维护b的最小生成树】

每次统计的答案就是     当前加入的a+【1到N】b的最大值

很明显用link cut tree


把边看作点,每次加入一条边就连上两端的点,删去类似。

我们对每个节点维护子树的最大值编号,每次就可以通过link cut tree找到最大权值对应的边删去,也可以迅速统计路径b最大权值


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define isr(u) (e[e[u].f].ch[1] == u)
#define isrt(u) (!e[u].f || (e[e[u].f].ch[0] != u &&e[e[u].f].ch[1] != u))
using namespace std;
const int maxn=200005,maxm=100005,INF=100000000;

inline int read(){
	int out=0,flag=1;char c=getchar();
	while(c<48||c>57) {if(c=='-') flag=-1;c=getchar();}
	while(c>=48&&c<=57) {out=out*10+c-48;c=getchar();}
	return out*flag;
}

int N,M,temp[maxn];

struct EDGE{
	int x,y,a,b;
}edge[maxm];

inline bool operator < (const EDGE& a,const EDGE& b){
	return a.a < b.a;
}

struct node{
	int w,f,ch[2],rev,Maxu;
	node() {f = ch[0] = ch[1] = rev = w = 0;}
}e[maxn];

inline void push_up(int u){
	e[u].Maxu = u;
	if (e[u].ch[0] && e[e[e[u].ch[0]].Maxu].w > e[e[u].Maxu].w) e[u].Maxu = e[e[u].ch[0]].Maxu;
	if (e[u].ch[1] && e[e[e[u].ch[1]].Maxu].w > e[e[u].Maxu].w) e[u].Maxu = e[e[u].ch[1]].Maxu;
}

inline void pd(int u){
	if (e[u].rev){
		swap(e[u].ch[0],e[u].ch[1]);
		e[e[u].ch[0]].rev ^= 1;
		e[e[u].ch[1]].rev ^= 1;
		e[u].rev = 0;
	}
}

inline void push_down(int u){
	int i = 0;
	do {temp[++i] = u;} while(!isrt(u) && (u = e[u].f));
	while (i) pd(temp[i--]);
}

inline int Find(int u){
	while (e[u].f) u = e[u].f;
	return u;
}

inline void spin(int u){
	int s = isr(u),fa = e[u].f;
	e[u].f = e[fa].f;
	if (!isrt(fa)) e[e[fa].f].ch[isr(fa)] = u;
	e[fa].ch[s] = e[u].ch[s^1];
	if (e[u].ch[s^1]) e[e[u].ch[s^1]].f = fa;
	e[fa].f = u;
	e[u].ch[s^1] = fa;
	push_up(fa);
}

inline void splay(int u){
	push_down(u);
	while(!isrt(u)){
		if (isrt(e[u].f)) spin(u);
		else if (isr(u) ^ isr(e[u].f)) spin(u),spin(u);
		else spin(e[u].f),spin(u);
	}
	push_up(u);
}

inline void Access(int u){
	for (int v = 0; u; u = e[v = u].f){
		splay(u);
		e[u].ch[1] = v;
		if (v) e[v].f = u;
		push_up(u);
	}
}

inline void Make_root(int u){
	Access(u); splay(u);
	e[u].rev ^= 1;
}

inline void Link(int u,int v){
	Make_root(u); e[u].f = v;
}

inline void Cut(int u,int v){
	Make_root(u); Access(v); splay(v);
	e[u].f = 0;
	e[v].ch[0] = 0;
	push_up(v);
}

inline int Query(int u,int v){
	if (Find(u) != Find(v)) return 0;
	Make_root(u); Access(v); splay(v);
	return e[v].Maxu;
}

void init(){
	e[0].w = INF;
	e[0].Maxu = 0;
	N = read();
	M = read();
	for (int i = 1; i <= M + N; i++) e[i].Maxu = i;
	for (int i = 1; i <= M; i++){
		edge[i].x = read();
		edge[i].y = read();
		edge[i].a = read();
		edge[i].b = read();
	}
	sort(edge + 1,edge + 1 + M);
}

void solve(){
	int ans = INF,x,y,t;
	for (int i = 1; i <= M; i++){
		e[N + i].w = edge[i].b;
		if (Find(x = edge[i].x) != Find(y = edge[i].y)){
			Link(N + i,x);
			Link(N + i,y);
		}else {
			t = Query(x,y);
			if(e[t].w > e[N + i].w){
				Cut(t,edge[t - N].x);
				Cut(t,edge[t - N].y);
				Link(N + i,x);
				Link(N + i,y);
			}
		}
		ans = min(ans,edge[i].a + e[Query(1,N)].w);
	}
	if (ans == INF) printf("-1\n");
	else printf("%d\n",ans);
}

int main()
{
	init();
	solve();
	return 0;
}