4151: [AMPPZ2014]The Cave
Time Limit: 5 Sec Memory Limit: 256 MBSec Special JudgeSubmit: 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
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
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");
}
}
评论 (0)
