算法思路

1. 二分图匹配模型：

   • 将猎人视为左侧节点，动物视为右侧节点
   • 边的存在条件：猎人在特定时间内能够击败动物
   • 使用匈牙利算法求最大匹配，判断是否能完全匹配

2. 时间计算：

   • 计算猎人i击败动物j所需的总时间g[i][j]
   • 考虑猎人移动时间、攻击过程中的生命值变化及恢复

3. 二分查找：

   • 对总时间进行二分查找，确定最小的可行时间
   • 每次检查当前时间是否满足所有动物被击败的条件

代码实现解析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define Maxn 261
#define INF 1800000010

int link[Maxn],vis[Maxn],d[Maxn][Maxn],g[Maxn][Maxn];

int fi[Maxn],ne[Maxn*Maxn],to[Maxn*Maxn],te;

int ia[Maxn],pa[Maxn],ih[Maxn],ph[Maxn];
int H,A;

// 添加边到邻接表
void addedge(int u,int v){
	te++;ne[te]=fi[u];fi[u]=te;to[te]=v;
}

// 匈牙利算法核心：寻找增广路径
bool find(int i){
	int j,e;
	for(e=fi[i];~e;e=ne[e]){
		j=to[e];
		if (!vis[j]){
			vis[j]=1;
			if (link[j]==0 || find(link[j])){
				link[j]=i;
				return true;
			}
		}
	}
	return false;
}

// 计算猎人i击败动物j所需的总时间
int cal(int i,int j){
	if (ih[i]==0&&ph[i]==0) return INF;
	int tmp=ia[j]-ih[i]+d[i][j]*pa[j];
	// 特殊情况处理：初始生命值为0且tmp为0
	if (ih[i]==0&&tmp==0) return 1+g[i][j];
	if (tmp<=0) return g[i][j];
	int ret=0;
	int tp=ph[i]-pa[j];
	if (tp<=0) return INF;  // 恢复速度不足以抵消伤害
	if (tmp%tp){ret++;}  // 处理余数
	ret+=tmp/tp;  // 计算攻击次数
	ret+=d[i][j];  // 加上移动时间
	return ret;
}

// 检查在时间m内是否能击败所有动物
int check(int m){
	int i,j;
	memset(fi,-1,sizeof(fi));
	te=0;
	// 构建二分图：如果猎人i能在m时间内击败动物j，则添加边
	for(i=1;i<=H;++i){
		for(j=1;j<=A;++j){
			if (g[i][j]<=m) {
				addedge(i,j);
			}
		}
	}
	
	// 匈牙利算法求最大匹配
	memset(link,0,sizeof(link));
	int ans=0;
	for(i=1;i<=H;i++){
		memset(vis,0,sizeof(vis));
		if (find(i)) ans++;
	}
	if (ans==A) return 1;  // 所有动物都能被击败
	else return 0;
}


int main(){
	int i,b,j;
	while(1){
		scanf("%d%d",&H,&A);
		if (H==0&&A==0) break;
		// 输入猎人信息
		for(i=1;i<=H;++i){
			scanf("%d%d",&ih[i],&ph[i]);
		}
		// 输入动物信息
		for(i=1;i<=A;++i){
			scanf("%d%d",&ia[i],&pa[i]);
		}
		
		// 输入移动时间矩阵
		for(i=1;i<=H;i++)
			for(j=1;j<=A;++j){
				scanf("%d",&b);
				d[i][j]=b;
			}
		
		// 计算每个猎人击败每个动物所需的时间
		for(i=1;i<=H;++i){
			for(j=1;j<=A;++j){
				g[i][j]=cal(i,j);
			}
		}
		
		// 二分查找最小可行时间
		int l=0,r=1700011000,m,ans=r+10;
		while(l<=r){
			m=((long long)l+r)/2;
			if (check(m)) {
				if (ans>m) ans=m;
				r=m-1;
			}
			else l=m+1;
		}
		if (ans>1700011000) printf("IMPOSSIBLE\n");
		else printf("%d\n",ans);
	}
	return 0;
}