隐藏
「bzoj3280」小R的烦恼 - 费用流/餐巾问题 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3280」小R的烦恼 - 费用流/餐巾问题

题目大意

    小R最近遇上了大麻烦,他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他,但是要求小R帮助他一起解决一个难题。
    问题是这样的,程设老师最近要进行一项邪恶的实验来证明$P=NP$,这个实验一共持续$n$天,第$i$天需要$a[i]$个研究生来给他搬砖。研究生毕竟也是人,所以雇佣研究生是需要钱的,机智的程设老师已经联系好了$m$所大学,第$j$所大学共有$l[j]$个研究生,同时雇佣这所大学的一个研究生需要$p[j]$元钱。
    本来程设老师满心欢喜的以为,这样捡最便宜的$\max\lbrace a[i]\rbrace$个研究生雇来,就可以完成实验;结果没想到,由于他要求硕士生们每天工作$25$个小时不许吃饭睡觉上厕所喝水说话咳嗽打喷嚏呼吸空气,因此一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生,毫无疑问,就不能再进行工作了。但是机智的老师早早联系好了$k$家医院,第i家医院医治一个濒死的研究生需要$d[i]$天,并且需要$q[i]$元钱。
    现在,程设老师想要知道,最少花多少钱,能够在这$n$天中满足每天的需要呢?若无法满足,则请输出impossible。注意,由于程设老师良心大大的坏,所以他是可以不把濒死的研究生送去医院的!


题目分析

lzz打的标签是线性规划,但这道题如果写出线性规划来不等式很多,难以写完,且单纯形空间有点不可接受,因此还是用费用流做吧。

和网络流24题之餐巾问题类似。

我们可以将每一天拆成两个点,分别表示每一天的开始和结束。

从源点$S$连接$m$条边到第$1$天的开始结点,表示这$m$个学校的学生。
从每一天$i$的开始结点连一条边到汇点$T$,容量为$a[i]$,费用为$0$,表示每天需要的流量。
从源点$S$连向每天$i$的结束结点,容量为$a[i]$,费用为$0$,表示每天处于濒死状态的学生。
从每天的结束结点$x’$连向后$d+1$天的开始结点,容量为$inf$,费用为$q$,表示去医院救学生。
从每天的开始结点向后一天的开始结点连一条容量为$inf$,费用为$0$的边,表示前一天没用到的学生留在后一天用。

为什么要这样建模呢?每次开始结点$x$直接连向$T$,又从$S$连容量相同的边到结束结点$x’$,是为了方便判断是否有解(汇点总流量=需要人数之和),如果不判断是否有解可以直接将开始结点$x$连向结束结点$x’$,然后仅在最后一天的结束结点连向$t$。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=105;

struct Edge {
int from,to,cap,flow,cost;
Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

struct zkw_CostFlow {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn],vst[maxn];
int dist[maxn],path[maxn];
int flow,cost;
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v,int f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool spfa() {
for(int i=1; i<=n; i++)dist[i]=INT_MAX;
memset(inque,0,sizeof(inque));
dist[t]=0;
inque[t]=1;
deque<int>Q;
Q.push_back(t);
while(!Q.empty()) {
int Now=Q.front();
Q.pop_front();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(dist[Next]>dist[Now]+e.cost&&e.cap>e.flow) {
dist[Next]=dist[Now]+e.cost;
if(!inque[Next]) {
inque[Next]=1;
if(!Q.empty()&&dist[Next]<dist[Q.front()])Q.push_front(Next);
else Q.push_back(Next);
}
}
}
}
return dist[s]<INT_MAX;
}
int dfs(int Now,int a) {
if(vst[Now])return 0;
if(Now==t||a==0)return a;
int flow=0;
vst[Now]=1;
for(int id:G[Now]) {
Edge& e=edges[id];
int Next=e.to;
if(dist[Now]-e.cost!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
cost+=nextflow*e.cost;
e.flow+=nextflow;
edges[id^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
flow=cost=0;
while(spfa()) {
memset(vst,0,sizeof(vst));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} zkw;

int T,n,m,k,sum=0;

int main() {
T=Get_Int();
for(int t=1; t<=T; t++) {
n=Get_Int();
m=Get_Int();
k=Get_Int();
sum=0;
int S=2*n+1,T=2*n+2;
zkw.init(T);
for(int i=1; i<=n; i++) {
int v=Get_Int();
sum+=v;
zkw.AddEdge(S,n+i,v,0);
zkw.AddEdge(i,T,v,0);
if(i<n)zkw.AddEdge(i,i+1,INT_MAX,0);
}
for(int i=1; i<=m; i++) {
int v=Get_Int(),f=Get_Int();
zkw.AddEdge(S,1,v,f);
}
for(int i=1; i<=k; i++) {
int d=Get_Int(),f=Get_Int();
for(int j=1; j+d+1<=n; j++)zkw.AddEdge(n+j,j+d+1,INT_MAX,f);
}
int flow=zkw.maxflow(S,T);
if(flow!=sum)printf("Case %d: impossible\n",t);
else printf("Case %d: %d\n",t,zkw.cost);
}
return 0;
}
姥爷们赏瓶冰阔落吧~