hdu2413(二分+二分匹配)

时间：2022-06-02 13:01:44

题意：人和外星人星球大战，人总共有H个星球，外星人有A个星球，现在人要用飞船去打外星人的飞船，
要求每个人类星球只能对战一个外星球，且每个星球都开始有己知的飞船数，不论是人或外星人的星球，
并每个星球都有一个生产飞般的生产率p，既每年可以生产p只飞般。
人类飞般去打外星球时要经过一定的时间year才能到达所打的星球。
而外星球也会在这一段时间里生产飞般，人类星球要想赢一个外星人的星球必须飞船数不小于外星球的飞船数。
问人类星要想打赢所有的外星人星球最少需要多少年，如果不能打完所有外星球就输出IMPOSSIBLE.

做法是二分+二分匹配，二分时间

首先如果H<A那肯定不行

我们二分时间，建图就是如果人类的x星球能在规定时间内击败敌人的y星球，那就让x->y连边

然后二分匹配，如果每个外星球都匹配到了人类星球，就return true,不然return false;

#include<string>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<vector>

#include<queue>

using namespace std;

typedef long long ll;

const int MAX=<<;

int n,m;

typedef struct node

{

    ll rate,yuan;

}node ;

node arr[],axx[];

ll times[][];

bool used[];

int belong[];

bool map[][];

bool checks(int a,int b,ll lim)

{

    if(times[a][b]>lim)return false ;

    ll nums=axx[b].yuan+axx[b].rate*times[a][b];

    if(arr[a].rate<=axx[b].rate)return arr[a].yuan>=nums;

    else

    {

        if(arr[a].yuan>=nums)return true;

        ll cost=(nums-arr[a].yuan+arr[a].rate-axx[b].rate-)/(arr[a].rate-axx[b].rate)+times[a][b];

        return cost<=lim;

    }

}

bool dfs(int now)

{

    int i,j;

    for(i=;i<m;i++)

    {

        if(!used[i]&&map[now][i])

        {

            used[i]=;

            if(belong[i]==-||dfs(belong[i]))

            {

                belong[i]=now;

                return true;

            }

        }

    }

    return false;

}

bool check(ll mid)

{

    memset(map,,sizeof(map));

    memset(belong,-,sizeof(belong));

    int i,j;

    for(i=;i<n;i++)for(j=;j<m;j++)map[i][j]=checks(i,j,mid);

    int num=;

    for(i=;i<n;i++)

    {

        memset(used,,sizeof(used));

        if(dfs(i))num++;

    }

    return num==m;

}

int main()

{

    int i,j;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==&&m==)return ;

        for(i=;i<n;i++)scanf("%lld%lld",&arr[i].yuan,&arr[i].rate);

        for(i=;i<m;i++)scanf("%lld%lld",&axx[i].yuan,&axx[i].rate);

        for(i=;i<n;i++)for(j=;j<m;j++)scanf("%lld",&times[i][j]);

        ll l=,r=;

        if(n<m||!check(r))

        {

            printf("IMPOSSIBLE\n");

            continue;

        }

        while(r-l>)

        {

            ll mid=(l+r)/;

            if(check(mid))r=mid;

            else l=mid;

        }

        ll ans=l;

        if(!check(ans))ans++;

        printf("%lld\n",ans);

    }

}

相关文章