2135.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2135 on 2006-07-23 at 15:42:24 */ 
#include <cstdio>
#include <list>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int MAX = 256;
const int INF = 1 << 25;

class Network {
private:
	int size, r, c, full, h[MAX], e[MAX], cnth[MAX*2];
	int cap[MAX][MAX], flow[MAX][MAX], current[MAX];
	int lc[MAX][MAX], hc[MAX][MAX];
	bool vaild;
	void initFlow(int, int);
	void push(int);
	void relabel(int);
	void discharge(int);
	void gapHeuristic(int);
	int maxFlow(int, int);
public:
	void build();
	bool fullFlow();
	void show() const;
};
void Network::build() {
	full = 0; vaild = true;
	int i, j; scanf("%d %d", &r, &c); size = r+c+2;
	for(i = 0; i < size; i++)
		for(j = 0; j < size; j++)
			lc[i][j] = 0, hc[i][j] = INF;
	memset(cap, 0, sizeof(cap)); memset(flow, 0, sizeof(flow));
	for(i = 0; i < r; i++) {
		int sum; scanf("%d", &sum);
		full += sum; cap[0][i+2] = sum;
		for(j = 0; j < c; j++) hc[i+2][j+r+2] = min(hc[i+2][j+r+2], sum);
	}
	for(i = 0; i < c; i++) {
		int sum; scanf("%d", &sum);
		cap[i+r+2][1] = sum;
		for(j = 0; j < r; j++) hc[j+2][i+r+2] = min(hc[j+2][i+r+2], sum);
	}
	int e, E; scanf("%d", &E);
	for(e = 0; e < E; e++) {
		int tr, tc, v; char op;
		scanf("%d %d\n%c %d", &tr, &tc, &op, &v);
		int rl = (tr == 0) ? 0 : tr-1, rh = (tr == 0) ? r-1 : tr-1;
		int cl = (tc == 0) ? 0 : tc-1, ch = (tc == 0) ? c-1 : tc-1;
		for(i = rl; i <= rh; i++)
			for(j = cl; j <= ch; j++) {
				int cr = i+2, cc = j+r+2;
				switch(op) {
				case '=': lc[cr][cc] = max(lc[cr][cc], v); hc[cr][cc] = min(hc[cr][cc], v); break;
				case '<': hc[cr][cc] = min(hc[cr][cc], v-1); break;
				case '>': lc[cr][cc] = max(lc[cr][cc], v+1); break;
				}
			}
	}
	for(i = 2; i < r+2; i++)
		for(j = r+2; j < r+c+2; j++) {
			int &lmt = hc[i][j], low = lc[i][j];
			lmt -= low;
			cap[0][j] += low; cap[0][i] -= low; cap[i][j] = lmt;
			if(lmt < 0 || cap[0][i] < 0) vaild = false;
		}
}
void Network::push(int u) {
	int ex = min(cap[u][current[u]], e[u]);
	e[u] -= ex; e[current[u]] += ex; cap[u][current[u]] -= ex; cap[current[u]][u] += ex;
	flow[u][current[u]] += ex; flow[current[u]][u] -= ex;
}
void Network::relabel(int u) {
	int mh = INF, i;
	for(i = 0; i < size; i++) 
		if(cap[u][i] > 0) mh = min(mh, h[i]);
	if(--cnth[h[u]] == 0) gapHeuristic(h[u]);
	h[u] = mh + 1; cnth[h[u]]++;
}
void Network::discharge(int u) {
	while(e[u] > 0)
		if(current[u] == size) { relabel(u); current[u] = 0; }
		else if(cap[u][current[u]] > 0 && h[u] == h[current[u]] + 1) push(u);
		else current[u]++;
}
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;
	int i;
	for(i = 0; i < size; i++) { 
		e[s] -= cap[s][i]; e[i] += cap[s][i];
		cap[i][s] -= cap[s][i]; cap[s][i] = 0;
	}
}
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+1) {
			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] = 0;
		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];
}
bool Network::fullFlow() {
	return (maxFlow(0, 1) == full);
}
void Network::show() const {
	int i, j;
	for(i = 0; i < r; i++)
		for(j = 0; j < c; j++)
			printf("%d%c", flow[i+2][j+r+2]+lc[i+2][j+r+2], (j == c-1) ? '\n' : ' ');
}

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

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		if(t != 1) putchar('\n');
		net.build();
		if(!net.fullFlow()) printf("IMPOSSIBLE\n");
		else net.show();
	}

	return 0;
}