本蒟蒻又来写解题报告了。这次的题目是codevs 1035 火车停留。
题目大意就是给m个火车的到达时间、停留时间和车载货物的价值,车站有n个车道,而火车停留一次车站就会从车载货物价值中获得1%的利润,让你来求一种安排方法,使得车站收益最大,并输出收益值。
蒟蒻的思路是这样的:
一眼看出:最大费用最大流(MCMF)
显然cost:表示车站收益
然后……
以车站为点建立图求流?同一个车站可能经过好几辆火车……,貌似很麻烦……;
那么以什么建图、连边,还有怎么连?
貌似有点类似于方格取数2之中的拆点……;
那么这个就可以……以火车为点,把一个点拆成两个,然后建立流的关系。
Reach[i]和stay[i]作为建立不同火车是否可以建边的判断条件
假设火车i,将其分为点2*i-1和2*i,连一条流量为1,费用为-cost[i]的边
如果reach[i] + stay[i] < reach[j],在2*i和2*j-1之间连一条流量为1,费用为0的边。
建立汇点和起点S,T,从S向每个2*i-1连一条流量为1,费用为0的边。从每个2*i向T连一条流量为1,费用为0的边。
那么怎么限制n个车道呢?其实很简单,只需要建立超级汇点ST,然后从T向ST连一条流量为n,费用为0的边。
这样这个题目就大功告成了,代码不长,刚98行。建议大家还是去刷一下代码能力题,因为NOIP2015蒟蒻就被代码能力题给坑惨了。
废话不多说,上代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int INF = ;
const int maxe = ;
const int maxn = ;
int n,m,reach[maxn],stay[maxn],cost[maxn],vis[maxn<<],d[maxn<<],h[maxn<<],pre[maxn<<],rid[maxn],cid[maxn],now;
double ans;
struct edge{
int to,cost,cap,next;
}tr[maxe];
inline void init(){
now = ;
memset(h,-,sizeof(h));
memset(tr,,sizeof(tr));
memset(reach,,sizeof(reach));
memset(stay,,sizeof(stay));
memset(cost,,sizeof(cost));
}
inline void add(int u,int v,int cap,int cost){
tr[now].to = v;tr[now].cap = cap;tr[now].cost = cost;tr[now].next = h[u];
h[u] = now++;
tr[now].to = u;tr[now].cap = ;tr[now].cost = -cost;tr[now].next = h[v];
h[v] = now++;
}
bool SPFA(int s,int t,int &flow,int &cost){
for(int i = s;i <= t;++i){
d[i] = INF;
}
int minflow = INF;
memset(vis,,sizeof(vis));
memset(pre,-,sizeof(pre));
deque<int>q;
d[s] = ;
vis[s] = ;
q.push_back(s);
while(!q.empty()){
int x = q.front();q.pop_front();
vis[x] = ;
for(int i = h[x];i != -;i = tr[i].next){
edge e = tr[i];
if(d[e.to] > d[x] + e.cost && e.cap){
d[e.to] = d[x] + e.cost;
pre[e.to] = i;
minflow = min(minflow,e.cap);
if(!vis[e.to]){
vis[e.to] = ;
q.push_back(e.to);
}
}
}
}
if(d[t] == INF)return false;
flow += minflow;
cost += d[t] * minflow;
for(int i = t;i != s;i = tr[pre[i]^].to){
tr[pre[i]].cap -= minflow;
tr[pre[i]^].cap += minflow;
}
return true;
}
int MCMF(int s,int t){
int flow = ,cost = ;
while(SPFA(s,t,flow,cost));
return cost;
}
int main(){
scanf("%d%d",&n,&m);
init();
for(int i = ;i <= m;++i){
scanf("%d%d%d",&reach[i],&cost[i],&stay[i]);
rid[i] = *i;cid[i] = *i-;
add(cid[i],rid[i],,-cost[i]);
}
for(int i = ;i <= m;++i){
for(int j = ;j <= m;++j){
if(j != i)
if(reach[i] + stay[i] < reach[j]){
add(rid[i],cid[j],,);
}
}
}
int S = ,T = *m+,ST = *m+;
for(int i = ;i <= m;++i){
add(S,cid[i],,);
}
for(int i = ;i <= m;++i){
add(rid[i],T,,);
}
add(T,ST,n,);
ans = double(MCMF(S,ST))/;
printf("%0.2lf\n",-ans);
return ;
}
如果大家认为有用的话,欢迎转载。如果大家有意见的话,请在下方评论栏中给我留言,或者给我的E-mail PC-worker@outlook.com发邮件留言。谢谢大家。
习题:codevs 1035 火车停留解题报告的更多相关文章
-
wikioi 1035 火车停留 裸费用流
链接:http://wikioi.com/problem/1035/ 怎么说呢,只能说这个建图很有意思.因为只有m条道,然后能互相接在一起的连通,对每个点进行拆点,很有意思的一道裸费用留题. 代码: ...
-
习题:codevs 2822 爱在心中 解题报告
这次的解题报告是有关tarjan算法的一道思维量比较大的题目(真的是原创文章,希望管理员不要再把文章移出首页). 这道题蒟蒻以前做过,但是今天由于要复习tarjan算法,于是就看到codevs分类强联 ...
-
习题: codevs 2492 上帝造题的七分钟2 解题报告
这道题是受到大犇MagHSK的启发我才得以想出来的,蒟蒻觉得自己的代码跟MagHSK大犇的代码完全比不上,所以这里蒟蒻就套用了MagHSK大犇的代码(大家可以关注下我的博客,友情链接就是大犇MagHS ...
-
习题:codevs 1519 过路费 解题报告
今天拿了这道题目练练手,感觉自己代码能力又增强了不少: 我的思路跟别人可能不一样. 首先我们很容易就能看出,我们需要的边就是最小生成树算法kruskal算法求出来的边,其余的边都可以删掉,于是就有了这 ...
-
[置顶] 刘汝佳《训练指南》动态规划::Beginner (25题)解题报告汇总
本文出自 http://blog.****.net/shuangde800 刘汝佳<算法竞赛入门经典-训练指南>的动态规划部分的习题Beginner 打开 这个专题一共有25题,刷完 ...
-
LeetCode: Sort Colors 解题报告
Sort ColorsGiven an array with n objects colored red, white or blue, sort them so that objects of th ...
-
CH Round #56 - 国庆节欢乐赛解题报告
最近CH上的比赛很多,在此会全部写出解题报告,与大家交流一下解题方法与技巧. T1 魔幻森林 描述 Cortana来到了一片魔幻森林,这片森林可以被视作一个N*M的矩阵,矩阵中的每个位置上都长着一棵树 ...
-
二模13day1解题报告
二模13day1解题报告 T1.发射站(station) N个发射站,每个发射站有高度hi,发射信号强度vi,每个发射站的信号只会被左和右第一个比他高的收到.现在求收到信号最强的发射站. 我用了时间复 ...
-
BZOJ 1051 最受欢迎的牛 解题报告
题目直接摆在这里! 1051: [HAOI2006]受欢迎的牛 Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 4438 Solved: 2353[S ...
随机推荐
-
(转)Android消息处理机制(Handler、Looper、MessageQueue与Message)
转自 http://www.cnblogs.com/angeldevil/p/3340644.html Android消息处理机制(Handler.Looper.MessageQueue与Messag ...
-
C语言绘制余弦函数图象
#include"stdio.h" #include"math.h" void main() { double y; int x,m; for(y=1;y> ...
-
";HTTP 错误 500.19 请求的页面的相关配置数据无效"; 解决办法
HTTP 错误 500.19 - Internal Server Error无法访问请求的页面,因为该页的相关配置数据无效. 问题"详细错误信息模块 IIS Web Core通知 Begin ...
-
设计模式之前奏(UML类图)
原文:设计模式之前奏(UML类图) 本人菜菜一个,最近一直在博客园游走闲逛,看到了各种技术,各种各种…….便看到了大话设计模式这本书,下了电子版的看了看第一章,感觉相当不错,不仅通俗易懂,而且与实际案 ...
-
!function 笔记
一般看JQuery插件里的写法是这样的 (function($) { //... })(jQuery); 今天看到bootstrap的javascript组件是这样写的 !function( $ ){ ...
-
CentOS6.8通过yum安装MySQL5.7
Centos6.8通过yum安装mysql5.7 1.安装mysql的yum源 a.下载配置mysql的yum源的rpm包 根据上面3张图片中的操作下载下来的rpm文件可以通过如下命令获取: wget ...
-
EntityFramework Code-First 简易教程(四)-------继承策略
在前篇CodeFirst类型约定中,我们在数据库中为每一个模型类创建一个表,但是有个问题,我们可以设计出带继承关系的模型类,即面向对象编程既有“has a”(表示类继承)也有“is a”(表示类包含) ...
-
DataInputStream FileInputStream 区别
DataInputStream是数据输入流,读取的是java的基本数据类型. FileInputStream是从文件系统中,读取的单位是字节. FileReader 是从文件中,读取的单位是字符
-
HTML+CSS浏览器兼容性问题
浏览器兼容问题一:不同浏览器的标签默认的外补丁和内补丁不同 问题症状:随便写几个标签,不加样式控制的情况下,各自的margin 和padding差异较大. 碰到频率:100% 解决方案:CSS里 ...
-
JavaScript的进阶之路(六)理解函数
函数:定义一次,多次调用:用于对象的属性则称为对象的方法:在JavaScript中,函数即对象:嵌套的函数形成闭包: 定义函数和简单调用函数: //函数定义 function f1(){ //没有参数 ...