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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 2282 Chocolate  

2013-09-04 14:43:47|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=2282
有n个盒子摆成的环,每个盒子里有一定数量的巧克力,巧克力总数小于n,问最少移几步,使得每个盒子里巧克力数小于等于1,从第i个盒子移到第j个盒子的步数为abs(i-j)。
把空盒子看成一个集合X,把盒子里巧克力数大于1的盒子看成一个集合Y,则集合Y里每个盒子里的每颗巧克力到集合X都有边,权值为步数。这样问题化简为求完备匹配的最大权匹配,利用KM算法解决。

/*
* pro.cpp
*
* Created on: 2013-09-04
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
//#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=510;
const int M=150010;
const int MOD=20100501;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

int w[N][N];
int lx[N], ly[N];
int linky[N];
int visx[N], visy[N];
int lack;
int n;

bool find(int x, int n, int m)
{
visx[x] = true;
for (int y = 0; y < m; y++)
{
if (visy[y])
continue;
int t = lx[x] + ly[y] - w[x][y];
if (t > 0)
{
lack = min(lack, t);
continue;
}
visy[y] = true;
if (linky[y] == -1 || find(linky[y], n, m))
{
linky[y] = x;
return true;
}
}
return false;
}

int KM(int n, int m)
{
memset(linky, -1, sizeof(linky));
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (w[i][j] > lx[i])
lx[i] = w[i][j]; //初始化顶标
for (int x = 0; x < n; x++)
{
while (true)
{
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
lack = INF;
if (find(x, n, m))
break;
for (int i = 0; i < n; i++)
if (visx[i])
lx[i] -= lack;
for (int i = 0; i < m; i++)
if (visy[i])
ly[i] += lack;
}
}
int res = 0;
for (int i = 0; i < m; i++)
{
// if (w[linky[i]][i] <= -INF)
// return false;
if(linky[i] != -1)
res += w[linky[i]][i];
}
return res;
}


void solve()
{
int x[N],y[N];
int a,n1=0,m1=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a);
if(a == 0)
y[m1++]=i;
else
{
while(--a)
x[n1++]=i;
}
}
for(int i=0;i<n1;i++)
for(int j=0;j<m1;j++)
{
int t=abs(x[i]-y[j]);
w[i][j]=(-1)*min(t,n-t);
}
printf("%d\n",-1*(KM(n1,m1)));
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
while(scanf("%d",&n)!=EOF)
solve();
return 0;
}



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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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