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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3232]圈地游戏  

2015-04-26 17:36:33|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3232: 圈地游戏

差一点就想出来了……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long double ld;
const int N = 60;
const int P = N*N;
const int M = P*20;
const int MAX = 1E9+10;
const ld eps = 1e-13;
int scan(){int i=0;scanf("%d",&i);return i;}
struct Point{
Point(){next=NULL;}
Point *next;int d;
void push(int);
}point[P],*cur[P];
queue<Point*>pupa;
Point *newPoint(){
if(pupa.empty())return newPoint();
Point *r = pupa.front();pupa.pop();
if(r->next)pupa.push(r->next);
*r = Point();return r;
}
void Point::push(int a){
Point *l = new Point;
l->d = a;
l->next=next;next=l;
}
struct Edge{
int from,to;ld flow,cap;
Edge(int f=0,int t=0,ld fl=0,ld c=0){from=f;to=t;flow=fl;cap=c;}
}edges[M];
int n,m,level[P],gap[P],data[N][N],right[N][N],down[N][N];
int T,start,end,large;
ld dfs(int x,ld a){
if(x==end)return a;
ld flow=0,l;
for(Point *i = cur[x];i;i=i->next){
Edge &e = edges[i->d];
if(e.cap > eps + e.flow && level[x]-1 == level[e.to]){
cur[x] = i;
l = dfs(e.to,min(a,e.cap - e.flow));
e.flow += l;flow += l;
edges[i->d^1].flow -= l;a -= l;
if(a < eps)return flow;
}
}
cur[x] = point[x].next;
if(!(--gap[level[x]]))level[start] = large;
gap[++level[x]] += 1;
return flow;
}
ld isap(){
for(int i=1;i<=large;i++)level[i]=gap[i]=0,cur[i]=point[i].next;
ld flow=0;gap[0]=large;
while(level[start] < large)
flow += dfs(start,MAX);
return flow;
}
void AddEdge(int from,int to,ld cap,ld rcap=0){
// printf("%d->%d[%.3f]\n",from,to,cap);if(rcap > eps)printf("%d->%d[%.3f]\n",to,from,rcap);
point[from].push(T);
edges[T++] = Edge(from,to,0,cap);
point[to].push(T);
edges[T++] = Edge(to,from,0,rcap);
}
void clear(){T=0;for(int i=1;i<=large;i++)if(point[i].next)pupa.push(point[i].next),point[i].next=NULL;}
bool check(ld mid){
//make graph
int i,j,now=0;
ld all=0;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++){
now++;
if(data[i][j] < 0)AddEdge(now,end,MAX);
else AddEdge(start,now,data[i][j]),all += data[i][j];
//right
if(j!=m+1&&i!=0)
AddEdge(now,now+1,mid*right[i][j],mid*right[i][j]);
//down
if(i!=n+1&&j!=0)
AddEdge(now,now+m+2,mid*down[i][j],mid*down[i][j]);
}
all -= isap();
return all > eps;
}
int main(){
int i,j;
n = scan();m = scan();
start = (n+2)*(m+2)+1;
large = end = start + 1;
for(i=0;i<=n+1;i++)
for(j=0;j<=m+1;j++)
data[i][j]=-1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
data[i][j]=scan();
for(i=0;i<=n;i++)
for(j=1;j<=m;j++)
down[i][j] = scan();
for(i=1;i<=n;i++)
for(j=0;j<=m;j++)
right[i][j] = scan();
ld l,r;
l = 0;r = 1e9;
while(r-l > 1e-6){
ld mid = (l+r)/2;
if(check(mid))l = mid;
else r = mid;
clear();
}
printf("%.3f\n",(double)l);
return 0;
}

题解:
首先要求一个分数的极值,显然是分数规划
我们二分答案t然后看一下z=max(C - t*V)是否大于等于0,如果是的话就说明这是可行的答案。
然后问题就是要怎么搞求这个东西的极值
一看是选格子什么的,有收益有损失,自然联想到最小割模型
但是问题在与最小割模型选出来的东西不一定是一个联通块。
不过没关系,因为我们求的东西是个比率,所以显然一定是一个联通块最优(不过我不知道是不是对于Z同样)
然后在周围加一圈不能选的点,直接最小割就好辣
  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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