1345.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1345 on 2005-12-17 at 17:06:22 */ 
#include <cstdio>
#include <cstring>
#include <list>
#include <queue>
using namespace std;

const int N_MAX = 128;
const int MAX = 4 * N_MAX;
const int INF = 65536;
const int HASH_LIMIT = 523;
const int L_MAX = 32;

class Network {
private:
	int prev[MAX];
	bool augmentable(int, int);
public:
	int size;
	int cap[MAX][MAX];
	void clear();
	int maxFlow(int, int);
};
bool Network::augmentable(int s, int t) {
	memset(prev, -1, sizeof(prev));
	prev[s] = s;
	queue<int> queue;
	queue.push(s);
	while(!queue.empty()) {
		int p = queue.front(), i;
		queue.pop();
		for(i = 0; i < size; i++) {
			if(cap[p][i] > 0 && prev[i] == -1) {
				prev[i] = p;
				if(i == t) {
					return true;
				} else {
					queue.push(i);
				}
			}
		}
	}
	return false;
}
void Network::clear() {
	memset(cap, 0, sizeof(cap));
}
int Network::maxFlow(int s, int t) {
	int flow = 0;
	while(augmentable(s, t)) {
		int extend = INF, i;
		for(i = t; i != s; i = prev[i]) {
			if(extend > cap[prev[i]][i]) {
				extend = cap[prev[i]][i];
			}
		}
		for(i = t; i != s; i = prev[i]) {
			cap[prev[i]][i] -= extend;
			cap[i][prev[i]] += extend;
		}
		flow += extend;
	}
	return flow;
}

class Plug {
public:
	char name[L_MAX];
};

class HashTable {
public:
	static int hash(const char*);
	list<int> table[HASH_LIMIT];
	void clear();
};
int HashTable::hash(const char* str) {
	int i, l = (strlen(str)+1) / 2;
	unsigned int ret = 0;
	unsigned short *s = (unsigned short*)str;
	for (i = 0; i < l; i++) {
		ret ^= (s[i] << (i & 0x0F));
	}
	return ret % HASH_LIMIT;
}
void HashTable::clear() {
	int i;
	for(i = 0; i < HASH_LIMIT; i++) {
		table[i].clear();
	}
}

Plug plug[MAX];
HashTable ht;

int find(const char*, const int);

int main()
{
	Network net;
	list<int> pl, dl;
	int n, m, k, i;
	int x, T;
	
	scanf("%d", &T);
	for(x = 0; x < T; x++) {
		if(x != 0) putchar('\n');
		int tn = 0, num[N_MAX] = { 0 };
		pl.clear(); dl.clear(); ht.clear(); net.clear();
		scanf("%d", &n);
		for(i = 0; i < n; i++) {
			scanf("%s", plug[tn].name);
			int code = HashTable::hash(plug[tn].name);
			int o = find(plug[tn].name, code);
			if(o != -1) {
				num[o]++;
			} else {
				num[tn] = 1;
				pl.push_back(tn);
				ht.table[code].push_back(tn++);
			}
		}
		scanf("%d", &m);
		for(i = 0; i < m; i++) {
			int de = tn++, o;
			dl.push_back(de);
			scanf("%*s %s", plug[tn].name);
			int code = HashTable::hash(plug[tn].name);
			o = find(plug[tn].name, code);
			if(o == -1) {
				ht.table[code].push_back(tn);
				o = tn++;
			}
			net.cap[o][de] = 1;
		}
		scanf("%d", &k);
		for(i = 0; i < k; i++) {
			Plug &sale1 = plug[tn], &sale2 = plug[tn+1];
			scanf("%s %s", sale1.name, sale2.name);
			int code1 = HashTable::hash(sale1.name);
			int code2 = HashTable::hash(sale2.name);
			int o1 = find(sale1.name, code1);
			int o2 = find(sale2.name, code2);
			if(o1 == -1) {
				ht.table[code1].push_back(tn);
				o1 = tn++;
			}
			if(o2 == -1) {
				ht.table[code2].push_back(tn);
				o2 = tn++;
			}
			net.cap[o2][o1] = INF;
		}
		list<int>::iterator it;
		int s = tn++, t = tn++;
		for(it = pl.begin(), i = 0; it != pl.end(); it++, i++) {
			net.cap[s][*it] = num[i];
		}
		for(it = dl.begin(); it != dl.end(); it++) {
			net.cap[*it][t] = 1;
		}
		net.size = tn;
		printf("%d\n", m-net.maxFlow(s, t));
	}
	
	return 0;
}

int find(const char* s, const int code)
{
	if(!ht.table[code].empty()) {
		list<int>::iterator it;
		for(it = ht.table[code].begin(); it != ht.table[code].end(); it++) {
			if(!strcmp(s, plug[*it].name)) {
				return *it;
			}
		}
	}
	return -1;
}