> #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:危险的错误阿。。。。Re:帮忙看看哪里错了，程序超容易理解，wa了一百遍阿一百遍。 (24) cangratul 2007-05-18 16:54:53