[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;
}
