首页 > 搜索 > DFS搜索 > hdu 2413 Against Mammoths-分治-[解题报告]C++
2014
01-26

hdu 2413 Against Mammoths-分治-[解题报告]C++

Against Mammoths

问题描述 :

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 nships 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 non-negative integers n1 m1 n2 m2 … nH mH. The number ni is the initial number of Saber Tooth spaceships in the ith human planet and mi 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.

输出:

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 non-negative integers n1 m1 n2 m2 … nH mH. The number ni is the initial number of Saber Tooth spaceships in the ith human planet and mi 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.

样例输入:

2 1
2 3 0 3
2 2
2
2
0 0

样例输出:

6

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2413

思路:由于要求最少的时间,可以考虑二分,然后就是满足在limit时间下,如果地球战舰数目比外星战舰数目多,就连边,然后求最大匹配即可,判断匹配数目是否等于外星球数目,如果相等,说明可以占领,继续二分。

#include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<algorithm>
 #include<vector>
 using namespace std;
 #define MAXN 333
 #define inf 1<<20
 typedef long long ll;
 vector<int>map[MAXN];
 int mark[MAXN];
 int ly[MAXN];
 int hp[MAXN],hq[MAXN];
 int ap[MAXN],aq[MAXN];
 int tt[MAXN][MAXN];
 int n,m;
 
 int dfs(int u)
 {
     for(int i=0;i<map[u].size();i++){
         int v=map[u][i];
         if(!mark[v]){
             mark[v]=true;
             if(ly[v]==-1||dfs(ly[v])){
                 ly[v]=u;
                 return 1;
             }
         }
     }
     return 0;
 }
 
 bool MaxMatch(int limit)
 {
     for(int i=1;i<=n;i++)map[i].clear();
     for(int i=1;i<=n;i++){
         for(int j=1;j<=m;j++){
             ll t1=1ll+hp[i]+(ll)(limit-tt[i][j])*hq[i];
             ll t2=1ll+ap[j]+(ll)limit*aq[j];
             if(t1>=t2)map[i].push_back(j);
         }
     }
     int res=0;
     memset(ly,-1,sizeof(ly));
     for(int i=1;i<=n;i++){
         memset(mark,false,sizeof(mark));
         res+=dfs(i);
     }
     if(res==m)return true;
     return false;
 }
 
 int main()
 {
   //  freopen("1.txt","r",stdin);
     while(scanf("%d%d",&n,&m),(n+m)){
         for(int i=1;i<=n;i++)
             scanf("%d%d",&hp[i],&hq[i]);
         for(int i=1;i<=m;i++)
             scanf("%d%d",&ap[i],&aq[i]);
         for(int i=1;i<=n;i++)
             for(int j=1;j<=m;j++)
                 scanf("%d",&tt[i][j]);
         int low=0,high=inf,mid,ans=inf;
         while(low<=high){
             mid=(low+high)>>1;
             if(MaxMatch(mid)){
                 ans=mid;
                 high=mid-1;
             }else
                 low=mid+1;
         }
         if(ans<inf){
             printf("%d\n",ans);
         }else
             puts("IMPOSSIBLE");
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/wally/p/3143463.html


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }