[bzoj2547]玩具兵<Spfa+二分+匈牙利算法>
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2547
挺有意思的一道题,这道题可以划分成几个小题。。。。。。。
题目大意:
三个兵种在一个n*m的图上,图的每一个格子有一个高度,三个兵种一种走不下降的路,一种走不上升的路,一种随便走。数量分别是k,k,1
然后t个目的地,每个目的地必须有ri个兵,ri之和为2*k+1
然后你可以交换兵,让不能走的情况又变成能走,例如,第一种兵走到了山顶,四周都是下降的,这时候就可以和第二,三种兵交换位置,继续走下去。。。
【解题思路】
这道题分解下来就是先来一个spfa找每一个兵到每一个点的最小交换次数,然后就是二分这个一共的交换次数,接着就是二分图匹配。。。
我们跑spfa,以每个兵开始扩展,遇到不能走就换一次,记录每个兵到每个点的最小交换次数,然后把当前兵到指定点的值记录入一个新的数组(表示二分图的连接情况)
然后二分。。因为最少是不交换,最大交换2*k次,因为可以每个兵和天兵交换一次然后去终点,天兵是随便走,所以最多交换2*k次,然后二分次数。。二分当中的check就是用二分图匹配了。。。Check成立的判断时交换次数+最大匹配数,如果这个值大于了兵的数量,说明这个方案是可行的。。。
这是大致思路,但是还是要注意一些细节的地方。
Spfa要注意当前的兵种是在变化的,所以要结合到当前位置之前的交换次数和最初状态
最初为0,交换偶数次,当前还是0,交换奇数次,当前为1
最初为1,交换偶数次,当前还是1,交换奇数次,当前为0
假设开始是c,次数是t,这个最终结果就是c^(t&1)
另外一个就是要注意二分图匹配时,除了要求vis[i]==0之外,还有x兵到i点的次数小于我们二分出来的限制。。。
然后就还是结合代码理解吧,我看别人的思路都不是很懂,还是结合代码读懂的。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<queue>
#define maxn 105
using namespace std; const int dx[]={,-,,,};
const int dy[]={,,,-,}; int att[maxn][maxn],h[maxn][maxn];
int f[maxn][maxn];//表示到达这个位置的最小交换次数
int n,m,k,t,r;
pair<int,int>a[maxn];
pair<int,int>b[maxn];
queue<pair<int,int> >q; void init()
{
scanf("%d%d%d%d",&n,&m,&k,&t);
for(int i=;i<=*k+;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
}
int tot=;
for(int i=;i<=t;i++)
{
scanf("%d%d%d",&b[tot].first,&b[tot].second,&r);
r--;tot++;
for(r;r>=;r--,tot++){
b[tot]=b[tot-];
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&h[i][j]);
} void bfs(int x,int y,int cnt){
memset(f,0x3f3f3f,sizeof(f));
f[x][y]=;
q.push(make_pair(x,y));
while(!q.empty()){
int nx=q.front().first,ny=q.front().second;
for(int i=;i<=;i++)
{
int nowx=nx+dx[i],nowy=ny+dy[i];
if(nowx<||nowx>n||nowy<||nowy>m)continue;
int tt=;
if(cnt^(f[nx][ny]&)){
if(h[nowx][nowy]>h[nx][ny])tt=;
}else if(h[nowx][nowy]<h[nx][ny])tt=;
if(f[nowx][nowy]>f[nx][ny]+tt){
f[nowx][nowy]=f[nx][ny]+tt;
q.push(make_pair(nowx,nowy));
} }
q.pop();
} } int vis[maxn*],ck[maxn*]; int ok(int x,int limit){
for(int i=;i<=*k+;i++)
{
if(vis[i]==&&att[x][i]<=limit){
vis[i]=;
if(ck[i]==||ok(ck[i],limit)){
ck[i]=x;return ;
}
}
}
return ;
} int check(int x){
memset(ck,,sizeof(ck));
int tot=;
for(int i=;i<=*k;i++){
memset(vis,,sizeof(vis));
if(ok(i,x))tot++;
}
if(tot+x>=*k)return ;
else return ;
} int ans(){
int l=,r=*k;//最坏情况就是天兵挨着和每一个交换,最多换2*k次
while(l<r){
int mid=(l+r)>>;
if(check(mid))r=mid;else l=mid+;
}
return l;
} int main()
{
init();
for(int i=;i<=*k;i++)
{
if(i<=k)bfs(a[i].first,a[i].second,);
else bfs(a[i].first,a[i].second,);
for(int j=;j<=*k+;j++){
att[i][j]=f[b[j].first][b[j].second];
}
}
printf("%d\n",ans());
}
总结:
把一个大题打乱成多个小题是一个很有效的方式
注意分析状态的变化,比如题中的兵种在spfa的时候是变化的
最新文章
- hibernate 的SessionFactory的getCurrentSession 与 openSession() 的区别
- 总结-html
- Sublime Text插件:HTML-CSS-JS Prettify
- phpcms常用方法简介
- phpcms 标签
- 使用Redux管理你的React应用
- web开发-给即将毕业实习生的一点面试经验
- 20145221 《Java程序设计》实验报告二:Java面向对象程序设计
- linux清空文件等有用的指令
- xampp改到phpmyadmin的root密碼無法登錄
- poj3537--Crosses and Crosses
- REST Web Server,REST介绍
- Linux应用环境
- iOS-状态栏字体颜色【白色】【Xcode9.1】
- Ubuntu如何配置SSH免密登录
- UI前端开发都是做什么的以及html、css、php、js等究竟是神马关系
- [SCOI2014]方伯伯的玉米田
- webrtc aecd算法解析一(原理分析)
- python+opencv 运行环境搭建
- Linux 常用基本命令及应用技巧
热门文章
- css实战#用css画一个中国结
- Vmware安装的linux系统开机黑屏,关闭显示虚拟机忙怎么怎么解决?
- 小白的springboot之路(十六)、mybatis-plus 的使用
- 基于springcloud搭建项目-公共篇(二)
- php判断二个数最大公约数
- Matplotlib数据可视化(6):饼图与箱线图
- 编译 AR9271 wifi 网卡固件 htc_9271.fw
- 【Spring Data 系列学习】Spring Data JPA @Query 注解查询
- pip 安装超时问题
- 深入理解计算机系统 (CS:APP) - 高速缓存实验 Cache Lab 解析