2501.cpp

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

/* This Code is Submitted by wywcgs for Problem 2501 on 2007-06-05 at 10:12:58 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 256;

bool atk[N][N];
int pth[N][N], n, m;
long long g[N][N];
int match[N];
bool check[N];

int maxmatch(long long);
bool dfs(int, long long);

int main()
{
	int as[N], av[N], bs[N], bv[N];
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(int i = 0; i < n; i++) scanf("%d %d", &as[i], &av[i]);
		for(int i = 0; i < m; i++) scanf("%d %d", &bs[i], &bv[i]);
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
			scanf("%d", &pth[i][j]);
		if(n < m) { printf("IMPOSSIBLE\n"); continue; }
		long long lo = 1LL << 60, hi = -1;
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) {
			atk[i][j] = false;
			int c1 = av[i]-bv[j];
			long long day = -1, b1 = (long long)bv[j]*pth[i][j]+bs[j]-as[i];
			if(c1 <= 0 && b1 <= 0) day = 0;
			if(c1 > 0) day = max(0LL, (b1+c1-1)/c1);
			if(day < 0) continue;
			g[i][j] = day+pth[i][j]; atk[i][j] = true;
			hi >?= g[i][j]; lo <?= g[i][j]-1;
		}
		if(hi < 0) { printf("IMPOSSIBLE\n"); continue; }
		while(hi-lo != 1) {
			long long mid = (lo+hi)/2;
			if(maxmatch(mid) == m) hi = mid;
			else lo = mid;
		}
		if(maxmatch(hi) != m) printf("IMPOSSIBLE\n");
		else printf("%lld\n", hi);
	}
	return 0;
}

int maxmatch(long long mid)
{
	int mth = 0;
	memset(match, -1, sizeof(match));
	for(int i = 0; i < n; i++) {
		memset(check, false, sizeof(check));
		if(dfs(i, mid)) mth++;
	}
	return mth;
}
bool dfs(int v, long long k)
{
	for(int i = 0; i < m; i++) {
		if(!atk[v][i] || g[v][i] > k || check[i]) continue;
		check[i] = true;
		int t = match[i];
		match[i] = v;
		if(t == -1 || dfs(t, k)) return true;
		match[i] = t;
	}
	return false;
}