1294.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1294 on 2006-04-14 at 17:42:58 */ 
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int JM = 256;
const int INF = 1 << 28;

class Network {
private:
	int size, full, h[JM], e[JM], cnth[JM*2];
	list<pii> n[JM];
	list<pii>::iterator current[JM];
	bool vaild;
	void insert(int, int, int);
	void initFlow(int, int);
	void push(int);
	void relabel(int);
	void discharge(int);
	void gapHeuristic(int);
	int maxFlow(int, int);
public:
	void make();
	bool tour();
};
void Network::insert(int u, int v, int ex) {
	list<pii>::iterator it;
	for(it = n[u].begin(); it != n[u].end(); it++)
		if(it->first == v) { it->second += ex; return; }
	n[u].push_back(pii(v, ex));
}
void Network::initFlow(int s, int t) {
	memset(h, 0, sizeof(h)); h[s] = size;
	memset(e, 0, sizeof(e));
	memset(cnth, 0, sizeof(cnth)); cnth[size] = 1; cnth[0] = size-1;
	list<pii>::iterator it;
	for(it = n[s].begin(); it != n[s].end(); it++) {
		int v = it->first, &cap = it->second;
		e[s] -= cap; e[v] += cap;
		insert(v, s, cap); cap = 0;
	}
}
void Network::push(int u) {
	int v = current[u]->first, &cap = current[u]->second, ex = min(cap, e[u]);
	e[u] -= ex; e[v] += ex; cap -= ex; insert(v, u, ex);
}
void Network::relabel(int u) {
	list<pii>::iterator it; int mh = INF;
	for(it = n[u].begin(); it != n[u].end(); it++)
		if(it->second > 0) mh = min(mh, h[it->first]+1);
	if(--cnth[h[u]] == 0) gapHeuristic(h[u]);
	cnth[mh]++; h[u] = mh;
}
void Network::discharge(int u) {
	while(e[u] > 0)
		if(current[u] == n[u].end()) { relabel(u); current[u] = n[u].begin(); }
		else if(current[u]->second > 0 && h[u] == h[current[u]->first] + 1) push(u);
		else current[u]++;
}
void Network::gapHeuristic(int k) {
	if(k >= size+1) return;
	int i;
	for(i = 0; i < size; i++)
		if(h[i] > k && h[i] <= size && i != 0)
			{ cnth[h[i]]--; h[i] = size+1; cnth[size+1]++; }
}
int Network::maxFlow(int s, int t) {
	if(!vaild) return -INF;
	initFlow(s, t);
	int i; list<int> L;
	for(i = 0; i < size; i++) {
		current[i] = n[i].begin();
		if(i != s && i != t) L.push_back(i);
	}
	list<int>::iterator u;
	for(u = L.begin(); u != L.end(); u++) {
		int oh = h[*u];
		discharge(*u);
		if(oh != h[*u]) { L.push_front(*u); L.erase(u); u = L.begin(); }
	}
	return e[t];
}
void Network::make() {
	int id[JM], od[JM], m, i;
	scanf("%d %d", &size, &m); size += 2;
	for(i = 0; i < size; i++) n[i].clear(), id[i] = od[i] = 0;
	for(i = 0; i < m; i++) {
		int a, b, o; scanf("%d %d %d", &a, &b, &o); a++; b++;
		od[a]++; id[b]++;
		if(o == 0) n[a].push_back(pii(b, 1));
	}
	vaild = true; full = 0;
	for(i = 2; i < size && vaild; i++)
		if((id[i]&1) != (od[i]&1)) vaild = false;
		else if(id[i] > od[i]) n[i].push_back(pii(1, (id[i]-od[i])/2));
		else if(id[i] < od[i]) { n[0].push_back(pii(i, (od[i]-id[i])/2)); full += (od[i]-id[i])/2; }
}
bool Network::tour() {
	return maxFlow(0, 1) == full;
}

int main()
{
	Network net;
	int t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		net.make();
		printf("%spossible\n", net.tour() ? "" : "im");
	}

	return 0;
}