#include <stdio.h>
#include <string.h>
#define MAX 301
int n,m;
int g[MAX][MAX],cx[MAX],cy[MAX],px[MAX],py[MAX];

int path(int x)
{
	int y;
	for (y=0; y<m; y++)
		if (!py[y] && g[x][y]!=0) 
		{
			py[y]=1;
		  	if (cy[y]==-1 || path(cy[y])) {
				cy[y]=x;cx[x]=y;
				return 1;
			}
		}
	return 0;
}

int match(){
	int x,count=0;
	memset(cx,-1,sizeof(cx));
	memset(cy,-1,sizeof(cy));
	for (x=0; x<n; x++)
		if (cx[x]==-1) {
			memset(px,0,sizeof(px));
			memset(py,0,sizeof(py));
			if (path(x)) count++;
		  }
	return count;
}

int dis[MAX][MAX];
int rateE[MAX];
int preE[MAX];
int rateO[MAX];
int preO[MAX];
int flag;

int main(int argc, char *argv[])
{
	int i,j;
	int l,r,mid;
	__int64 cntE,cntO;
	while(scanf("%d%d",&n,&m),m+n)
	{
		flag = 0;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&preE[i],&rateE[i]);
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&preO[i],&rateO[i]);
		}
		for(i=0;i<n;i++)
		{
			for(j=0;j<m;j++)
			{
				scanf("%d",&dis[i][j]);
			}
		}
		l = 0;
		r = 1000000;
		while(l<r)
		{
			mid = (l+r)/2;
			memset(g,0,sizeof(g));
			for(i=0;i<n;i++)
			{
				for(j=0;j<m;j++)
				{
					if(mid < dis[i][j]) continue;
					cntE = (__int64)preE[i] + (__int64)rateE[i]*(mid-dis[i][j]);
					cntO = (__int64)preO[i] + (__int64)rateO[j]*mid;
					if(cntE>=cntO)
					{
						g[i][j] = 1;
					}
				}
			}
			if(match()==m)
			{
				flag = 1;
				r = mid;
			}
			else
			{
				l = mid + 1;
			}
		}
		if(flag) printf("%d\n",r);
		else printf("IMPOSSIBLE\n");
	}
	return 0;
}

• Re:这题是匹配么，怎么不对啊 (10) tt1234 2007-08-17 19:48:15
  • 哪错了,指点一下 (10) ares_theone 2007-09-06 20:32:39