现在的位置: 首页 > 综合 > 正文

树上的三角形 –Beauty of Programming(2013全国挑战赛)

2018年04月01日 ⁄ 综合 ⁄ 共 2781字 ⁄ 字号 评论关闭

描述

有一棵树,树上有只毛毛虫。它在这棵树上生活了很久,对它的构造了如指掌。所以它在树上从来都是走最短路,不会绕路。它还还特别喜欢三角形,所以当它在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢?

输入

输入数据的第一行包含一个整数 T,表示数据组数。

接下来有 T 组数据,每组数据中:

第一行包含一个整数 N,表示树上节点的个数(从 1 到 N 标号)。

接下来的 N-1 行包含三个整数 a, b, len,表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 M,表示询问数。

接下来M行每行两个整数 S, T,表示毛毛虫从 S 爬行到了 T,询问这段路程中的树枝/树干是否能拼成三角形。

输出

对于每组数据,先输出一行"Case #X:",其中X为数据组数编号,从 1 开始。

接下来对于每个询问输出一行,包含"Yes"或“No”,表示是否可以拼成三角形。

数据范围

1 ≤ T ≤ 5

小数据:1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000

大数据:1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
样例输出
Case #1:
No
Yes
Case #2:
No
Yes
//source here
#include<stdio.h>
#include<string>
#include<memory.h>
#include<stdlib.h>
using namespace std;
struct load{
    int dian;
    load*next;
};
int shortload(int start,int juzhen[][105],int dian,load **load_path);
//const int INF=0x3f3f3f3f;
const int INF=10000000;
int visit[105];
int juzhen[105][105];
int dis[105];
int path[105][105];
load * load_path[105];
int main()
{
	int zu,x=1;
	scanf("%d",&zu);
	while(zu--)
	{
		printf("Case #%d:\n",x);
		x++;
		int dian,line,chang;
		int start_x,end_x;
		int i,j,k,l; 
		scanf("%d",&dian);
		for( i=0;i<dian;i++)
			for( j=0;j<dian;j++)
				juzhen[i][j]=INF;

		for(i=0;i<dian-1;i++)
		{
			int start,end;
			scanf("%d%d%d",&start,&end,&chang);
			juzhen[start-1][end-1]=juzhen[end-1][start-1]=chang;
		}
		int ceshi;
		scanf("%d",&ceshi);
		while(ceshi--)
		{
			memset(path,0,105*105*sizeof(int ));
			scanf("%d%d",&start_x,&end_x);
			for( i=0;i<dian;i++)
			{ 
				load_path[i]=(load*)malloc(sizeof(load));
				load_path[i]->dian=start_x-1;
				load* p=(load*)malloc(sizeof(load));
				p->dian=i;
				p->next=NULL;
				load_path[i]->next=p;
			}
			shortload(start_x-1,juzhen,dian,load_path);
			load* p=load_path[end_x-1];
			i=0;
			if(p)
			{
				while(p->next) 
				{
					path[end_x-1][i]=juzhen[p->dian][p->next->dian];
					i++;   
					p=p->next;
				}
			}
			int flag=0;
			if(i<3)
				printf("No\n");
			else 
			{
				for(j=0;j<i-2;j++)
					for( k=j+1;k<i-1;k++) 
						for(l=k+1;l<i;l++)
						{
							if((path[end_x-1][j]+path[end_x-1][k]>path[end_x-1][l])&&(path[end_x-1][j]-path[end_x-1][k]<path[end_x-1][l])
								&&(path[end_x-1][j]+path[end_x-1][l]>path[end_x-1][k])&&(path[end_x-1][j]-path[end_x-1][l]<path[end_x-1][k])
								&&(path[end_x-1][k]+path[end_x-1][l]>path[end_x-1][j])&&(path[end_x-1][k]-path[end_x-1][l]<path[end_x-1][j])
								)
							{
								printf("Yes\n"); 
								flag=1;
								k=i-1;
								j=i-2;
								break;
							}
						}
						if(flag==0)
							printf("No\n");
			}
		}
	}
}
int shortload(int start,int juzhen[][105],int dian,load ** load_path)
{
	for(int i=0;i<dian;i++)
	{
		dis[i]=juzhen[start][i];
		visit[i]=0;
	}
	visit[start]=1;
	dis[start]=0;
	int x=0;
	for(int i=0;i<dian;i++)
	{
		int min=INF;
		for(int j=0;j<dian;j++)
		{
			if(dis[j]<min&&visit[j]==0)
			{
				min=dis[j];
				x=j;
			}
		}
		visit[x]=1;
		for(int j=0;j<dian;j++)
			if(visit[j]==0&&dis[x]+juzhen[x][j]<dis[j])
			{
				load*p=load_path[x]->next;
				while(p)
				{
					load* q=(load*)malloc(sizeof(load));
					q->next=load_path[j]->next;
					load_path[j]->next=q;
					p=p->next;
				}
				p=load_path[x]->next;
				load*q=load_path[j]->next;
				while(p)
				{
					q->dian=p->dian;
					p=p->next;
					q=q->next;
				}
				dis[j]=dis[x]+juzhen[x][j];
			}     
	}
	return 0;
}

抱歉!评论已关闭.