UVALIVE 4970 最小权匹配-ihasudgq-ChinaUnix博客

ihasudgq的ChinaUnix博客

首页　| 　博文目录　| 　关于我

ihasudgq

博客访问： 185417
博文数量： 89
博客积分： 0
博客等级：民兵
技术积分： 828
用户组：普通用户
注册时间： 2013-10-08 10:44

文章分类

全部博文（89）

灵域www.uy0.net（79）
未分配的博文（10）

文章存档

2014年（9）

2013年（80）

我的朋友

相关博文

UVALIVE 4970 最小权匹配

分类： 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 ;
}

阅读(269) | 评论(0) | 转发(0) |

上一篇：发布文章时多少天、多少小时、多少分前发布功能

下一篇：将动态库添加到VC程序中

给主人留下些什么吧！~~

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6