$BZOJ3232$ 圈地游戏 网络流

正解:最小割+01分数规划

解题报告:

传送门$QwQ$

感$jio$这个好像是$NOIp2018$集训的时候$cjk$学长讲01分数规划的时候港的,,,?$QwQ$虽然我还是不会嘤

首先看到这个分数形式,又说是最大值,显然考虑01分数规划呗?然后就考虑怎么$check$?

先更新下每条边的权值变成了$ed_{val}\cdot mid$,然后现在就要算$\sum ed_{val}-\sum nod_{val}$

然后再考虑下什么样的边会被计入?就如果一条边的一边格子被选了另一边没被选就会被计入答案嘛$QwQ$

这时候就会$jio$得有点儿像最小割辣,,,?就是减法,然后又有一定的彼此之间滴制约关系啥的

然后我开始想到这儿就$jio$得,黑白染色然后黑色建一排白色建一排相邻格子之间连边然后就做完辣$QwQ$?

仔细一想发现布星,因为这样并不能保证只围出了一个圈,,,不能作出约束$QwQ$

于是考虑再换一种建边方式?发现上面的问题在于没有对不能选的点作出约束,所以显然所有点要放一排$QwQ$

欧克这样显然可以满足关于点的需求了,但是依然要考虑关于边的条件$QwQ$

考虑相邻格子之间连流量为边权的双向边,保证如果两个点中如果相邻俩格子一个选了一个没选就必须把这条边的边权也割了$QwQ$

然后还有就所有边界上的点都要和$T$连一条流量为边界边权的边,这个挺显然?因为如果选了这个点一定是要付出边权的代价的鸭$QwQ$

然后就跑个最小割就成$QwQ$

如果实在无法理解建图的可以自己画下图,,,说实话这个建图方法我也麻油想到,我看了题解之后自己画了个图才$get$的,,,$QwQ$

$over$

最后我一定要感谢这道题,,,它让我意识到我滴二分+网络流一定有问题,,,(我连$T$三道二分+网络流就是找不到错我还以为是我常数太大嘤,,,

港下问题在哪儿$QwQ$?就,$bfs,dfs,dinic$中判断$\neq 0$改成判断$>eps$,$over$

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define lf double
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define n(i) edge[i].nxt
#define ri register int
#define rb register int
#define rc register char
#define rp(i,x,y) for(int i=x;i<=y;++i)
#define my(i,x,y) for(int i=x;i>=y;--i)
#define e(i,x) for(int i=head[x];~i;i=n(i)) const int N=1e4+,M=;
const lf eps=1e-,inf=1e9;
int n,m,dep[N],head[N],cur[N],S,T,ed_cnt=-,val[M][M],h[M][M],s[M][M];
lf l,r=,sum;
struct ed{int to,nxt;lf wei;}edge[N<<]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il int nam(ri x,ri y){return (x-)*m+y;}
il void ad(ri x,ri y,lf z)
{
//printf("%d -> %d : %.3lf\n",y,x,z);
edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,,sizeof(dep));dep[S]=;
while(!Q.empty())
{ri nw=Q.front();Q.pop();e(i,nw)if(w(i)>eps && !dep[t(i)]){dep[t(i)]=dep[nw]+,Q.push(t(i));if(t(i)==T)return ;}}
return ;
}
lf dfs(ri nw,lf flow)
{
if(nw==T || flow<eps)return flow;lf ret=;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i)>eps && dep[t(i)]==dep[nw]+)
{lf tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^)+=tmp,flow-=tmp;}
if(ret<eps)dep[nw]=;
return ret;
}
il lf dinic(){lf ret=;while(bfs()){rp(i,S,T)cur[i]=head[i];while(){lf d=dfs(S,inf);ret+=d;if(d<=eps)break;}}return ret;}
il bool check(lf mid)
{
memset(head,-,sizeof(head));ed_cnt=-;
rp(i,,n)rp(j,,m)ad(nam(i,j),S,val[i][j]);
rp(i,,n-)rp(j,,m)ad(nam(i+,j),nam(i,j),mid*h[i][j]),ad(nam(i,j),nam(i+,j),mid*h[i][j]);
rp(i,,n)rp(j,,m-)ad(nam(i,j),nam(i,j+),mid*s[i][j]),ad(nam(i,j+),nam(i,j),mid*s[i][j]);
rp(i,,m)ad(T,nam(,i),mid*h[][i]),ad(T,nam(n,i),mid*h[n][i]);//,printf("QwQ mid=%lf h=%d h=%d\n",mid,h[0][i],h[n][i]);
rp(i,,n)ad(T,nam(i,),mid*s[i][]),ad(T,nam(i,m),mid*s[i][m]);//,printf("QwQQ mid=%lf s=%d s=%d\n",mid,s[i][0],s[i][m]);
lf tmp=dinic();
//printf("mid=%.3lf sum=%lf dinic()=%.3lf\n",mid,sum,tmp);
return abs(sum-tmp)>eps;
} int main()
{
//freopen("3232.in","r",stdin);freopen("3232.out","w",stdout);
n=read();m=read();S=;T=n*m+;
rp(i,,n)rp(j,,m)sum+=(val[i][j]=read());rp(i,,n)rp(j,,m)h[i][j]=read();rp(i,,n)rp(j,,m)s[i][j]=read();
while(r-l>eps){lf mid=(l+r)/;if(check(mid))l=mid;else r=mid;}
printf("%.3lf\n",r);
return ;
}

随机推荐

  1. VMware中的Ubuntu网络设置

    网络配置: VMware安装后会有两个默认网卡,分别是VMnet8(192.168.83.1)和VMnet1(192.168.19.1),当然不同的机器上,这两个网卡的 IP会不同的.在windows ...

  2. Eclipse c&plus;&plus;头文件问题(未完)

    http://*.com/questions/7905025/string-could-not-resolved-error-in-eclipse-for-c-eclipse- ...

  3. Delphi 线程的处理

    http://www.cnblogs.com/doit8791/archive/2012/05/16/2502671.html

  4. Android新浪微博客户端(七)——ListView中的图片异步加载、缓存

    原文出自:方杰|http://fangjie.info/?p=193转载请注明出处 最终效果演示:http://fangjie.sinaapp.com/?page_id=54 该项目代码已经放到git ...

  5. Linux学习3——磁盘文件管理系统与压缩和打包操作

    一.写在前面  本节将对Linux的磁盘文件系统.文件的压缩打包等操作进行简要介绍. 二.完成目标 1.了解磁盘文件系统的接本知识 2.操作文件和目录的相关命令 3.文件系统的简单操作命令 4.Lin ...

  6. Oracle Bills of Material and Engineering Application Program Interface &lpar;APIs&rpar;

    In this Document Goal   Solution   1. Sample Notes for BOM APIs   2. Datatypes used in these APIs   ...

  7. 使用pip安装报错的处理方法&lowbar;2

    终端更新pip出错 sudo pip install --upgrade pip : 1.ReadTimeoutError: HTTPSConnectionPool(host='pypi.Python ...

  8. SublimeText快捷键

    在我做了一次包含一些现场编码的演示后,一些观众问我是如何操作这么快.当然这里没有唯一的答案,答案是一堆简单的快捷键和大量的实践的组合.为了回应那些询问,我觉得有必要看看我每天想都不用想且使用的快捷键. ...

  9. 我在微信小程序遇到的坑

    这段时间刚好结束一个小程序,被坑的好惨,所以罗列出来,有用的着的,就抱走吧! 1.关于音频,项目要求能在退出小程序的情况下继续播放,所以我直接用了     wx.getBackgroundAudioM ...

  10. Chrome 浏览器快捷键

    Ø  前言 记录下 Chrome 的快捷键,原文链接:http://www.cnblogs.com/mikalshao/archive/2010/11/03/1868568.html   1.   标 ...

上一篇:转 iOS 调试技巧


下一篇:ProgressDialog(三)——代号为中心的屏幕上显示ProgressDialog(ProgressBar)