BZOJ1061 [Noi2008]志愿者招募

题面

​ 题意还是比较简单明了的:http://www.lydsy.com/JudgeOnline/problem.php?id=1061

题解

​ 网上有人评价这题是:费用流神题,单纯性裸题。

​ 然而我并不知道什么是线性规划。

​ 有一种做法大概是这样的:(先假设有解)

​ 对于每一种类型志愿者的人数我们设为X[i]X[i]

​ 那么对于每一天,设可以涵盖这一天的志愿者类型分别是f[i][1]f[i][1],f[i][2]f[i][2]……

​ 那么我们要满足对于所有\sum_{i=1}^{f[i]存在} X[f[i]] >= A[i]

​ 不妨假设总是存在一个y[i]y[i],满足y[i]>=0y[i]>=0,并且

​ \sum_{j=1}^{f[i][j]存在} X[f[i][j]] -y[i] = A[i]

​ 作差分(A[0]=A[n+1]=0)

​ 得到了下面的式子:

\sum_{j=1}^{f[i][j]存在} X[f[i][j]]-\sum_{j=1}^{f[i-1][j]存在} X[f[i-1][j]] -y[i] + y[i-1] - A[i] + A[i-1] = 0

​ 然后抵消后每一个X[i]X[i]必然只会加一次,减一次。

hint:流量平衡

​ 设每一天(或者说每一个等式)为节点,增加源点S和汇点T。

  • 如果A[i]A[i1]A[i]-A[i-1]小于0,那么S到ii连一条容量为(A[i]-A[i-1]),费用为0的边,否则iiTT连一条 容量为(A[i-1]-A[i]),费用为0的边

  • 如果一个变量X[i]在第j个等式中出现为X[i],在第k个等式中出现为-X[i],从顶点j向顶点k连接一条容量为∞,权值为V[i]的有向边。

  • 如果一个变量Y[i]在第j个等式中出现为Y[i],在第k个等式中出现为-Y[i],从顶点j向顶点k连接一条容量为∞,权值为0的有向边。

然后跑最小费用最大流。因为流量平衡,并且y[i]>=0,所以有解即可。

参考,from network1

​  网上还有别的做法,貌似很好理解

from network2

难看的Code

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
//Hello Wolrd
//There is Special Pig Jiong in the world.
#include<cstdio>
#include<ctype.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f,oo = inf;
#define pc putchar
#define RG register
char __wzp[1<<15|1],*__S=__wzp+32768;
#define gc() (__S>=__wzp+32768?(__wzp[fread(__wzp,sizeof(char),1<<15,stdin)]=EOF),*((__S=__wzp)++):*(__S++))
inline ll read(){
RG ll x=0,f=1;RG char c=gc();
for(;!isdigit(c);c=gc())if(c=='-')f=-1;
for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
#define mem(x,v) memset(x,v,sizeof(x))
#define rep(i,a,b) for(RG int i=(a);i<(b);++i)
#define N 2005
#define M 50005
struct Edge{
int to,nxt,cap,cost;
Edge(){}
Edge(int to,int nxt,int cap,int cost):to(to),nxt(nxt),cap(cap),cost(cost){}
}edge[2*M];
int first[N],nume,n,m;
void Addedge(int a,int b,int cap,int cost){
edge[nume] = Edge(b,first[a],cap,cost);first[a] = nume++;
edge[nume] = Edge(a,first[b],0,-cost);first[b] = nume++;
}
int dis[N],vis[N],pre[N];
int S,T,a[N];
bool spfa(){
queue<int> q;
mem(dis,0x3f);
mem(vis,false);
mem(pre,-1);
dis[S]=0;
vis[S]=true;
q.push(S);
while(!q.empty()){
int u = q.front();q.pop();
vis[u] = false;
for (int e=first[u];~e;e=edge[e].nxt){
int v = edge[e].to;
if(edge[e].cap&&dis[v]>dis[u]+edge[e].cost){
dis[v]=dis[u]+edge[e].cost;
pre[v] = e;
if(!vis[v]){
q.push(v);
vis[v]=true;
}
}
}
}
return dis[T]!=inf;
}
int mcmf(){
int minflow,maxflow=0,mincost=0;
while(spfa()){
minflow = inf;
for(int i=pre[T];~i;i=pre[edge[i^1].to])
minflow = min(minflow,edge[i].cap);
for(int i=pre[T];~i;i=pre[edge[i^1].to])
edge[i].cap -= minflow,
edge[i^1].cap += minflow;
mincost += minflow * dis[T];
maxflow += minflow;
}
return mincost;
}
int main(){
mem(first,-1);nume = 0;
n = read(),m = read();
S = n + 2;T = S + 1;
for(int i=1;i<=n;i++) a[i] = read();
for(int i=1;i<=m;i++){
int s = read(),t = read(),c = read();
Addedge(s,t+1,inf,c);
}
a[0]=a[n+1]=0;
for(int i=1;i<=n+1;i++){
if(a[i]-a[i-1]>=0)
Addedge(S,i,a[i]-a[i-1],0);
else
Addedge(i,T,a[i-1]-a[i],0);
}
for(int i=1;i<=n;i++) Addedge(i+1,i,inf,0);
printf("%d\n",mcmf());
return 0;
}
文章目录
  1. 1. 题面
  2. 2. 题解