#include <cstdio>
#include <algorithm>
#include <memory.h>
using std::sort;

const int N = 201;
int p[N];
int rank[N];
int gold[N];
int store[N];

int n, m;

void init()
{
	for(int i = 1; i <= n; i++)
		p[i] = i;
	memset(rank, 0x00, sizeof(rank));
}

int find_set(int x)
{
	if(p[x] == x)
		return x;
	p[x] = find_set(p[x]);
	return p[x];
}

void link(int x, int y)
{
	if(rank[x] > rank[y])
	{
		p[y] = x;
		gold[x] += gold[y];
		store[x] += store[y];
	}
	else
	{
		p[x] = y;
		if(rank[x] == rank[y])
			rank[y]++;
		gold[y] += gold[x];
		store[y] += store[x];
	}
}

void join(int x, int y)
{
	link(find_set(x), find_set(y));
}

bool test()
{
	for(int i = 1; i <= n; i++)
	{
		int r = find_set(i);
		if(gold[r] > store[r])
			return false;
	}
	return true;
}

struct Node
{
	int x;
	int y;
	int d;
	bool operator<(const Node &node) const
	{
		return d<node.d;
	}
};

Node a[N*N];

int main()
{
	while(true)
	{
		scanf("%d", &n);
		if(!n)
			break;
		init();
		int i;
		for(i = 1; i <= n; i++)
			scanf("%d", gold+i);
		for(i = 1; i <= n; i++)
			scanf("%d", store+i);
		
		scanf("%d", &m);
		int x, y, d;
		for(i = 0; i < m; i++)
		{
			scanf("%d%d%d", &x, &y, &d);
			a[i].x = x, a[i].y = y, a[i].d = d;
		}
		
		if(test())
		{
			printf("0\n");
			continue;
		}
		
		sort(a, a+m);
		
		i = 0;
		do
		{
			join(a[i].x, a[i].y);
		}while(!test() && ++i<m);
		
		if(i >= m)
			printf("No Solution\n");
		else
			printf("%d\n", a[i].d);
	}
}

• 危险的错误阿。。。。Re:帮忙看看哪里错了，程序超容易理解，wa了一百遍阿一百遍。 (1790) badboy 2007-05-16 16:39:22
  • Re:危险的错误阿。。。。Re:帮忙看看哪里错了，程序超容易理解，wa了一百遍阿一百遍。 (24) cangratul 2007-05-18 16:54:53