1003.Emergency

2017-10-18

英文描述

Emergency (25)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, you job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input Specification:
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N(<= 500) – the number of cities(and the cities are numbered from 0 to N – 1), M – the number of roads, C1 and C2 – the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.
Output Specification:
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4

中文描述

紧急情况

身为一个城市的紧急救援队的领导，你应该为你的国家提供一张特殊的地图。这张地图展示了被道路连接着的一些散落的城市。每座城市救援队的总数和每对城市之间道路的长度被标记在地图上。当其他城处于紧急状况呼叫你的时候，你的工作是领导你的救援队尽可能快的赶到处于紧急状况的城市，与此同时竟可能多的呼叫正在路上的救援队。
输入规格：
每个文件包含一个测试用例。对于每一个测试用例，第一行包含4个整数：N（ <= 500）- 城市的数量（城市标号范围从0到N – 1），M – 道路的数量，C1和C2 – 你当前所在城市和你必须营救的城市。下一行包含N个整数，第i个整数代表第i城市中营救队的数量。此外的M行中，每一行描述由3个整数c1，c2和L组成的一条道路，c1和c2是一对被一条道路连接的城市，L是这条路的长度。此测试用例保证C1和C2之间至少存在一条道路。
输出规格：
对于每一个测试用例，在一行内输出2个数：C1和C2之间不同最短路径的数量和你可能召集的最大的营救队总数。在一行内的所有数字必须被一个额外的空格间隔开来并且在这个行的末尾没有额外的空格。
样例输入:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
样例输出:
2 4

分析与解题

问题：1. 求最短路径条数。2. 在多条最短路径中，求节点权值（营救队数量）之和的最大值。根据最短路径中上界性质：设G = (V , E)为一个带权重的有向图，其权重函数由w：E→R给出，其源节点为s，改图由算法INITIALIZE-SINGLE-SOURCE(G, s)执行初始化。那么对于所有的节点v∈V，v.d >= δ(s, v)，并且该不变式在对图G的边进行任何次序的松弛过程中保存成立。而且，一旦v.d取得其下届δ(s, v)后，将不再发生变化。简要解释一下这个性质的含义。提出这个性质的问题描述是这样的：最短路径估计的值将会如何变化（最短估计路径也就是性质中的d值）。结论中的δ函数是指源节点到v节点的最短路径（注意此处是最短路径，并非最短路径估计值），也就是说最短估计路径的的值d（此后将用d来描述）将永远大于或者等于最短路径值。讲到这里需要提一下最短路径的引理：三角不等式，δ(s, v) <= δ(s, u) + w(u, v)，这个例子我采用一种比较通俗的语言来解释，假设源节点s到目标节点d，存在一条最短路径p，p路径途径（u，v）这条边，也就是这条路径中是先到达u后到达v，那么也就是说，s到v的最短路径永远小于或者等于s到u的最短路径加上(u，v)这条路径本身的长度。举个生活中的例子，假如你从北京到广东，途径郑州和长沙，也就是说从北京到长沙的距离永远小于或者等于从北京到郑州的距离加上郑州到长沙的距离，也就是公式的由来δ(s, v) <= δ(s, u) + w(u, v)。接着，我们需要讲述另一个话题：松弛，所谓松弛也就是说根据情况来更新d的值，当一条边（u, v）中，如果v.d >= u.d + w(u, v)时就来更新v.d的值，令v.d = u.d + w(u, v)。通俗点讲是这样的，你从北京到郑州，有两条路，一条为北京-邯郸-郑州，另一条为北京-拉萨-郑州，当你算了一下北京到邯郸474km，北京-拉萨-郑州4064km，假如此刻v.d是4064km也就是北京-拉萨-郑州这条路，当你去查看u.d + w(u, v)时，也就是北京-邯郸为u.d，w(u, v)为邯郸到郑州的距离252，当4064 >= 474 + 252，也就是北京-拉萨-郑州这条路，要比北京-邯郸-郑州要长时，你就会去选择北京-邯郸-郑州这条路。言归正传，我们可以把上界性质中的d理解为三角不等式中的δ(s, u) + w(u, v)，所以说，d将永远大于或者等于δ。此处有一个隐含了的条件。也就是v.d = δ(s, v)时候，v.d的值将不再变化。因此你可以利用这一点来求的多条最短路径，也就是说，当你发现v.d == u.d + w(u, v)时，意味着已经找到了两条相同的最短路径。

C语言实现

/*  Emergency:shortest path
*	图结构采用邻接表，最短路径算法采用dijkstra

*   init() 初始化操作，将除了源节点外的其他节点
		   d值赋值无穷，营救小队最大值初始化为0
*	relax() 如果v.d的值大于v.d + w(u, v)将v.d赋
		    值为v.d + w(u, v), 将v.maxamount = 
			u.maxamount + v.rescue, 将v.shortsum
			= u.shortsum
			如果v.d == v.d + w(u, v), v->shortsum 
			= v->shortsum + u->shortsum, 如v->maxamount
			小于u->maxamount + v->rescue的话，将
			v->maxamount = u->maxamount + v->rescue
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct arcnode
{
	int length;
	int info; //城市标号
	struct arcnode *next;
}arcnode;
typedef struct vernode
{
	int d;
	int info; //城市标号
	int shortsum;   //最短路径条数
	int maxamount;  //不同最短路径营救小队最大值
	int rescue;    //每座城市营救小队数量
	int visited;   //最小优先队列使用
	arcnode *next;
}vernode;
typedef struct
{
	vernode vertex[502];
	int versum, arcsum;
}AdjList;
void init(AdjList *G, vernode *s)
{
	int i = 1;
	while(i <= G->versum)
	{
		G->vertex[i].d = 65536; 
		G->vertex[i].maxamount = 0; //营救小队最大值初始化
		G->vertex[i].visited = 0;  //访问标记
		i++;
	}
	s->d = 0;
	s->shortsum = 1;
	s->maxamount = s->rescue;
}
void relax(vernode *u, vernode *v, int weight)
{
	if(v->d > (u->d + weight))
	{
		v->d = (u->d + weight);
		v->maxamount = v->rescue + u->maxamount; 
		v->shortsum = u->shortsum;
	}
	else if(v->d == (u->d + weight))
	{
		v->shortsum += u->shortsum;
		if(v->maxamount < (u->maxamount + v->rescue))
			v->maxamount = u->maxamount + v->rescue;
	}
}
vernode *search(AdjList *G, arcnode *e)
{
	int i = 1;
	while(i <= G->versum)
	{
		if(G->vertex[i].info == e->info)
			return &G->vertex[i];
		i++;
	}
}
vernode *findmin(AdjList *G)
{
	int i = 1;
	int min = 65536;
	while(i <= G->versum)
	{
		if(G->vertex[i].visited != 1)
		{
			//search for min
			if(min > G->vertex[i].d)
				min = G->vertex[i].d;
		}
		i++;
	}
	i = 1;
	while(i <= G->versum)
	{
		if(G->vertex[i].visited != 1)
		{
			if(min == G->vertex[i].d)
			{
				G->vertex[i].visited = 1;
				return &G->vertex[i];
			}
		}
		i++;
	}
}
void dijkstra(AdjList *G, vernode *s)
{
	init(G, s);
	int i = 1;
	while(i <= G->versum)
	{
		vernode *u = findmin(G);
		arcnode *e = u->next;
		while(e != NULL)
		{
			vernode *v = search(G, e);
			relax(u, v, e->length);
			e = e->next;
		}
		i++;
	}
}
void insert(vernode *L, arcnode *x)
{
	x->next = L->next;
	L->next = x;
}
void input(AdjList *G, int *source, int *destination)
{
	scanf("%d%d%d%d", &G->versum, &G->arcsum, source, destination);
	int i = 1;
	while(i <= G->versum)
	{
		scanf("%d", &G->vertex[i].rescue);
		G->vertex[i].info = i - 1;
		G->vertex[i].next = NULL;
		i++;
	}
	i = 1;
	int s, d, w;
	while(i <= G->arcsum)
	{
		scanf("%d%d%d", &s, &d, &w);
		int j = 1;
		while(j <= G->versum)
		{
			if(s == G->vertex[j].info)
			{
				arcnode *p = (arcnode*)malloc(sizeof(arcnode));
				p->info = d;
				p->length = w;
				insert(&G->vertex[j], p);
			}
			if(d == G->vertex[j].info)
			{
				arcnode *p = (arcnode*)malloc(sizeof(arcnode));
				p->info = s;
				p->length = w;
				insert(&G->vertex[j], p);
			}
			j++;
		}
		i++;
	}
}
void output(AdjList *G, int destination)
{
	printf("%d %d\n",G->vertex[destination].shortsum, G->vertex[destination].maxamount);
}
void emergency()
{
	AdjList a;
	int s, d;
	input(&a, &s, &d);
	if(s != d)
	{
		dijkstra(&a, &a.vertex[s + 1]);
		output(&a, d + 1);
	}
	else
	{
		printf("%d %d\n", 1, a.vertex[d + 1].rescue);
	}
}
int main()
{
	emergency();
	return 0;
}

测试链接

click me