洛谷P3980 [NOI2008]志愿者招募——费用流
题目介绍题目描述输入格式输出格式测试样例
题解代码
题目介绍
题目描述
链接: 传送门. 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要 n 天才能完成，其中第 i 天至少需要 ai 个人。布布通过了解得知，一共有 m 类志愿者可以招募。其中第 i类可以从第 si天工作到第 ti天，招募费用是每人 ci元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
输入格式
第一行包含两个整数 n,m，表示完成项目的天数和可以招募的志愿者的种类。接下来的一行中包含 n 个非负整数，表示每天至少需要的志愿者人数。 接下来的 m行中每行包含三个整数 si,ti,ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。 1≤n≤1000，1≤m≤10000，题目中其他所涉及的数据均不超过 2^31−1。
输出格式
仅包含一个整数，表示你所设计的最优方案的总费用。
测试样例
输入 #1 3 3 2 3 4 1 2 2 2 3 5 3 3 2
输出#1 14
题解
参考链接: dalao博客. 看起来感觉是最小费用流，但不知如何建网络。参考了大佬们的题解也只能是理解了这种建网络方式，还是要多做题。 先建网络如下，再解释：
对第i天需要的志愿者数量为ai,在第i天和第i+1天连边，容量INF-ai,费用0；对第i种志愿者(si,ti,ci)，在si和ti+1间连边，容量INF，费用ci；最后超级源点对第1天连边、第N+1天对超级汇点连边，容量都INF，费用都为0.
以上第3步，使得最终流经全网络的网络流流量为INF。对于第i天和第i+1天，为了令其间所有边(包括连接i和i+1边、以及跨过的边)总容量也为INF，则必然先流经直接连接的费用为0的边(对费用无贡献)，对于不足的容量a[i] 则通过志愿者流过，即流经第2步所建边。
该建网络方式具有特点：以时间顺序流经网络，体现将志愿者的工作覆盖范围。因此从源点向汇点跑一遍最小费用最大流即可。
代码
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std
;
typedef long long ll
;
const int maxn
=1010;
const ll INF
=0x3f3f3f3f3f3f3f3f;
const int inf
=0x3f;
class Edge{
public:
ll to
,cap
,cost
,nxt
,rev
;
};
int head
[maxn
];
Edge edge
[maxn
<<5];
int cnt
=1;
int N
,M
,a
,S
,T
;
void add(ll u
,ll v
, ll cap
, ll cost
){
edge
[cnt
].to
=v
;edge
[cnt
].cap
=cap
;edge
[cnt
].cost
=cost
;edge
[cnt
].nxt
=head
[u
];edge
[cnt
].rev
=cnt
+1; head
[u
]=cnt
++;
edge
[cnt
].to
=u
;edge
[cnt
].cap
=0; edge
[cnt
].cost
=-cost
;edge
[cnt
].nxt
=head
[v
];edge
[cnt
].rev
=cnt
-1; head
[v
]=cnt
++;
}
bool vis
[maxn
<<1];
int pre
[maxn
<<1],preEdge
[maxn
<<1];
ll dis
[maxn
<<1];
ll flow
[maxn
<<1];
ll h
[maxn
<<1];
bool Dkjistra(int S
, int T
){
memset(vis
,false,sizeof(vis
));
memset(dis
, inf
, sizeof(dis
));
memset(flow
, inf
, sizeof(flow
));
priority_queue
<pair
<int, int> > que
;
dis
[S
] = 0;
que
.push(make_pair(-dis
[S
], S
) );
while(!que
.empty() ){
int u
= que
.top().second
; que
.pop();
if(vis
[u
]) continue;
vis
[u
] = true;
for(int i
=head
[u
]; i
; i
=edge
[i
].nxt
){
Edge
&e
= edge
[i
];
if(vis
[e
.to
]) continue;
if(e
.cap
>0 && dis
[e
.to
] > dis
[u
] + e
.cost
+ h
[u
] - h
[e
.to
]){
dis
[e
.to
] = dis
[u
] + e
.cost
+ h
[u
] - h
[e
.to
];
pre
[e
.to
] = u
;
preEdge
[e
.to
] = i
;
flow
[e
.to
] = min(flow
[u
], e
.cap
);
que
.push(make_pair(-dis
[e
.to
], e
.to
));
}
}
}
for(int i
=1;i
<=T
;i
++) h
[i
] += dis
[i
];
return dis
[T
] != INF
;
}
void MCMF(){
ll maxflow
= 0;
ll mincost
= 0;
while(Dkjistra(S
, T
)){
maxflow
+= flow
[T
];
mincost
+= flow
[T
] * h
[T
];
int now
= T
;
while(now
!=S
){
Edge
&e
= edge
[preEdge
[now
]];
e
.cap
-= flow
[T
];
edge
[e
.rev
].cap
+= flow
[T
];
now
= pre
[now
];
}
}
printf("%lld\n",mincost
);
}
int main(){
scanf("%d%d",&N
,&M
);
S
=N
+2;T
=N
+3;
for(int i
=1;i
<=N
;i
++){
scanf("%d",&a
);
add(i
,i
+1,INF
-a
,0);
}
add(S
,1,INF
,0);add(N
+1,T
,INF
,0);
int s
,t
;
for(int i
=1;i
<=M
;i
++){
scanf("%d%d%d",&s
,&t
,&a
);
add(s
,t
+1,INF
,a
);
}
MCMF();
}
最后： 多做题、多思考建网络方式
