EK费用流居然写错了……
Description
Input
Output
在第一行输出最少的总费用。
Sample Input
2 1 3 1 2 1
2 6 8 5 0
8 2 4 1
6 1 0
4 -1
4
Sample Output
HINT
1<= N < =100 1<= M <= 79
题目分析
这就是一个无源汇最小费用最大流的模型,关于M个人的限制则是把(TT,SS)的边流量设为M
掌握得还是不够熟练啊
#include<bits/stdc++.h>
const int maxn = ;
const int maxm = ;
const int INF = 2e9; struct Edge
{
int u,v,f,c,cst;
Edge(int a=, int b=, int c=, int d=, int e=):u(a),v(b),f(c),c(d),cst(e) {}
}edges[maxm];
int n,m,S,T,SS,TT,ans;
int edgeTot,head[maxn],nxt[maxm],bck[maxm],cst[maxn],flw[maxn];
bool inq[maxn<<]; void addedge(int u, int v, int c, int cst)
{
edges[edgeTot] = Edge(u, v, , c, cst), nxt[edgeTot] = head[u], head[u] = edgeTot, ++edgeTot;
edges[edgeTot] = Edge(v, u, , , -cst), nxt[edgeTot] = head[v], head[v] = edgeTot, ++edgeTot;
}
void maxFlow()
{
for (;;)
{
std::queue<int> q;
memset(flw, , sizeof flw);
memset(bck, , sizeof bck);
memset(cst, 0x3f3f3f3f, sizeof cst);
q.push(S), flw[S] = INF, cst[S] = ;
for (int tmp; q.size(); )
{
tmp = q.front(), q.pop(), inq[tmp] = ;
for (int i=head[tmp]; i!=-; i=nxt[i])
{
int v = edges[i].v;
if (cst[tmp]+edges[i].cst < cst[v]&&edges[i].f < edges[i].c){
cst[v] = cst[tmp]+edges[i].cst, bck[v] = i;
flw[v] = std::min(flw[tmp], edges[i].c-edges[i].f);
if (!inq[v]) q.push(v), inq[v] = ;
}
}
}
if (!flw[T]) break;
for (int i=T; i!=S; i=edges[bck[i]].u)
edges[bck[i]].f += flw[T], edges[bck[i]^].f -= flw[T];
ans += flw[T]*cst[T];
}
}
int main()
{
memset(head, -, sizeof head);
scanf("%d%d",&n,&m);
S = n+n+, T = S+, SS = T+, TT = SS+;
for (int i=,v; i<=n; i++)
{
scanf("%d",&v);
addedge(S, i+n, v, );
addedge(i, T, v, );
addedge(SS, i, INF, );
addedge(i+n, TT, INF, );
}
addedge(TT, SS, m, );
for (int i=; i<=n; i++)
for (int j=,x; j<=n-i; j++)
{
scanf("%d",&x);
if (x!=-) addedge(i+n, i+j, INF, x);
}
maxFlow();
printf("%d\n",ans);
return ;
}
END
【上下界网络流 费用流】bzoj2055: 80人环游世界的更多相关文章
-
[BZOJ2055]80人环游世界 有上下界最小费用最大流
2055: 80人环游世界 Time Limit: 10 Sec Memory Limit: 64 MB Description 想必大家都看过成龙大哥的<80天环游世界>,里面 ...
-
BZOJ2055: 80人环游世界
题解: 总算A掉了,各种蛋疼... int main() { freopen("input.txt","r",stdin); freopen("out ...
-
BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流
https://darkbzoj.cf/problem/2055 https://blog.csdn.net/Clove_unique/article/details/54864211 ←对有上下界费 ...
-
bzoj千题计划159:bzoj2055: 80人环游世界(有源汇上下界可行最小费用流)
http://www.lydsy.com/JudgeOnline/problem.php?id=2055 某个国家必须经过vi次, 可以转化为上下界都为vi的边 对这张图做有源汇上下界可行最小费用流 ...
-
[bzoj2055]80人环游世界[网络流,上下界网络流]
手动画了整张图,,算是搞懂了吧,, #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; templat ...
-
bzoj2055: 80人环游世界(可行流)
传送门 表示完全看不懂最小费用可行流…… 据某大佬说 我们考虑拆点,然后进行如下连边 $s$向$a_i$连边,权值$0$,容量$[0,m]$ $a_i$向$a_i'$连边,权值$0$容量$[v_i,v ...
-
【BZOJ2055】80人环游世界 有上下界费用流
[BZOJ2055]80人环游世界 Description 想必大家都看过成龙大哥的<80天环游世界>,里面的紧张刺激的打斗场面一定给你留下了深刻的印象.现在就有这么 一个 ...
-
【BZOJ-2055】80人环游世界 上下界费用流 (无源无汇最小费用最大流)
2055: 80人环游世界 Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 321 Solved: 201[Submit][Status][Discus ...
-
P4553 80人环游世界(上下界费用流)
P4553 80人环游世界 emm......先从上下界网络流(转)开始 再到现在的上下界费用流 因为有上下界,我们需要记下每个点的流量差$ex[i]$,用于调整 $ins(x,y,l,r,v)=li ...
随机推荐
-
关于七牛云存储,HTTPS资源上传不成功问题
关于七牛云存储,HTTPS资源上传不成功问题 官方给出了一个解决方案,亲测可用.特此记录一下. 找到QNConfiguration.m文件.然后重写两个方法,直接上代码. + (instancetyp ...
-
oracle数据库使用plsql(64位)时出现的问题
64位win7上装PL/SQL,经常会遇见“Could not load "……\bin\oci.dll"”这个错误,我查了一下资料,原因是PL/SQL只对32位OS进行支持,解决 ...
-
codeforces 702E Analysis of Pathes in Functional Graph 倍增
题目链接 给一个图, 然后给出每条边的权值和一个k值. 让你求出从每个点出发, 走k次能获得的边权的和以及边权的最小值. 用倍增的思想, 求出每个点走一次能到达的点, 权值和以及最小值, 走两次..四 ...
-
ExtJS4.2学习(三)——入门基础
1.怎么给某一组件注册事件? 先画一个组件,然后在控制器中加入对这个组件的处理(包括组件对应的方法调用和方法定义). 2.ExtJS4的提示框和JS的差异: ExtJS4:一步走完程序: JS:让程序 ...
-
全网最详细的如何在谷歌浏览器里正确下载并安装Postman【一款功能强大的网页调试与发送网页HTTP请求的Chrome插件】(图文详解)
不多说,直接上干货! 想必,玩过Java Web的你,肯定是对于http post和get等请求测试的过程记忆犹新吧. Postman的安装方法分好几种,主要分为两种安装模式介绍: (1)chrome ...
-
sql里 where和order by一起使用是怎样的顺序
where 列2 = ‘条件1’ 这个先执行过滤后的数据 再order by ‘条件2’最后取第一条数据也就是先where 再order by 再limit
-
display: table 实现menu等高居中排列
display: table 属性,顾名思义,就是就像表格一样陈列元素,设置这个属性之后,就具有了表格所特有的某些特性,比如居中对齐之类的. 本篇文章要实现的需求也是非常常见的——左侧栏menu菜单居 ...
-
linux输入法
sudo apt-get install fcitx-table-wbpy安装fcitx 中文是灰色的就拖到第一个 桌面右上角有个设置,可以添加拼音 拼音特别难用
-
svg用作背景图
svg用做背景图的几种方式 1. 直接使用 background: url('data:image/svg+xml;charset=utf-8,<svg width="10" ...
-
mysql binlog 使用
用于数据恢复的binlog 前提条件 1.定时mysqldumps全备数据库 2.开启binlog增量备份 情景:手滑误操作删表操作 立刻 mysql>flush logs; #开启一个新的b ...