bzoj1066: [SCOI2007]蜥蜴

每个点(i,j)，(i,j)→(i,j)'连上容量为h[i][j]的边。(i,j)为入点。(i,j)'为出点

对于所有有蜥蜴的点，从S给它连一条容量为1的边。对于所有可以跳到外面的点，连到T，容量是h[i][j]。

网络流跑一遍

const int N = 30;
struct Point {
	int Ox, Oy, H;
	Point() {}
	Point(int _Ox, int _Oy, int _H) : Ox(_Ox), Oy(_Oy), H(_H) {}
} Dat[sqr(N)], Start[sqr(N)];
struct Edge {
	int V, Val;
	Edge *Next, *Pair;
	Edge() {}
	Edge(int _V, int _Val, Edge *_Next) : V(_V), Val(_Val), Next(_Next) {}
} *Fir[sqr(N) << 1];
int n, m, Dis, Tot, Sum;
int H[sqr(N) << 1], Gap[sqr(N) << 1], S, T;

char Str[N];
inline void Input() {
	scanf("%d%d%d", &n, &m, &Dis), getchar();
	Tot = Sum = 0;
	For(i, 1, n) {
		scanf("%s", Str + 1), getchar();
		For(j, 1, m)
			if(Str[j] != '0') Dat[++Tot] = Point(i, j, Str[j] - '0');
	}
	For(i, 1, n) {
		scanf("%s", Str + 1), getchar();
		For(j, 1, m)
			if(Str[j] == 'L') Start[++Sum] = Point(i, j, 0);
	}
}

#define Num(x, y) (((x) - 1) * (m) + (y))
#define In(x) (x)
#define Out(x) ((x) + ((n) * (m)))
inline void insert(int u, int v, int c) {
	Fir[u] = new Edge(v, c, Fir[u]), Fir[v] = new Edge(u, 0, Fir[v]);
	Fir[u]->Pair = Fir[v], Fir[v]->Pair = Fir[u];
}

inline int Sap(int u, int last) {
	int MinH = T, use = last, v;
	if(u == T) return last;
	for(Edge *Tab = Fir[u]; Tab != NULL; Tab = Tab->Next)
		if(Tab->Val > 0) {
			if(H[u] == H[v = Tab->V] + 1) {
				int flow = Sap(v, min(use, Tab->Val));
				Tab->Val -= flow, Tab->Pair->Val += flow, use -= flow;
				if(H[S] >= T) return last - use;
				if(!use) break;
			}
			MinH = min(MinH, H[v]);
		}
	if(use == last) {
		if(!(--Gap[H[u]])) H[S] = T;
		Gap[H[u] = MinH + 1]++;
	}
	return last - use;
}

inline void Solve() {
	// Build
	For(i, 1, Tot) {
		int u = Num(Dat[i].Ox, Dat[i].Oy), v;
		For(j, i + 1, Tot)
			if(sqr(Dat[i].Ox - Dat[j].Ox) + sqr(Dat[i].Oy - Dat[j].Oy) <= sqr(Dis)) {
				v = Num(Dat[j].Ox, Dat[j].Oy);
				insert(Out(u), In(v), INF), insert(Out(v), In(u), INF);
			}
		insert(In(u), Out(u), Dat[i].H);
	}
	S = ((n * m) << 1) + 1;
	T = S + 1;
	For(i, 1, Sum) insert(S, In(Num(Start[i].Ox, Start[i].Oy)), 1);
	For(i, 1, Tot)
		if(Dat[i].Ox <= Dis || Dat[i].Oy <= Dis) insert(Out(Num(Dat[i].Ox, Dat[i].Oy)), T, INF);
	
	// Sap
	int Ans = 0;
	for(Gap[0] = T; H[S] < T;)
		Ans += Sap(S, INF);
	printf("%d\n", Sum - Ans);
}

int main() {
	#ifndef ONLINE_JUDGE
	SETIO("1066");
	#endif
	Input();
	Solve();
	return 0;
}