BZOJ.3698.XWW的难题(有源汇上下界最大流ISAP)

时间:2022-09-22 23:03:35

题目链接

按套路行列作为两部分,连边 \(S->row->column->T\)。

S向代表行的元素连边cap(A[i][n])(容量上下界为上下取整),代表列的元素向T连边cap(A[n][i]),对于每个元素(i,j)由行i向列j连边cap(A[i][j]).

考虑我们建的这张图实际流量是什么,对于 \(S->Row_i->(i,j)->Col_j->T\),设这是x的流量,实际表示A[i][n]多加了x,A[i][j]多加了x,A[n][i]多加了x;

答案要求整个矩阵,所以最后的最大流*3即可。

有源汇上下界不需要再统计每条边的流量下限了,因为有一条T->S的边,在第一次求最大流时所有边的流量下限已经加到反向边S->T上了,所以第二次直接求S->T最大流即可。

//60476kb	92ms
#include <cstdio>
#include <algorithm>
const int N=1e6,M=1e6,INF=0x3f3f3f3f; int n,src,des,dgr[N],Enum,cur[N],H[N],fr[M<<1],to[M<<1],nxt[M<<1],cap[M<<1],lev[N],num[N],q[N],pre[N];
double A[103][103];
bool inq[N]; inline void AddEdge(int u,int v,int w)
{
if(w)
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w,
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0;
}
bool BFS()
{
for(int i=0; i<des; ++i) lev[i]=des+1;
q[0]=des, lev[des]=0; int h=0,t=1;
while(h<t)
{
int x=q[h++];
for(int i=H[x]; i; i=nxt[i])
if(lev[to[i]]==des+1 && cap[i^1])
lev[to[i]]=lev[x]+1, q[t++]=to[i];
}
return lev[src]<=des;
}
int Augment()
{
int mn=INF;
for(int i=des; i!=src; i=fr[pre[i]])
mn=std::min(mn,cap[pre[i]]);
for(int i=des; i!=src; i=fr[pre[i]])
cap[pre[i]]-=mn, cap[pre[i]^1]+=mn;
return mn;
}
int ISAP()
{
if(!BFS()) return 0;
for(int i=0; i<=des; ++i) ++num[lev[i]],cur[i]=H[i];
int x=src,res=0;
while(lev[src]<=des)
{
if(x==des) x=src,res+=Augment();
bool can=0;
for(int i=cur[x]; i; i=nxt[i])
if(lev[to[i]]==lev[x]-1 && cap[i])
{
can=1, cur[x]=i, pre[x=to[i]]=i;
break;
}
if(!can)
{
int mn=des;
for(int i=H[x]; i; i=nxt[i])
if(cap[i]) mn=std::min(mn,lev[to[i]]);
if(!--num[lev[x]]) break;
++num[lev[x]=mn+1];
cur[x]=H[x];
if(x!=src) x=fr[pre[x]];
}
}
return res;
} int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
int S=0, T=n<<1|1; Enum=1, src=S, des=T;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j) scanf("%lf",&A[i][j]);
int res=0;
for(int i=1; i<n; ++i) dgr[src]-=(int)A[i][n],dgr[i]+=(int)A[i][n], AddEdge(src,i,(A[i][n]-(int)A[i][n])>0);
for(int i=1; i<n; ++i) dgr[i+n]-=(int)A[n][i],dgr[des]+=(int)A[n][i], AddEdge(i+n,des,(A[n][i]-(int)A[n][i])>0);
for(int i=1; i<n; ++i)
for(int j=1; j<n; ++j)
dgr[i]-=(int)A[i][j],dgr[j+n]+=(int)A[i][j], AddEdge(i,j+n,(A[i][j]-(int)A[i][j])>0);
int SS=des+1,TT=des+2; src=SS, des=TT;
for(int i=S; i<=T; ++i)
if(dgr[i]>0) dgr[SS]+=dgr[i],AddEdge(SS,i,dgr[i]);
else if(dgr[i]<0) AddEdge(i,TT,-dgr[i]);
AddEdge(T,S,INF);
if(ISAP()==dgr[SS]) src=S,des=T,printf("%d",3*ISAP());
else printf("No"); return 0;
}

BZOJ.3698.XWW的难题(有源汇上下界最大流ISAP)的更多相关文章

  1. BZOJ 3698&colon; XWW的难题 &lbrack;有源汇上下界最大流&rsqb;

    3698: XWW的难题 题意:(1)A[N][N]=0:(2)矩阵中每行的最后一个元素等于该行前N-1个数的和:(3)矩阵中每列的最后一个元素等于该列前N-1个数的和.给A中的数进行取整操作(可以是 ...

  2. 3698&colon; XWW的难题&lbrack;有源汇上下界最大流&rsqb;

    3698: XWW的难题 Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 354  Solved: 178[Submit][Status][Discus ...

  3. BZOJ 2502 清理雪道(有源汇上下界最小流)

    题面 滑雪场坐落在FJ省西北部的若干座山上. 从空中鸟瞰,滑雪场可以看作一个有向无环图,每条弧代表一个斜坡(即雪道),弧的方向代表斜坡下降的方向. 你的团队负责每周定时清理雪道.你们拥有一架直升飞机, ...

  4. BZOJ 3698 XWW的难题:有上下界的最大流

    传送门 题意 给你一个 $ n*n $ 的正实数矩阵 $ A $ ,满足XWW性. 称一个 $ n*n $ 的矩阵满足XWW性当且仅当: $ A[n][n] = 0 $ 矩阵中每行的最后一个元素等于该 ...

  5. bzoj 2406&colon; 矩阵【二分&plus;有源汇上下界可行流】

    最大值最小,所以考虑二分 |Σaij-Σbij|<=mid,所以Σbij的上下界就是(Σaij-mid,Σaij+mid) 考虑建有上下界网络,连接(s,i,Σaik-mid,Σaik+mid) ...

  6. bzoj 2502 清理雪道 (有源汇上下界最小流)

    2502: 清理雪道 Time Limit: 10 Sec  Memory Limit: 128 MB Description        滑雪场坐落在FJ省西北部的若干座山上. 从空中鸟瞰,滑雪场 ...

  7. BZOJ 2406 矩阵(二分&plus;有源汇上下界可行流)

    题意 题解 二分答案+可行流判断. 模板题. CODE #include <cstdio> #include <cstring> #include <algorithm& ...

  8. 【有源汇上下界费用流】BZOJ 3876 &lbrack;Ahoi2014&rsqb;支线剧情

    题目链接: http://www.lydsy.com:808/JudgeOnline/problem.php?id=3876 题目大意: 给定一张拓扑图(有向无环图),每条边有边权,每次只能从第一个点 ...

  9. BZOJ 2502 清理雪道&sol; Luogu P4843 清理雪道 &lpar;有源汇上下界最小流&rpar;

    题意 有一个有向无环图,求最少的路径条数覆盖所有的边 分析 有源汇上下界最小流板题,直接放代码了,不会的看dalao博客:liu_runda 有点长,讲的很好,静心看一定能看懂 CODE #inclu ...

随机推荐

  1. 由SecureCRT引发的思考和学习

    由SecureCRT引发的思考和学习 http://mp.weixin.qq.com/s?__biz=MzAxOTAzMDEwMA==&mid=2652500597&idx=1&amp ...

  2. MySQL 通过mysql&lowbar;config&lowbar;editor更安全的登录数据库

    在5.6版本中,MySQL可以通过mysql_config_editor登录数据库,变得更加安全. [root@hank-yoon ~]# mysql_config_editor set --logi ...

  3. Linux学习笔记--(1)

    今天用Linux 的 test 命令,发现了一个有趣的现象: 打入 " test "abc"="abc" ;echo $? " 后,结果应该 ...

  4. linux&lowbar;grep

    grep常用的命令行选项: 选项 说明 -c 只显示有多少行匹配,而不具体显示匹配的行. -h 不显示文件名. -i 在字符串比较的时候忽略大小写. -l 只显示包含匹配模板的行的文件名清单. -L ...

  5. debian安装后sudo命令不能用的解决方法

    注:转载他人 且试用过了,我的debian版本是debian8.2 64X debian安装完之后发现sudo命令不能用 找了半天发现是没有安装sudo 得了,进入root安包,炸开他,apt-get ...

  6. 封装好的图片滑动框架&lpar;AndroidImageSlider&rpar;

    前言 广告轮播条的重要性不言而喻.在很多类型app中出场率都很高. 今天给大家介绍一个轮播图开源项目,这个项目把轮播图需要的ViewPager跟计时器做了封装,使用极其方便,支持gradle在线依赖. ...

  7. POJ1032 Parliament(数论)

    New convocation of The Fool Land's Parliament consists of N delegates. According to the present regu ...

  8. kaptcha验证码插件使用与参数

    kaptcha使用1 kaptcha使用2 kaptcha使用3 kaptcha参数说明

  9. Python后端相关技术&sol;工具栈

    编辑器 最常见: vim / SublimeText2 / PyCharm Vim有兴趣可以看看 k-vim 适合Python/Golang开发 本地环境 pip/easy_install 包管理 v ...

  10. SQL Tuning Advisor

    SQL Tuning Advisorsql调优顾问可提供的建议有:-收集对象的统计信息-创建索引-重写sql语句-创建sql profile-创建sql plan baseline SQL Tunin ...