1487.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1487 on 2006-08-02 at 10:48:09 */ 
#include <cstdio>
#include <cstring>
 
const int MAX = 128;
 
int power[MAX];
bool ship[MAX][MAX];
int max;
 
void fleet(int*, int, int);
 
int main()
{
	int n, m;
	int i, t;
	
	for(t = 1; scanf("%d %d", &n, &m) != EOF && n != 0; t++) {
		for(i = 0; i < n; i++) {
			scanf("%d", &power[i]);
		}
		memset(ship, true, sizeof(ship));
		for(i = 0; i < m; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			ship[y][x] = ship[x][y] = false;
		}
		max = 0;
		if(m == 0) {
			for(i = 0; i < n; i++) {
				max += power[i];
			}
		} else {
			int stack[MAX], top = 0;
			for(i = 0; i < n; i++) {
				stack[top++] = i;
			}
			fleet(stack, top, 0);
		}
		printf("Case %d: %d\n", t, max);
	}
	
	return 0;
}
 
void fleet(int* con, int n, int prev)
{
	if(n == 0) {
		if(max < prev) {
			max = prev;
		}
	} else {
		int i, j;
		for(i = 0; i < n; i++) {
			int stack[MAX], top = 0;
			int total = power[con[i]] + prev;
			for(j = i+1; j < n; j++) {
				if(ship[con[i]][con[j]]) {
					stack[top++] = con[j];
					total += power[con[j]];
				}
			}
			if(total > max) {
				fleet(stack, top, prev+power[con[i]]);
			}
		}
	}
}