首页 > ACM题库 > HDU-杭电 > HDU 4354-Missile[解题报告]HOJ
2015
05-23

HDU 4354-Missile[解题报告]HOJ

Missile

问题描述 :

Long long ago,there is a strange area where all the C cities are located in a straight line.To make things easy,lets regard the line as X axis.
Even more strangely,cities belonging to the same country are not necessarily adjacent to each other.
But people of these countries are still living happily with their friends.
However,their enemies are preparing for a disastrous attack.Recently they have invented a new weapon called missile,which can destroy any city if they have enough power.If they want to destroy a set of cities,the power required is max{xi}-min{xj},where i and j are all from the city set they want to destroy.Now the enenies are wondering the minimum power needed to destroy some cities which are from at least K different countries.This is an easy task.The problem is that some countries are strangely protected.That means ,if country A and country B has a special relationship,you can destroy at most one country’s cities.A good news is that the relationships will not form circles.But the enemies regard it as helpless,so they order you to write a programme to calculate the specific power.In this task,you can assume that once the missile is launched with certain power,it will destroy the cities from as more countries as possible.

输入:

There is an integer T (1<=T<=60) indicating the cases you have to solve.Then the following T cases,each one begins with four integers C,N,K,M.C is the number of cities.N is the number of different countries.K is the number of distinct countries the enemies want to destroy.M is the number of the strange relationships. Then comes the next C lines,each line has two integers.The first one is the city’s position x(-109<=x<=109),and the second one is the country Y it belongs to(1<=Y<=N).
No two cities are located in the same position.In last M lines, each line contains two integers A and B (1 <= A, B <= N) which means country A and country B has a special relationship.(1<=C<=5000,1<=N<=2000,1<=K<=N,0<=M<=1000)

输出:

There is an integer T (1<=T<=60) indicating the cases you have to solve.Then the following T cases,each one begins with four integers C,N,K,M.C is the number of cities.N is the number of different countries.K is the number of distinct countries the enemies want to destroy.M is the number of the strange relationships. Then comes the next C lines,each line has two integers.The first one is the city’s position x(-109<=x<=109),and the second one is the country Y it belongs to(1<=Y<=N).
No two cities are located in the same position.In last M lines, each line contains two integers A and B (1 <= A, B <= N) which means country A and country B has a special relationship.(1<=C<=5000,1<=N<=2000,1<=K<=N,0<=M<=1000)

样例输入:

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

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

样例输出:

Case #1: 3
Case #2: -1
Hint
Not all the cases are big ones.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define NMAX 2002
#define CMAX 5002
#define MMAX 1002
int C,N,K,M;
int to[MMAX<<1],next[MMAX<<1],head[NMAX],edge;
int dp[NMAX][2],hav[NMAX];
bool vis[NMAX];
struct node
{
    int x,belong;
} city[CMAX];
bool cmp(node a,node b)
{
    return a.x<b.x;
}
void init()
{
    memset(hav,0,sizeof(hav));
    memset(head,-1,sizeof(head));
    edge=0;
}
inline void add(int u,int v)
{
    to[edge]=v,next[edge]=head[u],head[u]=edge++;
    to[edge]=u,next[edge]=head[v],head[v]=edge++;
}
void dfs(int now)
{
    vis[now]=true;
    dp[now][0]=0;
    dp[now][1]=1;
    for(int i=head[now],v; ~i; i=next[i])
    {
        v=to[i];
        if(!vis[v]&&hav[v])
        {
            dfs(v);
            dp[now][0]+=max(dp[v][0],dp[v][1]);
            dp[now][1]+=dp[v][0];
        }
    }
}
bool ok()
{
    memset(vis,0,sizeof(vis));
    int res=0;
    for(int i=1; i<=N; i++)
    {
        if(hav[i]&&!vis[i])
        {
            dfs(i);
            res+=max(dp[i][0],dp[i][1]);
        }
    }
    return res>=K;
}
int main()
{
    int T,u,v;
    scanf("%d",&T);
    for(int ca=1; ca<=T; ca++)
    {
        init();
        scanf("%d%d%d%d",&C,&N,&K,&M);
        for(int i=0; i<C; i++)
            scanf("%d%d",&city[i].x,&city[i].belong);
        sort(city,city+C,cmp);
        for(int i=0; i<M; i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        int l,r,ans=-1;
        l=r=0;
        int cNum=1;
        hav[city[0].belong]=1;
        while(l<C&&r<C)
        {
            bool flag=false;
            if(cNum>=K)
            {
                if(ok())
                {
                    flag=true;
                    if(ans==-1)
                        ans=city[r].x-city[l].x;
                    else
                        ans=min(ans,city[r].x-city[l].x);
                }
            }
            if(flag)
            {
                --hav[city[l].belong];
                if(hav[city[l].belong]==0)
                    --cNum;
                ++l;
            }
            else
            {
                ++r;
                if(hav[city[r].belong]==0)
                    ++cNum;
                ++hav[city[r].belong];
            }
        }
        printf("Case #%d: %d\n",ca,ans);
    }
    return 0;
}