BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流

时间:2021-12-23 02:03:46

https://darkbzoj.cf/problem/2055

https://blog.csdn.net/Clove_unique/article/details/54864211 ←对有上下界费用流的处理方法

首先建立附加源汇ss,tt 
对于原图里有的一条边x->y,[l,r],cost,变成x->y,r-l,cost 
每一个点的权di定义为所有流入这个点的边的下界和-所有流出这个点的边的下界和 
对于一个点i,若di>0,ss->i,di,0;若di<0,i->tt,-di,0 
连边t->s,inf,0 
然后对ss,tt做最小费用最大流 
最终的费用为(网络流中计算的费用+原图中有费用的边的下界*这条边的费用)

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
const int minf=;
int n,m,S,T,SS,mx,ans;
struct nod{
int x,y,v,co,rev,next;
}e[maxn*maxn];
int head[maxn]={},tot=;
int dis[maxn]={},fa[maxn]={},vis[maxn]={};
inline void init(int x,int y,int v,int co){
e[++tot].x=x;e[tot].y=y;e[tot].v=v;e[tot].co=co;e[tot].rev=tot+;e[tot].next=head[x];head[x]=tot;
e[++tot].x=y;e[tot].y=x;e[tot].v=;e[tot].co=-co;e[tot].rev=tot-;e[tot].next=head[y];head[y]=tot;
}
queue<int>q;
inline bool SPFA(){
memset(dis,,sizeof(dis));
memset(fa,,sizeof(fa));
mx=dis[];
q.push(S);dis[S]=;
while(!q.empty()){
int x=q.front();q.pop();vis[x]=;
for(int i=head[x];i;i=e[i].next){
int y=e[i].y;
if((!e[i].v)||dis[y]<=e[i].co+dis[x])continue;
dis[y]=e[i].co+dis[x];fa[y]=i;
if(!vis[y]){
q.push(y);vis[y]=;
}
}
}
return dis[T]!=mx;
}
inline void doit(){
int val=mx;
for(int i=fa[T];i;i=fa[e[i].x])val=min(val,e[i].v);
for(int i=fa[T];i;i=fa[e[i].x]){e[i].v-=val; e[e[i].rev].v+=val; ans+=e[i].co*val;}
}
int main(){
int x;
scanf("%d%d",&n,&m);S=n*+;T=S+;SS=T+;
for(int i=;i<=n;i++){
scanf("%d",&x);
if(x<=)continue;
init(i,i+n,,);
init(S,i+n,x,); init(i,T,x,);
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
scanf("%d",&x);if(x!=-)init(i+n,j,minf,x);
}
}
init(S,SS,m,);
for(int i=;i<=n;i++) init(SS,i,minf,);
ans=;
while(SPFA())doit();
printf("%d\n",ans);
return ;
}

BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流的更多相关文章

  1. &lbrack;bzoj2055&rsqb;80人环游世界&lbrack;网络流,上下界网络流&rsqb;

    手动画了整张图,,算是搞懂了吧,, #include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; templat ...

  2. BZOJ 3876 支线剧情 有源汇有上下界最小费用可行流

    题意: 给定一张拓扑图,每条边有边权,每次只能从第一个点出发沿着拓扑图走一条路径,求遍历所有边所需要的最小边权和 分析: 这道题乍一看,可能会想到什么最小链覆盖之类的,但是仔细一想,会发现不行,一是因 ...

  3. &lbrack;BZOJ2055&rsqb;80人环游世界 有上下界最小费用最大流

    2055: 80人环游世界 Time Limit: 10 Sec  Memory Limit: 64 MB Description     想必大家都看过成龙大哥的<80天环游世界>,里面 ...

  4. BZOJ2055&colon; 80人环游世界

    题解: 总算A掉了,各种蛋疼... int main() { freopen("input.txt","r",stdin); freopen("out ...

  5. zoj3229 Shoot the Bullet&lpar;有源汇有上下界的最大流&rpar;

    题意: 一个屌丝给m个女神拍照,计划拍照n天,每一天屌丝给给定的C个女神拍照,每天拍照数不能超过D张,而且给每个女神i拍照有数量限制[Li,Ri],对于每个女神n天的拍照总和不能少于Gi,如果有解求屌 ...

  6. zoj 3229 有源汇有上下界的最大流模板题

    /*坑啊,pe的程序在zoj上原来是wa. 题目大意:一个屌丝给m个女神拍照.计划拍照n天,每一天屌丝最多个C个女神拍照,每天拍照数不能超过D张,并且给每一个女神i拍照有数量限制[Li,Ri], 对于 ...

  7. Shoot the Bullet ZOJ - 3229 有源汇有上下界的最大流

    /** zoj提交评判不了,所以不知道代码正不正确.思路是应该没问题的.如果有不对的地方,请多指教. 题目:Shoot the Bullet ZOJ - 3229 链接:https://vjudge. ...

  8. 【上下界网络流 费用流】bzoj2055&colon; 80人环游世界

    EK费用流居然写错了…… Description     想必大家都看过成龙大哥的<80天环游世界>,里面的紧张刺激的打斗场面一定给你留下了深刻的印象.现在就有这么     一个80人的团 ...

  9. bzoj千题计划159:bzoj2055&colon; 80人环游世界(有源汇上下界可行最小费用流)

    http://www.lydsy.com/JudgeOnline/problem.php?id=2055 某个国家必须经过vi次, 可以转化为上下界都为vi的边 对这张图做有源汇上下界可行最小费用流 ...

随机推荐

  1. &lbrack;bzoj2732&rsqb;&lbrack;HNOI2012&rsqb;射箭

    Description 沫沫最近在玩一个二维的射箭游戏,如下图所示,这个游戏中的$x$轴在地面,第一象限中有一些竖直线段作为靶子,任意两个靶子都没有公共部分,也不会接触坐标轴.沫沫控制一个位于$(0, ...

  2. JS 4 新特性:混合属性(mixins)之二

    Mixins many classes[混合许多个类] 迄今为止,我们已经学会了简单的继承,我们还能够通过使用mixins处理机制来混合许多类.源于这种理念是非常简单的:我们能够把许多个类最终混合到一 ...

  3. 2014 Super Training &num;8 A Gears --并查集

    题意: 有N个齿轮,三种操作1.操作L x y:把齿轮x,y链接,若x,y已经属于某个齿轮组中,则这两组也会合并.2.操作Q x y:询问x,y旋转方向是否相同(等价于齿轮x,y的相对距离的奇偶性). ...

  4. js原生设计模式——3简单工厂模式&bsol;js面向对象编程实例

    <!DOCTYPE html><html lang="en"><head>    <meta charset="UTF-8&qu ...

  5. Linux 环境下 MySQ导入和导出MySQL的sql文件

    将服务器上的文件导入或导出还需要使用工具传输到本机中,推荐使用winscp,与xshell搭配使用 1 导入数据库 两种方法 .首先建空数据库 mysql>create database abc ...

  6. 快速搭建vsftp 服务器并配置指定目录

    1  搭建vsftp 服务器 前期准备: 1.用root 进入系统 2.使用命令 rpm  -qa|grep vsftpd 查看系统是否安装了ftp,若安装了vsftp,使用这个命令会在屏幕上显示vs ...

  7. 搭建vue的开发环境

    随手笔记:win7 64bit 1.安装node,直接从node官网下载,安装即可. 2.命令行输入 node -v 查看是否安装成功,显示node的版本号即安装成功.安装成功后,输入node,进入n ...

  8. Day 5-6 反射和内置方法之item系列

    python面向对象中的反射:通过字符串的形式操作对象相关的属性.python中的一切事物都是对象(都可以使用反射) #!_*_ coding:utf-8 _*_ class People: def ...

  9. Android 性能测试之CPU

    接上一篇 CPU跟内存一样,存在一些测试子项,如下清单所示 1.空闲状态下的应用CPU消耗情况 2.中等规格状态下的应用CPU消耗情况 3.满规格状态下的应用CPU消耗情况 4.应用CPU峰值情况 C ...

  10. 将jsonModel转化为文件

    将jsonModel转化为文件 这个类是我自己写着用的,用于将字典文件直接转换成Model的文件,省去你写无数Model中属性的代码: TransformDictionary.h 与 Transfor ...