[BZOJ 1061][NOI2008]志愿者招募
膜了一发BYVoid的题解……竟然搞懂了
这首先是个非常简单的线性规划，就是有若干限制（每天要求的志愿者），形如：
\[P_i = X_a + X_b +\ldots + X_c\geq A_i\]
（这里用\(X_i\)表示第\(i\)类志愿者雇佣了多少个，\(P_i\)表示第\(i\)天的志愿者总数，\(A_i\)同原题面）
且最小化总费用。
既然我们我知道\(P_i\geq A_i\)，那么说明\(P_i\)一定可以表示为\(A_i + Y_i\)（\(Y_i\geq 0\)）。然后这样限制就变成了：
\[P_i = X_a + X_b +\ldots + X_c + Y_i = A_i\]
这个长得很像可以流量平衡的样子，但是流量的变动是表示不了的……
然后假设\(P_0 = 0\)且\(P_{n + 1} = 0\)，这样就可以对限制差分一下，我们就有了\(n + 1\)个限制，然后这个式子就可以流量平衡做了（因为不考虑常数项的话，同一变量只可能在两个限制中出现，并且一正一负，这样就可以通过一个限制送给另一个限制流量来表示了。至于常数项，通过源或者汇连边即可表达）。
然后由于志愿者无限，所以这个东西也一定有解……
我局的我这么渣各位看官看懂的可能性基本上是零……还是推荐BYVoid神犇的题解，比我透彻多了。
代码：
/**************************************************************
Problem: 1061
User: danihao123
Language: C++
Result: Accepted
Time:3164 ms
Memory:6824 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
typedef long long ll;
int m, n;
const int maxno = 100005;
const int maxe = 100005;
int first[maxno];
int next[maxe], from[maxe], to[maxe]; ll flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, ll f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
int ins_edge(int u, int v, ll f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %lld, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
return gcnt - 1;
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
int tot;
bool spfa(int s, int t, ll &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static ll a[maxno]; static int p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0LL);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = LINF;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0LL) return false;
f += a[t];
c += a[t] * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, ll &f, ll &c) {
while(spfa(s, t, f, c));
}
const int maxn = 1005, maxm = 10005;
int E[maxn];
int A[maxn], D[maxn];
int main() {
scanf("%d%d", &n, &m);
int s = 0, t = n + 2; tot = n + 2;
for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
for(int i = 1; i <= n + 1; i ++) {
D[i] = A[i] - A[i - 1];
if(D[i] >= 0) {
E[i] = ins_edge(s, i, D[i]);
} else {
E[i] = ins_edge(i, t, -D[i]);
}
}
for(int i = 1; i <= n; i ++) {
ins_edge(i + 1, i, LINF);
}
while(m --) {
int S, T, C; scanf("%d%d%d", &S, &T, &C);
ins_edge(S, T + 1, LINF, C);
}
ll f = 0, c = 0; mcmf(s, t, f, c);
printf("%lld\n", c);
return 0;
}
[BZOJ 3171][TJOI2013]循环格
流量平衡入门中……
我竟然想民白了……
这个题就是要求每个点在且仅在一个环中，这样每个点的入、出度都是1。出度肯定是1，接下来我们想想怎么保证入度为1。
我们建两排点（也可以说是拆点？），一排表示流出，一排表示接受。然后流出点向相邻的接收点连边，费用的话考虑是否和原来这一格的方向不一样就行了。
这个不需要判断是否满流啥的……因为一定有解（比如说每个行构成一个环啥的）。
代码：
/**************************************************************
Problem: 3171
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:13844 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 20;
typedef long long ll;
char S[maxn][maxn];
int tot = 0; int num[maxn][maxn][2];
int R, C;
char D[4] = {'L', 'R', 'U', 'D'};
int tow(int i, int j, char dir, int flag) {
int dx = 0, dy = 0;
if(dir == 'L') {
dx = -1;
} else if(dir == 'R') {
dx = 1;
} else if(dir == 'U') {
dy = -1;
} else if(dir == 'D') {
dy = 1;
}
int nx = (i + dy + R) % R;
int ny = (j + dx + C) % C;
return num[nx][ny][flag];
}
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
int main() {
tot = 1; int s = 0, t = 1;
scanf("%d%d", &R, &C);
for(int i = 0; i < R; i ++) {
scanf("%s", S[i]);
for(int j = 0; j < C; j ++) {
num[i][j][0] = ++ tot;
num[i][j][1] = ++ tot;
}
}
for(int i = 0; i < R; i ++) {
for(int j = 0; j < C; j ++) {
ins_edge(s, num[i][j][0], 1);
ins_edge(num[i][j][1], t, 1);
for(int it = 0; it < 4; it ++) {
int u = num[i][j][0];
int v = tow(i, j, D[it], 1);
ins_edge(u, v, 1, (D[it] == S[i][j]) ? 0LL : 1LL);
}
}
}
int f = 0; ll c = 0;
mcmf(s, t, f, c);
printf("%lld\n", c);
return 0;
}
[BZOJ 1070][SCOI2007]修车
啊啊啊我为什么要去颓费用流啊……
这个题可以保证每个人的车最后都会被修，所以说也就是让你最小化总等待时间辣！
直接考虑给一个技术人员建时间轴是麻烦而不可取的。我们考虑一点，对于每一个技术人员，若总共修了\(t\)辆车，那么第\(i\)个来找他修车的人会影响后面人的等待时间，换言之我们可以认为第\(i\)个来修车的人给答案做出了\(c\cdot (t - i + 1)\)（这里用\(c\)表示他自己的修车时间，注意他也会影响他自己）的贡献，似乎可以苟最小费用最大流呢。
但问题在于我们并不能提前知道\(t\)是多少，并且这样的话费用不是递增的，一个人可能会优先考虑到后面的位置去修车。那么我们考虑倒过来，去考虑倒数第\(i\)个来修车的人的贡献，显然这个贡献是\(c\cdot i\)。然后接下来就肥肠简单了，，，
代码：
/**************************************************************
Problem: 1070
User: danihao123
Language: C++
Result: Accepted
Time:576 ms
Memory:13928 kb
****************************************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
#include <cassert>
typedef long long ll;
int m, n;
const int maxno = 100005;
const int maxe = 400005;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c = 0LL) {
#ifdef LOCAL
printf("Inserting Edge (%d, %d, %d, %lld)\n", u, v, f, c);
#endif
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
int tot;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + tot + 1, LINF);
std::fill(inq, inq + tot + 1, false);
std::fill(a, a + tot + 1, 0);
std::fill(p, p + tot + 1, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
int pos[105][105][2];
int main() {
scanf("%d%d", &m, &n);
int s = 0, t = 1; tot = 1;
for(int i = 1; i <= n; i ++) {
ins_edge(s, ++ tot, 1);
}
for(int i = 1; i <= m; i ++) {
for(int j = 1; j <= n; j ++) {
pos[i][j][0] = ++ tot;
pos[i][j][1] = ++ tot;
ins_edge(tot - 1, tot, 1);
ins_edge(tot, t, 1);
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
int T; scanf("%d", &T);
for(int k = 1; k <= n; k ++) {
int id = pos[j][k][0]; int id2 = pos[j][k][1];
ins_edge(i + 1, id, 1, k * T);
}
}
}
int f = 0; ll c = 0;
mcmf(s, t, f, c);
#ifdef LOCAL
printf("%d\n", f);
#endif
printf("%.2lf\n", (double(c)) / (double(n)));
return 0;
}
[BZOJ 1449][JSOI2009]球队收益
二次函数费用流的入门题……我真太弱了……
可以给比赛、队伍都建点，然后\(S\)向每个比赛连容量为1的边，每个比赛向队伍连容量为\(1\)的边，来表示赢家是谁。这样一来一次比赛只有一个队伍赢了。
考虑怎么处理那个二次函数费用。费用函数为\(f(x, y) = C x^2 + D y^2\)，由于一个队伍的总比赛次数是已知的，所以\(y\)不需要，不妨假设一个队伍有\(t\)场比赛，则费用函数为\(f(x) = C x^2 + D(t - x)^2\)。
对这个函数做差分：\(\Delta f(x) = f(x + 1) - f(x) = 2Cx - 2D(t - x) + C + D\)，然后这个差分是单调不降的。因此我们对所有差分都从队伍向\(T\)连边（费用为这一点的差分），这样一来的话会优先选择费用小的边，保证这个队伍的费用一直合法。
代码：
/**************************************************************
Problem: 1449
User: danihao123
Language: C++
Result: Accepted
Time:732 ms
Memory:1448 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
typedef long long ll;
const int maxn = 5005;
const int maxm = 1005;
const int maxno = maxn + maxm + 5;
const int maxe = (1000 * 2 + 1000 * 3) * 2 + 50;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c) {
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
int n, m;
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + n + m + 2, LINF);
std::fill(inq, inq + n + m + 2, false);
std::fill(a, a + n + m + 2, 0);
std::fill(p, p + n + m + 2, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
ll win[maxn], lose[maxn], C[maxn], D[maxn];
ll tot[maxn];
int main() {
scanf("%d%d", &n, &m);
ll ans = 0;
for(int i = 1; i <= n; i ++) {
scanf("%lld%lld%lld%lld", &win[i], &lose[i], &C[i], &D[i]);
tot[i] = win[i] + lose[i];
}
int s = 0, t = n + m + 1;
for(int i = 1; i <= m; i ++) {
int a, b; scanf("%d%d", &a, &b);
ins_edge(0, i + n, 1, 0);
ins_edge(i + n, a, 1, 0);
ins_edge(i + n, b, 1, 0);
tot[a] ++; tot[b] ++;
}
for(int i = 1; i <= n; i ++) {
ans += C[i] * win[i] * win[i] + D[i] * (tot[i] - win[i]) * (tot[i] - win[i]);
for(ll j = win[i]; j <= (tot[i] - lose[i] - 1LL); j ++) {
ins_edge(i, t, 1, 2LL * C[i] * j - 2LL * D[i] * (tot[i] - j) + C[i] + D[i]);
}
}
int f = 0; mcmf(s, t, f, ans);
printf("%lld\n", ans);
return 0;
}
[COGS 741]负载平衡
这个网络流题挺简单的……
首先从[tex]S[/tex]向每个点连容量为该点存货量的边（费用为0）。首先注意最后所有存货量都要变成总的平均值，所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边（费用为0）。最后根据题目要求在相邻点之间连边（容量都是无限大，费用为1）。
跑一遍最小费用最大流，得出的费用就是答案。
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[maxn];
int main(){
register int i,ave=0;
int n;
freopen("overload.in","r",stdin);
freopen("overload.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
ave+=A[i];
MCMF::AddEdge(0,i,A[i],0);
}
ave/=n;
for(i=1;i<=n;i++){
MCMF::AddEdge(i,n+1,ave,0);
if(i>1){
MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
}
if(i<n){
MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
}
}
MCMF::AddEdge(1,n,0x7f7f7f7f,1);
MCMF::AddEdge(n,1,0x7f7f7f7f,1);
printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
fclose(stdin);
fclose(stdout);
return 0;
}
[COGS 740]分配问题
很明显是二分图最大权匹配。可以用匈牙利算法求解，但我比较弱……所以就写了个费用流。
注意最优解和最差解都要给出！
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
inline void ClearGraph(){
register int i;
edges.clear();
for(i=0;i<maxn;i++)
G[i].clear();
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[105][105];
int main(){
int n;
register int i,j;
freopen("job.in","r",stdin);
freopen("job.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&A[i][j]);
MCMF::AddEdge(i,j+n,1,A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",MCMF::MincostMaxflow(0,2*n+1));
MCMF::ClearGraph();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
MCMF::AddEdge(i,j+n,1,-A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",-(MCMF::MincostMaxflow(0,2*n+1)));
return 0;
}
