# 33 条题解

• @ 2017-07-13 17:19:47
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,a,b,cn,ca,cb;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
f.resize(0);
f.resize(cw.size(),0);
f[s]=oo_max;
e.resize(0);
e.resize(cw.size(),-1);
u.resize(0);
u.resize(cw.size(),oo_max);
u[s]=0;
pre.resize(0);
pre.resize(cw.size(),-1);
pre[s]=s;
vis.resize(0);
vis.resize(cw.size(),0);
for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
{
int now=q.front();
for (int i=0;i<cw[now].size();i++)
if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
(*flow)=f[t];
(*cost)=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
int temp_flow,temp_cost;
while (bfs_1(s,t,&temp_flow,&temp_cost))
{
for (int i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
(*flow)+=temp_flow;
(*cost)+=(temp_flow*temp_cost);
}
}

int main()
{
while (~scanf("%d%d%d%d%d%d",&n,&a,&b,&cn,&ca,&cb))
{
cw.resize(0);
cw.resize(2*n+2);
ce.resize(0);
ce.resize(cw.size());
c.resize(0);
c.resize(cw.size());
p.resize(0);
p.resize(cw.size());
for (int i=0;i<cw.size();i++)
{
cw[i].resize(0);
ce[i].resize(0);
c[i].resize(0);
p[i].resize(0);
}
for (int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
if (i+1<=n)
if (i+a+1<=n)
if (i+b+1<=n)
}
int ans_flow=0,ans_cost=0;
min_cost_max_flow_1(0,cw.size()-1,&ans_flow,&ans_cost);
printf("%d\n",ans_cost);
}
}
``````
• @ 2017-07-13 17:20:16

很H2O的題

• @ 2009-09-18 17:40:01

额...奇怪了...

(1) s-> (1,2,...n)连一条容量为inf，费用为f的边;

(2) s->1 连一条容量为inf，费用为f的边，在连i->i+1容量为inf，费用为0的边.

这2种建图有区别吗?不明白...(1)WA,(2)Ac

• @ 2009-07-08 10:21:06

最小费用最大流:

设有顶点S,T,每天有顶点 G[i], 附加每天的往外供应的顶点 U[i]

S->G[1],容量INF,费用 f

G[i]->G,容量INF,费用0

G[i]->T,容量为当天需求量,费用0

S->U[i],容量为当天需求量,费用0

U[i]->G,容量INF,费用fa

U[i]->G,容量INF,费用fb

• @ 2017-01-04 00:03:53

测试数据 #0: Accepted, time = 0 ms, mem = 588 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 584 KiB, score = 20
测试数据 #2: Accepted, time = 0 ms, mem = 676 KiB, score = 20
测试数据 #3: Accepted, time = 0 ms, mem = 676 KiB, score = 20
测试数据 #4: Accepted, time = 15 ms, mem = 672 KiB, score = 20
Accepted, time = 15 ms, mem = 676 KiB, score = 100
代码

第一次只有40分。。看题解才知道和原题不一样，这个构图上有一点点区别。。
原题是需要a天洗完时，第i+a天就能用，但这个是i+a+1天，没差多少。。
构图是用二分图感觉好理解一点。。还是感觉有点不能理解为什么可以这么去想，还是要加油

``````#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define Mem(a,b) memset((a),(b),sizeof((a)))
#define Sy system("pause")
const int maxn = 1100;
const int INF = 0x3f3f3f;
using namespace std;

struct MCMF{

struct Edge
{
int from, to, cap, flow, cost;
Edge(int a, int b, int c, int d, int e) :from(a), to(b), cap(c), flow(d), cost(e) {}
Edge(){}
};
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn], d[maxn], p[maxn], a[maxn];

void init(int n){
this->n = n;
for (int i = 0; i < n; i += 1)G[i].clear(); edges.clear();
}

void AddEdge(int from, int to, int cap, int cost){
edges.push_back(Edge(from, to, cap, 0, cost));
edges.push_back(Edge(to, from, 0, 0, -cost));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}

bool BellmanFord(int s, int t, int & flow,int & cost){
for (int i = 0; i < n; i += 1) d[i] = INF;
memset(inq, 0, sizeof(inq));
d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;
queue<int> Q;
Q.push(s);
while (!Q.empty())
{
int u = Q.front(); Q.pop();
inq[u] = 0;
for (int i = 0; i < G[u].size(); i += 1){
Edge & e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost){
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if (!inq[e.to]){
Q.push(e.to); inq[e.to] = 1;
}
}
}
}
if (d[t] == INF) return false;
flow += a[t];
cost += d[t] * a[t];

for (int u = t; u != s; u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u] ^ 1].flow -= a[t];
}
return true;
}

int MinCostMaxFlow(int s, int t, int & cost){
int flow = 0; cost = 0;
while (BellmanFord(s, t, flow, cost));
return flow;
}
};

/*

S: 0  DLi:[1,n]  DRi:[n+1,2n] T:2n+1

*/

int main(){
int n, a, b, f, fa, fb,tmp;
scanf("%d %d %d %d %d %d", &n, &a, &b, &f, &fa, &fb);
int S = 0, T = 2 * n + 1;
MCMF D; D.init(2 * n + 2);
for (int i = 1; i <= n; i += 1){
scanf("%d", &tmp);
D.AddEdge(i + n, T, tmp, 0);
D.AddEdge(S, i + n, INF, f);
if (i + 1 <= n) D.AddEdge(i, i + 1, INF, 0);
if (i + a + 1<= n) D.AddEdge(i, i + n + a + 1, INF, fa);
if (i + b + 1 <= n) D.AddEdge(i, i + n + b + 1, INF, fb);
}
int ans;
D.MinCostMaxFlow(S, T, ans);
printf("%d\n", ans);

//Sy;
return 0;
}
``````
• @ 2013-12-14 10:58:55

厉害

• @ 2013-08-23 19:03:24

直接拿BZOJ超时的代码过来，居然还A了。。。。
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 504 KiB, score = 20
测试数据 #1: Accepted, time = 0 ms, mem = 492 KiB, score = 20
测试数据 #2: Accepted, time = 31 ms, mem = 1376 KiB, score = 20
测试数据 #3: Accepted, time = 31 ms, mem = 1412 KiB, score = 20
测试数据 #4: Accepted, time = 46 ms, mem = 1176 KiB, score = 20
Accepted, time = 108 ms, mem = 1412 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

#define MAXN 2010

struct node {
node *next,*other;
int t,f,c;
};

int n,a,b,fa,fb,f;

void INSERT(int s,int t,int f,int c){
node *p=new(node);
(*p).t=t;
(*p).f=f;
(*p).c=c;
}

int S,T;

int minc[MAXN],minf[MAXN],su[MAXN];
bool flag[MAXN];
node* d[MAXN];

struct cmp{
bool operator()(int x,int y){
return minc[x]>minc[y];
}
};

priority_queue<int,vector<int>,cmp>q;
/*
void OUT(){
for (int i=0;i++<T;){
printf("%d:\n",i);
while (p!=NULL){
// if ((*p).f){
printf("%d %d %d\n",(*p).t,(*p).f,(*p).c);
// }
p=(*p).next;
}
printf("\n\n");
}
}
*/
int main(){
scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
S=n*2+1;
T=S+1;
for (int i=0;i++<2*n+2;){
}
for (int i=0;i++<n;){
int x;
scanf("%d",&x);
INSERT(S,i,x,f);
INSERT(i,S,0,-f);
INSERT(S,n+i,x,0);
INSERT(n+i,S,0,0);
INSERT(i,T,x,0);
INSERT(T,i,0,0);
}
for (int i=0;i++<n;){
for (int j=i+a+1;j<=n;j++){
INSERT(n+i,j,0x7fffffff,fa);
INSERT(j,n+i,0,-fa);
}
for (int j=i+b+1;j<=n;j++){
INSERT(n+i,j,0x7fffffff,fb);
INSERT(j,n+i,0,-fb);
}
}
// OUT();
int min_cost=0;
while (1){
for (int i=0;i++<T;){
minc[i]=0x7fffffff;
}
minc[S]=su[S]=0;
minf[S]=0x7fffffff;
memset(flag,true,sizeof(flag));
while (!q.empty()){
q.pop();
}
q.push(S);
while (!q.empty()){
int v=q.top();
q.pop();
if (!flag[v]){
continue;
}
flag[v]=false;
if (v==T){
break;
}
while (p!=NULL){
if ((*p).f&&minc[(*p).t]>(minc[v]+(*p).c)){
minc[(*p).t]=minc[v]+(*p).c;
q.push((*p).t);
flag[(*p).t]=true;
minf[(*p).t]=min(minf[v],(*p).f);
su[(*p).t]=v;
d[(*p).t]=p;
}
p=(*p).next;
}
}
if (minc[T]==0x7fffffff){
break;
}
int i=T;
// printf("!!!%d",T);
while (su[i]){
// printf("-%d(%d)",su[i],((*d[i]).c*minf[T]));
(d[i]).f-=minf[T];
(
(*d[i]).other).f+=minf[T];
min_cost+=((*d[i]).c*minf[T]);
i=su[i];
}
// printf("\n\n");
// max_flow+=minf[T];
}
printf("%d\n",min_cost);
// OUT();
return 0;
}

• @ 2010-07-08 20:11:14

傻傻的问一句：为什么叫“餐巾纸引发的血案”啊…………明明就是餐巾计划问题改版嘛。。。

是不是起得恐怖一点容易吸引人眼球啊。。。出题人有点不择手段啊……

• @ 2010-04-05 22:01:02

这个...

我用的拆点，spfa最小费用流，(m:边数（包括反向边），n:点数)

第一次 40分...n=210,m=300*2;

最后三个错误号255-RE...

第二次 40分...n=210,m=500*2;

第三个TLE 最后两个RE-255...

第三次 AC...来了个暴力点的：

n=210,m=200*200*2;

为啥m=500*2就不行呢...*2是反向边...

建图：第i天需要a[i]个

S向点i连flow=a[i],cost=0; 表示第I天结束；

i+n向T连flow=a[i],cost=0; 表示第i天刚刚开始；

S向i+n连flow=INF,cost=f;(买的价钱) 表示第i天买花费；

i向i+n+a连flow=INF,cost=fa; 表示a消毒...

i向i+n+b连flow=INF,cost=fa; 表示b消毒...

求最小割最大流...

这样需要m=500*2为啥不够呢...

• @ 2010-03-08 21:26:15

晕，一开始当成餐巾问题，直接交，40分，后来发现了一个细微的差别：

餐巾问题第i天用完的餐巾洗了之后，如果洗餐巾花k天，那么第i+k天就可以用

…………

但这题，第i天用完之后开始洗，第i+k+1天才可以用，直接导致构图上的差别…………

之后费用流就行了 o(╯□╰)o

• @ 2010-02-28 20:11:15

此题的fa，fb小心

• @ 2009-11-06 21:09:49

贪心

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

• @ 2009-09-07 14:55:49

赞cgy4ever。

其实也可以S向每个i连一条边，容量Inf，费用f。

当然那个方法更好，只向1连一条边。

• @ 2009-08-22 17:18:40

大家注意了

本题和原题建图有点不一样!!!

• @ 2009-08-20 09:39:49

标题党...

• @ 2009-08-19 19:20:09

数据弱了，如果上下界的方法不优化在原题是TLE一个点的。

还是用cgy4ever神牛的方法比较快.

• @ 2009-08-02 21:07:19

听某神牛说过,此题贪心足矣.

我...

• @ 2009-08-02 17:16:21

cgy4ever建的模型非常经典！

数据规模小，直接spfa增广就可以解决了。

• @ 2009-07-25 15:50:37

弱弱的问下 我建模的时候采用每一天都可以买毛巾怎么是错的。。。

即S->i都连一条容量为无穷 费用为f的便。。

不知道这种和S->1有什么区别。。

• @ 2009-07-24 09:29:51

佩服cgy4ever大牛！！！！

一般建图是要求上下界的费用流的,一开始多次一举求了最大流

• @ 2009-07-17 16:34:45

典型的最小费用最大流问题 …… 尤其是图是一个二分图 = =||

建图为 ：

procedure addarc (u , v , c , w : longint) ;

begin

// writeln (u,' - > ',v,' : ',c,' : ',w) ;

inc (tot) ; arc[tot].d := v ; arc[tot].c := c ; arc[tot].w := w ;

arc[tot].next := vr ; vr := tot ;

inc (tot) ; arc[tot].d := u ; arc[tot].c := 0 ; arc[tot].w := -w ;

arc[tot].next := vr[v] ; vr[v] := tot ;

end ;

procedure solve ;

var i , c , n , New_cost , Q_time , Q_cost , S_time , S_cost

: longint ;

begin

fillchar (vr , sizeof (vr) , \$ff) ; tot := -1 ;

// readln (n , New_cost , Q_time , Q_cost , S_time , S_cost) ;

readln (n , Q_time , S_time , New_cost , Q_cost , S_cost) ;

s := n + n + 1 ; t := s + 1 ; z := t ;

for i := 1 to n do begin

addarc (s , i , c , 0) ;

addarc (n + i , t , c , 0) ;

addarc (s , n + i , oo , New_cost) ;

if (i + Q_time

ID
1552

5

(无)

301

105

35%

1