Back to year 3024, humans finally developed a new technology that
enables them to conquer the alien races. The new technology made it
possible to produce huge spaceships known as Saber Tooth spaceships as
powerful as the aliens' defending mammoths. At that time, humans ruled
several planets while some others were under control of the aliens.
Using Saber Tooth ships, humans finally defeated aliens and this became
the first Planet War in history. Our goal is to run a simulation of the
ancient war to verify some historical hypotheses.
Producing each spaceship takes an amount of time which is constant for
each planet but may vary among different planets. We call the number of
spaceships each planet can produce in a year, the
production rate
of that planet. Note that each planet has a
number of spaceships in it initially (before the simulation starts). The
planets start producing ships when the simulation starts, so if a
planet has n
ships initially, and has the production rate p
, it will have n + p
ships at the beginning of year 1, and
n + i×p
ships at the beginning of year i
(years are started from zero).
Bradley Bennett, the commander in chief of the human armies, decided a
strategy for the war. For each alien planet A, he chooses a
corresponding human planet P, and produces spaceships in P until a
certain moment at which he sends all spaceships in P to invade the
planet A. No alien planet is invaded by two human planets and no human
planet sends its spaceships to two different alien planets.
The defense power of the alien planets comes from their powerful
mammoths. Each alien planet contains a number of mammoths initially and
produces a number of mammoths each year (called the production rate of
the planet). When a fight between spaceships and mammoths takes place,
the side having the greater number of troops is the winner. If the
spaceships win, the alien planet is defeated. In case the number of
mammoths and spaceships are equal, the spaceships win.
The difficulty with planning this strategy is that it takes some time
for the spaceships to reach the alien planets, and during this time, the
aliens produce mammoths. The time required for spaceships to travel
from each human planet to each alien planet is known. The ships can
leave their planets only at the beginning of years (right after the
ships are produced) and reach the alien planets at the beginning of
years too (right after the mammoths are produced).
As an example, consider a human planet with two initial spaceships and
production rate three invading an alien planet with two initial mammoths
and production rate two. The time required to travel between the two
planets is two years and the ships are ordered to leave at year one. In
this case, five ships leave the human planet. When they reach the alien
planet, they confront eight mammoths and will be defeated during the
fight.
Bennett decided to prepare a plan that destroys every alien planet in
the shortest possible time. Your task is to write a program to generate
such a plan. The output is the shortest possible time (in years) in
which every alien planet is defeated.
There are multiple test cases in the input. The first line of each test case contains two numbers H
and A
which are the number of planets under the
control of humans and aliens respectively (both between 1 and 250). The
second line of the test case contains H
pairs of non-negative integers
n1 m1 n2 m2...nH mH
. The number ni
is the initial number of Saber Tooth spaceships in the i
-th human planet and mi
is the production rate of that planet. The third line contains A
pairs of 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 j
-th number on the i
-th line shows how many years it takes a spaceship to travel from the i
-th human planet to the j
-th 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.
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'.
2 1
2 3 0 3
2 2
2
2
0 0
6
題目描述：人類有許多星球，外星人也有他們的星球，兩大勢力開打。
人類的每一個星球只能攻擊外星人的一個星球。
但因為星球間與星球間有段距離，飛行也是需要時間的。
攻擊方式為建造戰艦，每個星球都有各自的初始戰艦個數以及每年生產戰艦的數量。
當戰艦個數大於或等於時，則可以勝過對方。
由於人類是主動的一方，必須多耗時間進行移動，移動的過程中，外星人仍然在建造戰艦。
求最近的一年，可以使得外星人全滅。
題目解法：
二分年份，對於每次二分建造新的圖，使用匈牙利算法進行二分匹配。
maxflow 寫起來效率有點差。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
int g[505][505], gt[505];
int mx[505], my[505], used[505];
int dfs(int now) {
int i, x;
for(i = 0; i < gt[now]; i++) {
x = g[now][i];
if(!used[x]) {
used[x] = 1;
if(my[x] == -1 || dfs(my[x])) {
mx[now] = x, my[x] = now;
return 1;
}
}
}
return 0;
}
int H, A, hn[300], hm[300], an[300], am[300];
int dist[300][300];
int check(int time) {
int i, j;
memset(mx, -1, sizeof(mx));
memset(my, -1, sizeof(my));
memset(gt, 0, sizeof(gt));
for(i = 0; i < H; i++) {
for(j = 0; j < A; j++) {
if(hn[i]+(long long)(time-dist[i][j])*hm[i] >=
an[j]+(long long)time*am[j])
g[i][gt[i]++] = j;
}
}
int matched = 0;
for(i = 0; i < H; i++) {
if(mx[i] == -1) {
memset(used, 0, sizeof(used));
if(dfs(i))
matched++;
if(matched >= A) return 1;
}
}
return matched >= A;
}
void binary_sol() {// binary search time.
int l = 0, r = 0xfffffff, mid;
int ret = 0xfffffff;
if(check(r) == 0) {
puts("IMPOSSIBLE");
return;
}
while(l <= r) {
mid = (l+r)/2;
if(check(mid))
r = mid-1, ret = mid;
else
l = mid+1;
}
printf("%d\n", ret);
}
int main() {
int i, j;
while(scanf("%d %d", &H, &A) == 2 && H+A) {
for(i = 0; i < H; i++)
scanf("%d %d", &hn[i], &hm[i]);
for(i = 0; i < A; i++)
scanf("%d %d", &an[i], &am[i]);
for(i = 0; i < H; i++)
for(j = 0; j < A; j++)
scanf("%d", &dist[i][j]);
binary_sol();
}
return 0;
}
文章定位：
