1 m1 n2 m2 … nH mH. The number n
i is the initial number of Saber Tooth spaceships in the ith human planet and m
i is the production rate of that planet. The third line contains A non-negative integers which specify the initial number of mammoths and the production rate of the alien planets in the same format as the second line. After the third line, there are H lines each containing A positive integers. The jth number on the ith line shows how many years it takes a spaceship to travel from the ith human planet to the jth alien planet. The last line of the input contains two zero numbers. Every number in the input except H and A is between 0 and 40000.
Output The output for each test case contains a single integer which is the minimum time in which all alien planets can be defeated. If it is impossible to destroy all alien planets, the output should be IMPOSSIBLE.
Sample Input
2 1
2 3 0 3
2 2
2
2
0 0
Sample Output
6
Source 2006 Asia Regional Tehran 题意：人和外星人星球大战，人总共有H个星球，外星人有A个星球，现在人要用飞船去打外星人的飞船，要求每个人类星球只能对战一个外星球，且每个星球都开始有己知的飞船数，不论是人或外星人的星球，并每个星球都有一个生产飞般的生产率p，既每年可以生产p只飞般。人类飞般去打外星球时要经过一定的时间year才能到达所打的星球。而外星球也会在这一段时间里生产飞般，人类星球要想赢一个外星人的星球必须飞船数不小于外星球的飞船数。问人类星要想打赢所有的外星人星球最少需要多少年，如果不能打完所有外星球就输出IMPOSSIBLE.
解题：要赢首先得满足一定的条件：1. H>=A. 2.每个外星球必需有人类星球去打。3.一个人类星球只能对战一个外星球且这人类星球的飞船数在到达外个外星球时必须大于外个外星球的飞船数。每个外星球都在一对一的战争是败。 现在我们可以根据是一对一的关系可以想到二分匹配，那么怎么建边呢，通过预处理，把每个人类星球能用有限的年内打赢每个外星球可以建立起一个边，并记下每条边所用的时间。我们可以再分析一下，因为我们所求的是用最少年数打完所有外星球，那么可以先对所有的边按年数从小到大排序，再以外星球作为去匹配人类星球建边（好处：当一个外星球找不到一条增广路去配人类星球，那么我们发现外星球是不可能被打完），当外星球全部可以去匹配人类星球时，再从最大的一个接一个的边去除掉，如果去掉的不是匹配边则不用找增广路，再接着去掉一条大边，如果去掉的是匹配边，那么从这条边相关的外星球去找一条增广路，如果找不到则说明去掉的这条边就是我们要求的最少年数打完所有外星球。就可以直接得出答案。 PS：根据上面的250MS AC。
#include
#include
#include
#include
#include
using namespace std; typedef struct nn { __int64 s,p; }planets; typedef struct nnn { __int64 hum,alien,fightyear; }Fight; __int64 HN,AN,fn; Fight fight[260*260]; planets humans[260],aliens[260]; int set_fightyear()//计算每个人类星球所要的最少年数 { __int64 y,k,p,i,j,alie[260]={0},ak=0; fn=0; for( i=1;i<=HN;i++) scanf("%I64d%I64d",&humans[i].s,&humans[i].p); for(i=1;i<=AN;i++) scanf("%I64d%I64d",&aliens[i].s,&aliens[i].p); for( i=1;i<=HN;i++) for( j=1;j<=AN;j++) { scanf("%I64d",&y); if(HN
0) { if(k%p==0)fight[++fn].fightyear=k/p+y; else fight[++fn].fightyear=k/p+1+y; if(alie[fight[fn].alien]==0)ak++,alie[fight[fn].alien]=1; } } } if(ak
0;i--) { alie=fight[i].alien; mk[alie]--;//去掉大边 if(match[map[alie][mk[alie]+1]]!=alie)continue;//不是匹配边 match[map[alie][mk[alie]+1]]=0; for( j=1;j<=HN;j++) vist[j]=0; flag=find(alie); if(flag==0)return fight[i].fightyear;//找不到增广路这条边就是答案 } } int main() { __int64 flag; while(scanf("%I64d%I64d",&HN,&AN)>0&&(HN||AN)) { flag=-1; int f=set_fightyear(); if(HN>=AN&&f)flag=answear(); if(flag==-1)printf("IMPOSSIBLE\n"); else printf("%I64d\n",flag); } }