注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1221][HNOI2001] 软件开发  

2014-12-01 19:40:12|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1221: [HNOI2001] 软件开发

BZOJ的source真是神剧透。。
不过看了剧透也想了好长时间
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1000+50;
const int P = N*3;
const int M = P*10;
const int MAX = 1E9+10;
const long long lMAX = 1e18;
int n,m,start,end,large,T;
int P1,P2;
struct Point{
Point(){next = NULL;}
Point *next;int d;
void push(int a){
Point *l = new Point;
l->next = next;next=l;
l->d = a;
}
}point[P];
struct Edge{
int from,to,cap,flow,cost;
Edge(){}
Edge(int f,int t,int c,int fl,int co):from(f),to(t),cap(c),flow(fl),cost(co){}
}edges[M];
void AddEdge(int from, int to, int cap, int cost){
point[from].push(T);
edges[T++] = Edge(from,to,cap,0,cost);
point[to].push(T);
edges[T++] = Edge(to,from,0,0,-cost);
}
typedef long long ll;
int flows[P],fa[P];
ll dis[P];
short v[P];
queue<int>dui;
bool spfa(int &flow,ll &cost){
for(int i=1;i<=large;i++)dis[i] = lMAX;
dis[start] = 0;
v[start] = 1;
flows[start] = MAX;
dui.push(start);
while(!dui.empty()){
int now = dui.front();dui.pop();
for(Point *i=point[now].next;i!=NULL;i=i->next){
Edge &e = edges[i->d];
if(dis[now] + e.cost < dis[e.to] && e.cap > e.flow){
flows[e.to] = min(flows[now],e.cap - e.flow);
dis[e.to] = dis[now] + e.cost;
fa[e.to] = i->d;
if(!v[e.to]){
dui.push(e.to);
v[e.to] = 1;
}
}
}
v[now] = 0;
}
if(dis[end]==lMAX)return 0;
flow += flows[end];
cost += flows[end]*dis[end];
int now = end;
while(now != start){
Edge &e = edges[fa[now]];
e.flow += flows[end];
edges[fa[now]^1].flow -= flows[end];
now = e.from;
}
return 1;
}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,a,b,c;
int cost[3];
n = scan();a = scan();b = scan();
cost[0] = scan();
cost[1] = scan();cost[2] = scan();

//make graph
P1 = n;P2 = n*2;
start = n*3+1;large = end = start + 1;
AddEdge(start,1,MAX,cost[0]);
for(i=1;i<=n;i++){
c = scan();
//edges
if(i>1)AddEdge(i-1,i,MAX,0);
AddEdge(i,P1+i,c,0);
AddEdge(P1+i,end,MAX,0);

AddEdge(start,P2+i,c,0);
if(i+a+1 <= n)AddEdge(P2+i,i+a+1,MAX,cost[1]);
if(i+b+1 <= n)AddEdge(P2+i,i+b+1,MAX,cost[2]);
}
//getans
int flow;ll ans;
flow = ans = 0;
while(spfa(flow,ans));
cout << ans << endl;
return 0;
}

题解:
费用流。
首先模拟过程可以很快得到一个建图:
[容量 ,费用]
S->D1 [MAX ,f ]
Di->Di+1 [MAX ,0 ]
Di->P1i [Ni ,0 ]
P1i->Di+a+1 [MAX ,fa ]
P1i->Di+b+1 [MAX ,fb ]
P1i->T [MAX ,0 ]
Di表示每一天拥有的毛巾,P1i表示每天用完的毛巾
乍一看似乎很正确,但是写完之后会发现是错的,费用永远都是ΣNi*f
为什么呢?
因为从P1i指向Dj的边并没有对增加流量有贡献,所以如果是最大流就一定会忽略这些边。
想办法修正
假设我们的建图是正确的,可以发现正确性基于最大流。
也就是说所有的P1i一定会有Ni的流量经过。
所以可以去掉原来从P1i->Dj的边,加入补偿流:
P2i->Di+a+1 [Ni ,fa ]
P2i->Di+b+1 [Ni ,fb ]
这样一来就对最大流有了贡献,问题至此解决。

另:
这么一来好像P1i就没有意义了?Di似乎可以直接连向汇点。
题目里没有给出Ni的范围,所以我用了longlong,结果异常慢。。
  评论这张
 
阅读(41)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017