首页 > 搜索 > DFS搜索 > HDU 4735-Little Wish~ lyrical step~-最短路径-[解题报告]HOJ
2015
09-17

HDU 4735-Little Wish~ lyrical step~-最短路径-[解题报告]HOJ

Little Wish~ lyrical step~

问题描述 :

N children are living in a tree with exactly N nodes, on each node there lies either a boy or a girl.
A girl is said to be protected, if the distance between the girl and her nearest boy is no more than D.
You want to do something good, so that each girl on the tree will be protected. On each step, you can choose two nodes, and swap the children living on them.
What is the minimum number of steps you have to take to fulfill your wish?

输入:

The first line has a number T (T <= 150) , indicating the number of test cases.
In a case, the first line contain two number n (1 <= n <= 50), D (1 <= D <= 10000000), Which means the number of the node and the distance between the girls and boys.
The next lines contains n number. The ith number means the ith node contains a girl or a boy. (0 means girl 1 means boy), The follow n – 1 lines contains a, b, w, means a edge connect ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).

输出:

The first line has a number T (T <= 150) , indicating the number of test cases.
In a case, the first line contain two number n (1 <= n <= 50), D (1 <= D <= 10000000), Which means the number of the node and the distance between the girls and boys.
The next lines contains n number. The ith number means the ith node contains a girl or a boy. (0 means girl 1 means boy), The follow n – 1 lines contains a, b, w, means a edge connect ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).

样例输入:

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

样例输出:

Case #1: 1

题意:有一个棵树,上面有n个结点。每个节点有住着一个孩子,男生或者女生,如果女生在一个D的范围内有男生则说明被保护,问你最少交换几个孩子的位置,使得所有女生都受保护,如果无法达成,输出-1。

思路:这道题目可以转化为重复覆盖的模型,男生结点为1,女生结点为0,则行为这个结点如果为1的话,可以那几个结点的人,包括自己,列为n个人,则可以使用DLX来解决。因为只有50个点,所以树上最短距可以用floyd预处理

但是这里要注意几点:

1)求得并不是最小的重复覆盖,而是在一定数目条件下,交换人数最少的次数,因此,要搜遍整棵树(也就是搜完所有可能),而不能使用迭代A*的方法。

2)如果完全搜整棵树会TLE,因此要加入一些剪枝,剪枝为,如果当前需要交换的节点数大于限制,则直接return.

代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define inf 0x3f3f3f
using namespace std;
const int maxn=60;
const int maxr=maxn*maxn+maxn;
int n,D;
int child[maxn];
int boys;
bool flag;
int map[maxn][maxn];
void init_m()//初始化图
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            if(i==j)
            {
                map[i][j]=0;
            }
            else
            {
                map[i][j]=inf;
            }
        }
}
void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(map[i][k]+map[k][j]<map[i][j])
                {
                    map[i][j]=map[i][k]+map[k][j];
                }
            }
}
struct node
{
    int l,r;
    int u,d;
    int s,c;
};
node dlx[maxr];
int h[maxn];
int limit;
int Q[maxn];
int X[maxr];
int hash[maxn];
int head,size;
void init(int r,int c)
{
    head=0;
    for(int i=0; i<=c; i++)
    {
        dlx[i].s=0;
        dlx[i].u=dlx[i].d=i;
        dlx[i].r=i+1;
        dlx[i+1].l=i;
    }
    size=c;
    dlx[c].r=0;
    while(r)
    {
        h[r--]=-1;
    }
}
void link(int r,int c)
{
    int tmp=++size;
    dlx[c].s++;
    dlx[tmp].c=c;
    X[tmp]=r;
    dlx[tmp].d=dlx[c].d;
    dlx[tmp].u=c;
    dlx[dlx[c].d].u=tmp;
    dlx[c].d=tmp;
    if(h[r]<0)
    {
        h[r]=dlx[tmp].l=dlx[tmp].r=tmp;
    }
    else
    {
        dlx[tmp].r=dlx[h[r]].r;
        dlx[tmp].l=h[r];
        dlx[dlx[h[r]].r].l=tmp;
        dlx[h[r]].r=tmp;
    }
}
void remove(int x)
{
    for(int i=dlx[x].d; i!=x; i=dlx[i].d)
    {
        dlx[dlx[i].r].l=dlx[i].l;
        dlx[dlx[i].l].r=dlx[i].r;
        dlx[dlx[i].c].s--;
    }
}
void resume(int x)
{
    for(int i=dlx[x].u; i!=x; i=dlx[i].u)
    {
        dlx[dlx[i].r].l=i;
        dlx[dlx[i].l].r=i;
        dlx[dlx[i].c].s++;
    }
}
int hh()
{
    int ret=0;
    memset(hash,0,sizeof(hash));
    for(int i=dlx[head].r; i!=head; i=dlx[i].r)
    {
        if(hash[i]==false)
        {
            hash[i]=true;
            ret++;
            for(int j=dlx[i].d; j!=i; j=dlx[j].d)
            for(int k=dlx[j].r; k!=j; k=dlx[k].r)
            {
                hash[dlx[k].c]=true;
            }
        }
    }
    return ret;
}
void dlx_dfs(int k)
{
    if(k+hh()>boys)//最大的限制为男生总数
    {
        return;
    }
    int ssd=0;
    for(int i=0;i<k;i++)
    {
        ssd+=child[Q[i]];
    }
    if(k-ssd>=limit) return;//剪枝判断
    if(dlx[head].r==head)
    {
        flag=true;
        limit=k-ssd;
        return;
    }
    int minn=n+2;
    int tt;
    for(int i=dlx[head].r; i!=head; i=dlx[i].r)
    {
        if(minn>dlx[i].s)
        {
            minn=dlx[i].s;
            tt=i;
        }
    }
    for(int i=dlx[tt].d; i!=tt; i=dlx[i].d)
    {
        Q[k]=X[i];
        remove(i);
        for(int j=dlx[i].r; j!=i; j=dlx[j].r)
        {
            remove(j);
        }
        dlx_dfs(k+1);
        for(int j=dlx[i].l; j!=i; j=dlx[j].l)
        {
            resume(j);
        }
        resume(i);
    }
    return;
}
int main()
{
   // freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    int cas=1;
    while(t--)
    {
        printf("Case #%d: ",cas++);
        scanf("%d%d",&n,&D);
        boys=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&child[i]);
            if(child[i]==1)
            {
                boys++;
            }
        }
        init_m();
        int a,b,c;
        for(int i=0;i<n-1;i++)//正反建图
        {
            scanf("%d%d%d",&a,&b,&c);
            map[a][b]=c;
            map[b][a]=c;
        }
        floyd();
        init(n,n);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                if(map[i][j]<=D)
                {
                    link(i,j);
                }
            }
            flag=false;
            limit=inf;
        dlx_dfs(0);
        if(!flag)
        {
            printf("-1\n");
        }
        else
        {
            printf("%d\n",limit);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/huolongshenghu/article/details/13298083