1297.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1297 on 2006-04-22 at 10:42:05 */ 
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

const int SN = 256;

class Graph {
private:
	vector<int> neib[SN];
	int n, d[SN], state[SN], best[SN][2];
public:
	bool build();
	int maxSafe();
};
bool Graph::build() {
	set<int> photon;
	int i, j, m; scanf("%d %d", &n, &m);
	if(n == 0) return false;
	memset(best, 0, sizeof(best)); memset(d, 0, sizeof(d));
	for(i = 0; i < n; i++) { scanf("%d", &state[i]); neib[i].clear(); }
	for(i = 0; i < m; i++) {
		int pe; scanf("%d", &pe);
		photon.insert(pe);
	}
	for(i = 0; i < n; i++)
		for(j = i+1; j < n; j++)
			if(photon.count(state[j]-state[i]) != 0)
				{ neib[i].push_back(j); neib[j].push_back(i); d[i]++; d[j]++; }
	return true;
}
int Graph::maxSafe() {
	int i, stack[SN], top = 0;
	for(i = 0; i < n; i++)
		if(d[i] <= 1) stack[top++] = i;
	int energy = 0;
	while(top > 0) {
		int p = stack[--top];
		best[p][1] += state[p];
		if(d[p] == 0) energy += max(best[p][0], best[p][1]);
		for(i = 0; i < (int)neib[p].size(); i++) {
			int o = neib[p][i];
			best[o][0] += max(best[p][0], best[p][1]);
			best[o][1] += best[p][0];
			if(--d[o] == 1) stack[top++] = o;
		}
	}
	return energy;
}

int main()
{
	Graph g;

	while(g.build()) printf("%d\n", g.maxSafe());
	
	return 0;
}