2194.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2194 on 2006-08-08 at 12:16:11 */ 
#include <cstdio>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
 
const int N = 840;
const int INF = 1 << 28;
const int L = 32;
const int DIR[][2] = { { 1, 1 }, { -1, -1 }, { 1, -1 }, { -1, 1 } };
 
int w, hi;
 
bool legal(int x, int y) { return (x >= 0 && x < hi && y >= 0 && y < w); }
int in(int o) { return 2*o+1; }
int out(int o) { return 2*o+2; }
 
class Edge {
public:
	int u, v, cuv, cvu, flow;
	Edge() {}
	Edge(int cu, int cv, int ccu, int ccv) : u(cu), v(cv), cuv(ccu), cvu(ccv), flow(0) {}
	int other(int p) const { return p == u ? v : u; }
	int cap(int p) const { return p == u ? cuv-flow : cvu+flow; }
	void addFlow(int p, int f) { flow += (p == u ? f : -f); } 
};
 
class Room {
private:
	vector<Edge> eg;
	Edge* net[N][2*N], *prev[N];
	int nn[N], v, s, t, ln;
	int h[N], hn[2*N], e[N], cur[N];
	void initNet();
	void initFlow();
	void gapHeuristic(int);
public:
	void make();
	int maxFlow(int, int);
};
void Room::gapHeuristic(int k) {
	if(hn[k] != 0) return;
	int i;
	for(i = 0; i < v; i++)
		if(h[i] > k) h[i] = v;
	for(i = k; i < v; i++)
		{ hn[v] += hn[i]; hn[i] = 0; }
}
void Room::initNet() {
	int i;
	memset(nn, 0, sizeof(nn));
	for(i = eg.size()-1; i >= 0; i--) {
		net[eg[i].u][nn[eg[i].u]++] = &eg[i];
		net[eg[i].v][nn[eg[i].v]++] = &eg[i];
	}
}
void Room::initFlow() {
	initNet();
	memset(h, 0, sizeof(h));
	memset(hn, 0, sizeof(hn)); hn[0] = v;
	int i;
	for(i = 0; i < v; i++) cur[i] = nn[i]-1;
}
void Room::make() {
	int range, i, j, k; char map[L][L];
	scanf("%d %d\n", &hi, &range);
	for(i = 0; i < hi; i++) gets(map[i]);
	w = strlen(map[0]);
	int s = 0, t = 2*w*hi+1; v = 2*w*hi+2;
	eg.clear();
	for(i = 0; i < hi; i++) {
		for(j = 0; j < w; j++) {
			int ii = in(i*w+j), oi = out(i*w+j);
			if(map[i][j] != '0') eg.push_back(Edge(ii, oi, map[i][j]-'0', 0));
			int c, r;
			for(c = 0; c <= range; c++)
				for(r = 0; r <= range-c; r++)
					for(k = 0; k < 4; k++) {
						int cx = i+r*DIR[k][0], cy = j+c*DIR[k][1];
						if(!legal(cx, cy)) eg.push_back(Edge(oi, t, INF, 0)); 
						else eg.push_back(Edge(oi, in(cx*w+cy), INF, 0));
					}
		}
	}
	for(ln = i = 0; i < hi; i++) {
		gets(map[i]);
		for(j = 0; j < w; j++)
			if(map[i][j] == 'L') { eg.push_back(Edge(s, in(i*w+j), 1, 0)); ln++; }
	}
}
int Room::maxFlow(int ss, int tt) {
	s = ss; t = tt; initFlow();
	int c = s, i, pre[N], flow = 0;
	pre[s] = -1;
	while(h[s] < v) {
		for(; cur[c] >= 0; cur[c]--)
			if(net[c][cur[c]]->cap(c) != 0 && h[c] == h[net[c][cur[c]]->other(c)]+1) break;
		if(cur[c] < 0) {
			int mh = INF, oh = h[c];
			for(i = nn[c]-1; i >= 0; i--)
				if(net[c][i]->cap(c) != 0) mh = min(mh, h[net[c][i]->other(c)]);
			if(mh == INF) h[c] = v;
			else { h[c] = mh+1; cur[c] = nn[c]-1; }
			hn[oh]--; hn[h[c]]++; gapHeuristic(oh);
			if(c != s) c = pre[c];
		} else {
			int p = net[c][cur[c]]->other(c);
			prev[p] = net[c][cur[c]];
			pre[p] = c; c = p;
			if(c == t) {
				int ex = INF;
				for(; c != s; c = pre[c])
					ex = min(ex, prev[c]->cap(pre[c]));
				for(c = t; c != s; c = pre[c])
					prev[c]->addFlow(pre[c], ex);
				flow += ex; c = s;
			}
		}
	}
	return ln-flow;
}
 
Room room;
 
int main()
{
	int t, T;

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		room.make();
		int dead = room.maxFlow(0, 2*w*hi+1);
		printf("Case #%d: ", t);
		if(dead == 0) printf("no");
		else printf("%d", dead);
		printf(" lizard%s left behind.\n", (dead < 2) ? " was" : "s were");
	}
	
	return 0;
}