求助,60分,我炸了啊QAQ
查看原帖
求助,60分,我炸了啊QAQ
218311
Updateღ楼主2020/6/14 11:36
#include <stdio.h>
#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <math.h>
#define maxn 50000
using namespace std;

struct node {
	int pre , val , to;
} g[maxn << 1 + 5];

struct point {
	long long to , val;
};

int m , n , x , y , z , cnt , demaxn , top , ll , rr;
int army[maxn + 5] , st[maxn + 5][35] , fa[maxn + 5] , d[maxn + 5] , dist[maxn + 5][35] , ues[maxn + 5] , v[maxn + 5] , ned[maxn + 5];
bool ok = false , f[maxn + 5] ,  need[maxn + 5];
long long l = 1 , r , ans;
queue<int> dl;
point remain[maxn + 5];

int cmp(point a , point b) {
	return a.val > b.val;
}

void mem() {
	memset(f , 0 , sizeof(f));
	ll = 0 , rr = 0 , top = 0;
}

int dfs(int rt) {
	bool bj = false;
	if(f[rt]) 
		return 1;
	for(int i = v[rt]; i; i = g[i].pre) {
		int p = g[i].to;
		if(d[p] < d[rt])
			continue;
		bj = true;
		if(!dfs(p)) 
			return 0;
	}
	if(!bj)
		return 0;
	return 1;	
}

void add(int ffa , int child , int t) {
	g[++cnt].pre = v[ffa];
	g[cnt].to = child;
	g[cnt].val = t;
	v[ffa] = cnt;
}

void RMQ() {
	for(int i = 1; i <= m; ++i)
		st[i][0] = fa[i];
	for(int j = 1; j <= demaxn; ++j) {
		for(int i = 2; i + (1 << j) - 1 <= m; ++i) {
			st[i][j] = st[st[i][j - 1]][j - 1];
			dist[i][j] = dist[st[i][j - 1]][j - 1] + dist[i][j - 1];
 	   }
	}
	return ;
}

int match() {
	if(ll < rr) 
		return 0;
	int i = 1 , j = 1;
	while(i <= ll && j <= rr) {
		if(ues[i] >= ned[j]) {
			++i;
			++j;
		} 
		else 
			++i;
	}
	if(j > rr)
		return 1;
	return 0; 
} 

void back() {
	sort(remain + 1 , remain + top + 1 , cmp);
	for(int i = 1; i <= top; ++i) {
		if(need[remain[i].to] && remain[i].val < dist[remain[i].to][0])
			need[remain[i].to] = false;
		else 
			ues[++ll] = remain[i].val;
	}
	for(int i = v[1]; i; i = g[i].pre)
		if(need[g[i].to]) 
			ned[++rr] = g[i].val;
	if(rr) sort(ned + 1 , ned + rr + 1);
	if(ll) sort(ues + 1 , ues + ll + 1);
}

int cheak(long long ti) {
	mem();
	long long e , t;
	for(int i = 1; i <= n; ++i) {
		e = army[i];
		t = ti;
		for(int j = demaxn; j >= 0; --j) {
			if(t - dist[e][j] >= 0 && st[e][j] > 1) {
				t -= dist[e][j];
				e = st[e][j];
			}
		}
		if(st[e][0] == 1 && t >= dist[e][0]) {
			remain[++top].to = e;
			remain[top].val = t - dist[e][0];
		}
		else 
			f[e] = true;
	}
	for(int i = v[1]; i; i = g[i].pre)
		if(!dfs(g[i].to))
			need[g[i].to] = true;
	back();
	return match();
}

void Binsea() {
	long long mid = (l + r) >> 1;
	while(l <= r) {
		if(cheak(mid)) {
			ok = true;
			r = mid - 1;
			ans = mid;
		}
		else l = mid + 1;
		mid = (l + r) >> 1;
	}
}

int main() {
//	freopen("P1084_5.in" , "r" , stdin);
//	freopen("1084.out" , "w" , stdout);
	scanf("%d", &m);
	demaxn = log(m) / log(2) + 1;
	for(int i = 1; i <= m - 1; ++i) {
		scanf("%d %d %d" , &x , &y , &z);
		r += z;
		add(x , y , z);
		add(y , x , z);
	}
	scanf("%d" , &n);
	for(int i = 1; i <= n; ++i) 
		scanf("%d", &army[i]);
	dl.push(1);
	d[1] = 1;
	int t;
	while(dl.size()) {
		t = dl.front();
		dl.pop();
		for(int i = v[t]; i; i = g[i].pre) {
			int p = g[i].to;
			if(d[p]) 
				continue;
			d[p] = d[t] + 1;
			fa[p] = t;
			dist[p][0] = g[i].val;
			dl.push(p);
		}
	}
	RMQ();
	Binsea();
	if(ok) printf("%d\n" , ans);
	else printf("-1");
	return 0;
}

希望有大佬帮忙改改,我照着题解打的QAQ

2020/6/14 11:36
加载中...