注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

那一日,泪水打湿雪花冰冷的心

曾经的滋味,回忆在一次次的离合中,回眸时,那一刻,如涟漪般在一刹那融化

 
 
 

日志

 
 

hdu 2295  

2011-01-12 22:50:00|  分类: hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
发现日志里没有hdu这一分类,果断加上,这个题有点类似支配集的样子,不过不太一样,题目是说给定A,B两个集合,从B中选尽可能少的来覆盖A集合,于是二分距离+dancing links就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int inf = 0x3f3f3f3f;
const int HGT = 100;
const int WID = 100;
const int SIZE = HGT*WID;
int hash[100],ans;
struct Dancer
{
    int L[SIZE], R[SIZE], D[SIZE], U[SIZE], C[SIZE], ROW[SIZE], S[SIZE];
    int m, id, rowId;
    void init(int m)
    {
        this->m = m;
        for(int i = 0; i <= m; i ++)
        {
            D[i] = U[i] = i;
            S[i] = 0;
            L[i] = i-1;
            R[i] = i+1;
        }
        L[0] = m;
        R[m] = 0;
        id = m + 1;
        rowId = 0;
    }
    void insert(int *xx, int lenx)
    {
        for(int j = 0; j < lenx; j ++, id ++)
        {
            int x = xx[j]+1;
            C[id] = x;
            ROW[id] = rowId;
            S[x] ++;
            D[id] = x;
            U[id] = U[x];
            D[U[x]] = id;
            U[x] = id;
            if( j == 0 )
            {
                L[id] = R[id] = id;
            }
            else
            {
                L[id] = id - 1;
                R[id] = id - j;
                R[id-1] = id;
                L[id-j] = id;
            }
        }
        rowId ++;
    }
    void remove(const int &c)
    {
        for(int i = D[c]; i != c; i = D[i])
        {
            L[R[i]] = L[i];
            R[L[i]] = R[i];
        }
    }
    void resume(const int &c)
    {
        for(int i = U[c]; i != c; i = U[i])
        {
            L[R[i]] = i;
            R[L[i]] = i;
        }
    }
    int h()
    {
        int c,i,j,ret = 0;
        memset(hash,0,sizeof(hash));
        for(c = R[0]; c != 0; c = R[c])
        {
            if(!hash[c])
            {
                ret++;
                hash[c] = true;
                for(i = D[c]; i != c; i = D[i])
                    for(j = R[i]; j != i; j = R[j])
                        hash[C[j]] = true;
            }
        }
        return ret;
    }
    int dfs(int dep)
    {
        if(R[0] == 0)
            return 1;
        int idx,i,j,Min = inf;
        if(dep+h() > ans) 
            return 0;
        for(i = R[0]; i != 0; i = R[i])
        {
            if(S[i] < Min)
            {
                Min = S[i];
                idx = i;
            }
        }
        if(!S[idx])
            return 0;
        for(i = D[idx]; i != idx; i = D[i])
        {
            remove(i);
            for(j = R[i]; j != i; j = R[j])
                remove(j);
            if(dfs(dep+1))
                return 1;
            for(j = L[i]; j != i; j = L[j])
                resume(j);
            resume(i);
        }
        return 0;
    }
} dc;
int n,m,k,a[100];
double x1[100],y1[100],x2[100],y2[100],r,l,mid;
double aa(int i,int j)
{
    return (x1[i]-x2[j])*(x1[i]-x2[j])+(y1[i]-y2[j])*(y1[i]-y2[j]);
}
int check(double radius)
{
    ans=k;
    dc.init(n);
    for(int i=0; i<m; ++i)
    {
        int k=0;
        for(int j=0; j<n; ++j)
            if(aa(j,i)<=radius*radius)
                a[k++]=j;
        dc.insert(a,k);
    }
    return dc.dfs(0);
}
double fabs(double x)
{
    if(x<0)
        return -x;
    return x;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0; i<n; ++i)
            scanf("%lf%lf",&x1[i],&y1[i]);
        for(int i=0; i<m; ++i)
            scanf("%lf%lf",&x2[i],&y2[i]);
        l=0,r=1000;
        while(fabs(r-l)>1e-7)
        {
            mid=(l+r)/2;
            if(check(mid))
                r=mid;
            else l=mid;
        }
        printf("%.6f\n",mid);
    }
    return 0;
}

  评论这张
 
阅读(1228)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018