UVa 10099 - The Tourist Guide

题目：有一个导游，要带领团队从当前点，走到目标点，但是每条路一次性通过的人有数量限制，

            所以需要分批次进行。问最少需要分多少次进行。

分析：贪心，最短路或最小生成树。图上贪心性质的扩散问题，可以作为最短路或者最小生成树求解。

            问题的贪心特性成立很容易证明。

            设集合A为当前计算的结果，则对于p∈A且q不在A中，如果点q加入集合A则满足p到q的路径为最宽。

          （反证法：如果存在更宽路径，则q应该更早加入，矛盾）

            由于满足贪心特性，所以利用kruskal，dijikstra等贪心算法只须最简单修改即可，

            每次按路径上的最小值跟新，而不是路径和即可。

注意：每次导游都要回去带人。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

#define oo 0x7fffffff

using namespace std;

typedef struct d_node
{
	int point1;
	int point2;
	int weight;
}enode;
enode edge[10001];

//union_set
int sets[101];
int rank[101];

void set_inital( int a, int b )
{
	for ( int i = a ; i <= b ; ++ i ) {
		rank[i] = 0;
		sets[i] = i;
	}
}

int  set_find( int a )
{
	if ( a != sets[a] )
		sets[a] = set_find( sets[a] );
	return sets[a];
}

void set_union( int a, int b )
{
	if ( rank[a] < rank[b] )
		sets[a] = b;
	else {
		if ( rank[a] == rank[b] )
			rank[a] ++;
		sets[b] = a;
	}
}
//end_union_set

int cmp_e( enode a, enode b )
{
	return a.weight > b.weight;
}

int vector[101];
int kruskal( int n, int r, int s, int t )
{
	set_inital( 1, n );
	for ( int i = 1 ; i <= n ; ++ i )
		vector[i] = oo;
	
	sort( edge, edge+r, cmp_e );
	for ( int i = 0 ; i < r ; ++ i ) {
		int A = set_find( edge[i].point1 );
		int B = set_find( edge[i].point2 );
		if ( A != B ) {
			set_union( A, B );
			int mid = min( vector[A], vector[B] );
			vector[set_find(A)] = min( mid, edge[i].weight );
			if ( set_find( s ) == set_find( t ) )
				return vector[set_find(s)];
		}
	}
	return -1;
}

int main()
{
	int N,R,a,b,c,s,t,p,C = 1;
	while ( scanf("%d%d",&N,&R) && N+R ) {
		for ( int i = 0 ; i < R ; ++ i ) {
			scanf("%d%d%d",&a,&b,&c);
			edge[i].point1 = a;
			edge[i].point2 = b;
			edge[i].weight = c;
		}
		scanf("%d%d%d",&s,&t,&p);
		
		int W = kruskal( N, R, s, t );
		int A = p/(W-1) + (p%(W-1) != 0);
		printf("Scenario #%d\nMinimum Number of Trips = %d\n\n",C ++,A);
	}
	return 0;
}

UVa 10099 - The Tourist Guide,布布扣,bubuko.com

UVa 10099 - The Tourist Guide

原文：http://blog.csdn.net/mobius_strip/article/details/21736353