Chinaunix首页 | 论坛 | 博客
  • 博客访问: 186158
  • 博文数量: 89
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 828
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:44
文章分类
文章存档

2014年(9)

2013年(80)

我的朋友

分类: C/C++

2013-10-12 16:28:08

题意:这道题的意思就是,给你N个棋子的坐标,这些棋子的走法是象棋中的马的走法。然后再给你N个坐标终点。
问所有的棋子走到其中一个坐标上,不能有重复,最少的步数是多少。
思路:这道题直接搜显然爆,因为他的坐标范围都是int ,所以我们就要考虑怎么处理出两个点之间的最短步数。
我直接把问题扔给队友了,然后他推出了一条公式,太神不能多说。
问题简化成给你两个点(x , y ) ,(x1 , y1),求这两个点之间最少需要多少步。
然后他经过一系列的数学推导,就搞定了。
过程我也不会,等下看代码。
然后接下来每个棋子到每个终点坐标的距离都处理出来了。
那么根据N = 15 。那么很显然状压DP就可以搞定,求出最小值。
但是考虑到每个棋子只有一个位置,那么很显然棋子和终点位置是二分图,那么很显然我们可以用最小权匹配来搞这个问题。
KM的姿势比状压优美许多。
[cpp] view plaincopyprint?
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#define Max 2505  
#define FI first  
#define SE second  
#define ll long long  
#define PI acos(-1.0)  
#define inf 1ll << 60ll  
#define LL(x) ( x << 1 )  
#define bug puts("here")  
#define PII pair  
#define RR(x) ( x << 1 | 1 )  
#define mp(a,b) make_pair(a,b)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
 
using namespace std;  
  
ll f(ll x,ll y) {//推出来的,太神不多说  
    x=abs(x);  
    y=abs(y);  
    if(x>y) {  
        swap(x,y);  
    }  
    if(x==0&&y==1) {  
        return 3;  
    }  
    if(x==2&&y==2) {  
        return 4;  
    }  
    ll z=max((y+1)/2ll,(x+y+2)/3ll);  
    if((z-x-y)&1) {  
        z++;  
    }  
    return z;  
}  
int n ;  
ll x[22] , y[22] ;  
ll xx[22] , yy[22] ;  
ll Map[22][22] ;  
ll lx[22] ,ly[22] ,linkx[22] , linky[22] ;  
bool visx[22] , visy[22] ;  
int find(int now){  
    visx[now] = 1 ;  
    for (int i = 0 ; i < n ; i ++ ){  
        if(!visy[i] && Map[now][i] - lx[now] - ly[i] == 0){  
            visy[i] = 1 ;  
            if(linky[i] == -1 || find(linky[i])){  
                linkx[now] = i ;  
                linky[i] = now ;  
                return 1 ;  
            }  
        }  
    }  
    return 0 ;  
}  
ll KM(){  
    mem(linkx , -1) ;  
    mem(linky , -1) ;  
    mem(ly ,0) ;  
    for (int i = 0 ; i < n ; i ++ ){  
        while(1){  
            mem(visx ,0) ;mem(visy , 0) ;  
            if(find(i))break ;  
            ll d = inf ;  
            for (int j = 0 ; j < n ; j ++ ){  
                if(visx[j])  
                    for (int k = 0 ; k < n ; k ++ ){  
                        if(!visy[k])  
                            d = min(d , Map[j][k] - lx[j] - ly[k]) ;  
                    }  
            }  
            for (int j = 0 ; j < n ; j ++ ){  
                if(visx[j])lx[j] += d ;  
                if(visy[j])ly[j] -= d ;  
            }  
        }  
    }  
    ll ans = 0 ;  
    for (int i = 0 ; i < n ; i ++ ){  
        if(linky[i] != -1 )ans += Map[linky[i]][i] ;  
    }  
    return ans ;  
}  
int main() {  
    int ca = 0 ;  
    while(cin >> n , n ){  
        for (int i = 0 ; i < n ; i ++ )cin >> x[i] >> y[i] ;  
        for (int i = 0 ; i < n ; i ++ )cin >> xx[i] >> yy[i] ;  
        for (int i = 0 ; i < n ; i ++ )lx[i] = inf ;  
        for (int i = 0 ; i < n ; i ++ ){  
            for (int j = 0 ; j < n ; j ++ ){  
                Map[i][j] = f(x[i] - xx[j] , y[i] - yy[j]) ;  
                lx[i] = min(lx[i] , Map[i][j]) ;  
            }  
        }  
        cout << ++ ca << ". " ;  
        cout << KM() << endl;  
    }  
    return 0 ;  
}  
阅读(273) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~