9
29
2015
0

4151: [AMPPZ2014]The Cave

4151: [AMPPZ2014]The Cave

Time Limit: 5 Sec  Memory Limit: 256 MBSec  Special Judge
Submit: 101  Solved: 45
[Submit][Status][Discuss]

Description

给定一棵有n个节点的树,相邻两点之间的距离为1。
请找到一个点x,使其满足所有m条限制,其中第i条限制为dist(x,a[i])+dist(x,b[i])<=d[i]。
 

 

Input

第一行包含一个正整数t(1<=t<=1000),表示数据组数。
对于每组数据,第一行包含两个正整数n,m(2<=n,m<=300000),表示点数、限制数。
接下来n-1行,每行两个正整数x,y(1<=x,y<=n),表示树上的一条边。
接下来m行,每行三个正整数a[i],b[i],d[i](1<=a[i],b[i]<=n,1<=d[i]<=600000),描述一条限制。
输入数据保证所有n之和不超过300000,所有m之和也不超过300000。
 

 

Output

输出t行。第i行输出第i组数据的答案,如果无解输出NIE,否则输出TAK,
然后输出x,如有多组解,输出任意一组。
 

 

Sample Input

2
5 3
1 2
2 3
2 4
3 5
1 4 2
5 5 5
3 2 1
3 2
1 2
2 3
1 1 2
3 3 1

Sample Output

TAK 2
NIE

HINT

 

Source

    来填上这个好久以前的坑。。。

    模拟赛里的一道题目。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
struct data{int x,y,next;} e[N<<1];
int head[N],dis[10][N],a[N],b[N],d[N],Max,cnt,n,m,T,t,Min,x,y;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(int x,int y){
	e[++cnt].x = x;e[cnt].y = y;
	e[cnt].next = head[x];head[x] = cnt;
}
void dfs(int x,int fa,int now,int p){
	dis[p][x] = now++;
	for (int i=head[x];i;i=e[i].next)
		if (e[i].y!=fa) dfs(e[i].y,x,now,p);
}
int main(){
	T = read();
	while (T--){
		n = read();m = read();cnt = 0;
		for (int i=1;i<=n;i++) head[i] = 0;
		for (int i=1;i<n;i++) x = read(),y = read(),Insert(x,y),Insert(y,x);
		for (int i=1;i<=m;i++){a[i] = read();b[i] = read();d[i] = read();}
		dfs(1,-1,0,0);x = 0;
		for (int i=1;i<=m;i++){
			t = dis[0][a[i]]+dis[0][b[i]]-d[i];
			if (t>Max || !x) {x = i;Max = t;}
		}
		dfs(a[x],-1,0,1);dfs(b[x],-1,0,2);t = 0;
		for (int i=1;i<=n;i++) 
			if (dis[1][i]+dis[2][i]<=d[x])
				if (!t || Min>dis[0][i]){t = i;Min = dis[0][i];}
		if (!t) {printf("NIE\n");continue;}
		dfs(t,-1,0,0);
		for (int i=1;i<=m;i++)
			if (dis[0][a[i]]+dis[0][b[i]]>d[i]) {t = 0;break;}
		if (t) printf("TAK %d\n",t);else printf("NIE\n");
	}
}
Category: BZOJ题解 | Tags: | Read Count: 381

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com