写在前面：SDOI2016 Round1滚粗后蒟蒻开始做网络流来自我拯救(2016-04-11再过几天就要考先修课，现在做网络流24题貌似没什么用←退役节奏)
做的题目将附上日期，见证我龟速刷题。
1.飞行员配对方案问题 2016-04-11
二分图最大匹配问题，更新了一下$Dinic$模板，带上了当前弧优化和多路增广。这道题输出方案有很多种，可是没有special judge，所以没有A，但方案数是对的。合法的输出方案只能用匈牙利算法解决。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 1003;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
}
queue<int> q;
bool vis[N];
int point[N], cap[N], nxt[N], to[N], d[N], cur[N], S, T, cnt = 1;
bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); d[S] = 0; vis[S] = 1;
int u, i;
while (!q.empty()) {
u = q.front(); q.pop();
for(i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int &i = cur[u]; i; i = nxt[i])
if (d[u] + 1 == d[to[i]] && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0, i;
while (BFS()) {
for(i = 1; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, 0x7fffffff);
}
return flow;
}
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
void findpair(int x) {
for(int i = point[x]; i; i = nxt[i])
if (cap[i] == 0 && to[i] != S) {printf("%d %d\n", x, to[i]); break;}
}
int main() {
int n, m;
read(n); read(m);
S = n + m + 1; T = S + 1;
for(int i = 1; i <= n; ++i)
ins(S, i, 1), ins(i, S, 0);
for(int i = n + 1; i <= n + m; ++i)
ins(i, T, 1), ins(T, i, 0);
int u, v;
read(u); read(v);
while (u != -1 && v != -1) {
ins(u, v, 1); ins(v, u, 0);
read(u); read(v);
}
printf("%d\n", Dinic());
for(int i = 1; i <= n; ++i)
findpair(i);
return 0;
}
2.太空飞行计划问题 2016-04-13
典型的最大权闭合图问题，可是还是要输出方案！！！制杖地卡了1h+因为把n+m打成了n+m+1，然后发现还是会WA两个点。最后百度得知数据是不盈利也不亏损的项目还要加上，如果要这么做还得删边balabalabala。我不想再改了，所以就这样吧。我现在感觉什么都需要special judge，因为我太弱了hhh
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 1003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} bool vis[N];
queue <int> q;
int point[N], nxt[N], to[N], cap[N], d[N], cur[N], S, T, cnt = 1, n, m, Qsum = 0, Qmincut; void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
} bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
int u, i;
while (!q.empty()) {
u = q.front(); q.pop();
for(i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
q.push(to[i]);
vis[to[i]] = 1;
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0, i;
while (BFS()) {
for(i = 1; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} void Q() {
for(int i = 1; i <= m; ++i)
if (vis[i]) printf("%d ", i);
puts(""); for(int i = m + 1; i <= m + n; ++i)
if (vis[i]) printf("%d ", i - m); printf("\n%d\n", Qsum - Qmincut);
} int main() {
read(m); read(n);
S = m + n + 1; T = S + 1; int num; char c;
for(int i = 1; i <= m; ++i) {
read(num);
Qsum += num;
ins(S, i, num);
ins(i, S, 0);
c = getchar();
while(1) {
num = 0;
for(; c < '0' || c > '9'; c = getchar())
if (c == '\n') break;
if (c == '\n') break;
for(; c >= '0' && c <= '9'; c = getchar())
num = num * 10 + c - '0';
num = num + m;
ins(i, num, inf);
ins(num, i, 0);
}
} for(int i = m + 1; i <= m + n; ++i) {
read(num);
ins(i, T, num);
ins(T, i, 0);
} Qmincut = Dinic(); Q(); return 0;
}
3.最小路径覆盖问题 2016-04-13
二分图最大匹配问题。遇到求“最小”，因为我们求的都是最大流，所以应该往补集转化的方向思考，“总的”-“最大的”=“最小的”。这种题还应该注意一个地方，虽然在这里用不着，但要处处留心：最小路径覆盖问题值得注意的地方
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 20003;
const int inf = 0x7fffffff; queue <int> q;
bool vis[N];
int point[N], cur[N], nxt[N], to[N], cap[N], d[N], n, m, S, T, cnt = 1, Qmincut; int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
} bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); d[S] = 0; vis[S] = 1;
while (!q.empty()) {
int u = q.front(), i; q.pop();
for(i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int &i = point[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int i, flow = 0;
while (BFS()) {
for(i = 1; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} void QQ(int x) {
vis[x] = 1;
printf("%d ", x);
for(int i = point[x]; i; i = nxt[i])
if (cap[i] < inf && n < to[i] && to[i] <= n + n) QQ(to[i] - n);
}
void Q() {
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i)
if (!vis[i]) QQ(i), puts("");
printf("%d\n", n - Qmincut);
}
int main() {
read(n); read(m);
int u, v;
S = n + n + 1; T = S + 1;
for(int i = 1, j = n + 1; i <= n; ++i, ++j)
ins(S, i, 1), ins(i, S, 0), ins(j, T, 1), ins(T, j, 0);
for(int i = 1; i <= m; ++i) {
read(u); read(v); v += n;
ins(u, v, inf); ins(v, u, 0);
} Qmincut = Dinic(); Q(); return 0;
}
4.魔术球问题 2016-04-17
最小路径覆盖问题，想了好久，看完题解后还是想了好久QuQ。当时主要是不明白为什么满足单调性，后来才发现DAG上不断加边，最小路径覆盖数肯定是不减的，当时好制杖啊QAQ。写完后更制杖的是我发现我又需要special judge！！！怎么我现在弱到什么都需要special judge！！！PS:昨天北大先修课乙烷，xyx考得最好但是他没有用正规的比赛号交题，，，
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c= getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N << 1], to[N << 1], cap[N << 1], d[N], S, T, cnt = 1, ans = 0, n, Q = 0;
bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int i = point[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
void Dinic() {
while (BFS()) ans -= DFS(S, 0x7fffffff);
} void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
void Qwork(int x) {
printf("%d ", x);
vis[x] = 1;
for(int i = point[x]; i; i = nxt[i])
if (!cap[i] && to[i] > 5000 && to[i] < 5000 + Q && !vis[to[i] - 5000])
Qwork(to[i] - 5000);
}
int main() {
read(n); S = 0; T = 10002;
while (1) {
++ans; ++Q;
for(int i = 1; i < Q; ++i)
if (sqrt(i + Q) == (int)(sqrt(i + Q)))
ins(i, Q + 5000, 1), ins(Q + 5000, i, 0);
ins(S, Q, 1); ins(Q, S, 0);
ins(Q + 5000, T, 1); ins(T, Q + 5000, 0);
Dinic();
if (ans > n) {
printf("%d\n", Q - 1);
break;
}
} memset(vis, 0, sizeof(vis));
for(int i = 1; i < Q; ++i)
if (!vis[i])
Qwork(i), puts(""); return 0;
}
5.圆桌问题 2016-04-17
很简单的二分图多重匹配，写完后我发现我又需要special judge了QAQ
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], cur[N], nxt[N << 1], to[N << 1], cap[N << 1], S, T, cnt = 1, d[N]; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0;
while (BFS()) {
for(int i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, 0x7fffffff);
}
return flow;
} void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
int main() {
int n, m, x, Qsum = 0;
read(m); read(n);
S = 0; T = m + n + 1;
for(int i = 1; i <= m; ++i)
read(x), ins(S, i, x), ins(i, S, 0), Qsum += x;
for(int i = m + 1; i < T; ++i)
read(x), ins(i, T, x), ins(T, i, 0);
for(int i = 1; i <= m; ++i)
for(int j = m + 1; j < T; ++j)
ins(i, j, 1), ins(j, i, 0); int Q = Dinic();
if (Q == Qsum) {
puts("1");
for(int i = 1; i <= m; ++i) {
cnt = 0;
for(int tmp = point[i]; tmp; tmp = nxt[tmp])
if (!cap[tmp] && to[tmp] > m && to[tmp] < T)
d[++cnt] = to[tmp] - m;
for(; cnt; --cnt) printf("%d ", d[cnt]);
puts("");
}
} else
puts("0"); return 0;
}
6.最长递增子序列问题 2016-04-17
分层图思想可以保证走的每条路都是最长的，统计最大流就可以了，对于第三问放宽$X_1,X_n$的限制即可。还有一个地方我卡了好久，就是$inf$设置成了$0x7fffffff$，这样会出现爆int的情况，只需把inf调小一点，输出时特判一下就没了，，，TwT我卡了3h+啊
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x = getint()
using namespace std;
const int N = 100003;
const int inf = 1E9;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], cur[N], d[N], nxt[N << 1], to[N << 1], cap[N << 1], S, T, cnt = 1; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); d[S] = 0; vis[S] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int f, flow = 0;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int i, flow = 0;
while (BFS()) {
for(i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} int a[N], f[N];
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
int main() {
int n;
read(n);
for(int i = 1; i <= n; ++i)
read(a[i]); f[n] = 1;
for(int i = n - 1; i > 0; --i) {
f[i] = 1;
for(int j = n; j > i; --j)
if (a[i] <= a[j] && f[j] + 1 > f[i])
f[i] = f[j] + 1;
} int k = 0;
for(int i = 1; i <= n; ++i)
k = max(k, f[i]);
printf("%d\n", k); S = 0; T = (n << 1) + 1;
for(int i = 1; i <= n; ++i) {
ins(i, i + n, 1), ins(i + n, i, 0);
if (f[i] == k)
ins(S, i, 1), ins(i, S, 0);
if (f[i] == 1)
ins(i + n, T, 1), ins(T, i + n, 0);
}
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
if (a[i] <= a[j] && f[i] == f[j] + 1)
ins(i + n, j, 1), ins(j, i + n, 0);
int Q = Dinic();
printf("%d\n", Q); memset(point, 0, sizeof(point)); cnt = 1;
for(int i = 1; i <= n; ++i) {
if (i == 1 || i == n) {
ins(i, i + n, inf), ins(i + n, i, 0);
if (f[i] == k)
ins(S, i, inf), ins(i, S, 0);
if (f[i] == 1)
ins(i + n, T, inf), ins(T, i + n, 0);
} else {
ins(i, i + n, 1), ins(i + n, i, 0);
if (f[i] == k)
ins(S, i, 1), ins(i, S, 0);
if (f[i] == 1)
ins(i + n, T, 1), ins(T, i + n, 0);
}
}
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
if (a[i] <= a[j] && f[i] == f[j] + 1)
ins(i + n, j, 1), ins(j, i + n, 0);
Q = Dinic();
printf("%d\n", Q > inf ? n : Q); return 0;
}
7.试题库问题 2016-04-17
水题，不过我又需要special judge了QuQ
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 10003;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], cur[N], nxt[N << 1], to[N << 1], S, T, cnt = 1, d[N], cap[N << 1]; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); d[S] = 0; vis[S] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int flow = 0, f;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0;
while (BFS()) {
for(int i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, 0x7fffffff);
}
return flow;
} void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
int main() {
int k, n, m = 0, x, p;
read(k); read(n);
S = 0; T = k + n + 1;
for(int i = 1; i <= k; ++i)
read(x), ins(S, i, x), ins(i, S, 0), m += x;
for(int i = 1; i <= n; ++i) {
read(p);
for(int j = 1; j <= p; ++j) {
read(x);
ins(x, i + k, 1);
ins(i + k, x, 0);
}
}
for(int i = k + 1; i < T; ++i)
ins(i, T, 1), ins(T, i, 0); int Q = Dinic();
if (Q == m) {
for(int i = 1; i <= k; ++i) {
printf("%d:", i);
for(int tmp = point[i]; tmp; tmp = nxt[tmp])
if (!cap[tmp] && to[tmp] > k && to[tmp] < T)
printf(" %d", to[tmp] - k);
puts("");
}
} else
puts("No Solution!"); return 0;
}
8.机器人路径规划问题
貌似这道题挺麻烦，CTSC和省选Round2前没有太多时间，暂时略过，省选二轮滚粗后再来看QAQ
9.方格取数问题 2016-04-18
因为最大独立点集+最小点覆盖集=总点数，那么最大点权独立集+最小点权覆盖集=总点权和。我们只需求最小点权覆盖集就可以了。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int inf = 0x7fffffff;
const int N = 100003;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], cur[N], nxt[N << 1], cap[N << 1], to[N << 1], S, T, cnt = 1, d[N]; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int flow = 0, f;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0;
while (BFS()) {
for(int i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} int a[53][53];
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
void QQ(int Qsum) {
int Q = Dinic();
Q = Qsum - Q;
printf("%d\n", Q);
}
int main() {
int n, m, Qsum = 0;
read(m); read(n);
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
read(a[i][j]), Qsum += a[i][j];
S = 0; T = n * m + 1;
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if ((i + j) % 2 == 0) {
ins(S, (i - 1) * n + j, a[i][j]);
ins((i - 1) * m + j, S, 0);
if (i > 1) {
ins((i - 1) * n + j, (i - 2) * n + j, inf);
ins((i - 2) * n + j, (i - 1) * n + j, 0);
}
if (j > 1) {
ins((i - 1) * n + j, (i - 1) * n + j - 1, inf);
ins((i - 1) * n + j - 1, (i - 1) * n + j, 0);
}
if (i < m) {
ins((i - 1) * n + j, i * n + j, inf);
ins(i * n + j, (i - 1) * n + j, 0);
}
if (j < n) {
ins((i - 1) * n + j, (i - 1) * n + j + 1, inf);
ins((i - 1) * n + j + 1, (i - 1) * n + j, 0);
}
}
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
if ((i + j) % 2 == 1) {
ins((i - 1) * n + j, T, a[i][j]);
ins(T, (i - 1) * n + j, 0);
} QQ(Qsum); return 0;
}
10.餐巾计划问题 2016-04-18
最小费用最大流问题。在保证最大流的前提下求最小费用，建图我就不细说了，主要是把买的和洗的餐巾分为两部分，网上有很多题解。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N << 1], to[N << 1], cap[N << 1], S, T, cnt = 1;
int d[N], w[N << 1], from[N << 1], pre[N << 1]; bool spfa(int s, int t) {
for(int i = 0; i <= t; ++i) vis[i] = 0, d[i] = inf;
d[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[t] != inf;
}
int mcmf(int s, int t) {
int ret = 0, f, u;
while (spfa(s, t)) {
f = inf;
for(u = t; u != s; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = t; u != s; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[t];
}
return ret;
} int nn, p, m, f, n, s, r[N];
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(nn); read(p); read(m); read(f); read(n); read(s);
for(int i = 1; i <= nn; ++i)
read(r[i]);
S = 0; T = (nn << 1) + 1;
for(int i = 1; i <= nn; ++i) {
ins(S, i, r[i], 0);
ins(i, S, 0, 0);
ins(i + nn, T, r[i], 0);
ins(T, i + nn, 0, 0);
ins(S, i + nn, inf, p);
ins(i + nn, S, 0, -p);
if (i < nn) {
ins(i, i + 1, inf, 0);
ins(i + 1, i, 0, 0);
}
if (i + m <= nn) {
ins(i, i + m + nn, inf, f);
ins(i + m + nn, i, 0, -f);
}
if (i + n <= nn) {
ins(i, i + n + nn, inf, s);
ins(i + n + nn, i, 0, -s);
}
} int Q = mcmf(S, T);
printf("%d\n", Q); return 0;
}
11.航空路线问题 2016-04-18
裸拆点最小费用最大流，我打错了MCMF模板，查了1h的错TwT。在第二组数据吐血QAQ，只好面向数据编程，，，还有I need special judge again!!!
#include<map>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} map <string, int> ma;
queue <int> q;
bool vis[N];
int point[N], nxt[N << 1], to[N << 1], cap[N << 1], d[N];
int S, T, cnt = 1, w[N << 1], from[N << 1], pre[N]; bool spfa() {
for(int i = 0; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} int n, v, x, y;
string s1, s2, str[N];
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
void QQ(int x) {
cout<< str[x] << endl;
for(int i = point[x + n]; i; i = nxt[i])
if (!cap[i] && !vis[to[i]] && to[i] > 0 && to[i] <= n)
{QQ(to[i]); break;}
}
void QQQ(int x) {
if (x == n) {
QQ(1);
return;
}
vis[x] = 1;
for(int i = point[x + n]; i; i = nxt[i])
if (!cap[i] && to[i] > 0 && to[i] <= n)
{QQQ(to[i]); break;}
cout << str[x] <<endl;
}
int main() {
read(n); read(v);
ma.clear();
for(int i = 1; i <= n; ++i)
cin >> str[i], ma[str[i]] = i;
S = 1; T = n << 1;
for(int i = 1; i <= n; ++i)
if (i == 1 || i == n) {
ins(i, i + n, 2, -1);
ins(i + n, i, 0, 1);
} else {
ins(i, i + n, 1, -1);
ins(i + n, i, 0, 1);
}
for(int i = 1; i <= v; ++i) {
cin >> s1 >> s2;
x = ma[s1]; y = ma[s2];
ins(x + n, y, 1, 0);
ins(y, x + n, 0, 0);
} int Q = mcmf();
if (cap[2] && n != 3)
puts("No Solution!");
else
printf("%d\n", n != 3 ? - Q - 2 : -Q), memset(vis, 0, sizeof(vis)), QQQ(1); return 0;
}
12.软件补丁问题 2016-04-18
因为只有20种错误，考虑状态压缩然后spfa最短路，这还是网络流吗，，，
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2000003;
char a[23], b[23];
bool vis[N];
queue <int> q;
int b1[N], b2[N], f1[N], f2[N], cost[N], n, m, d[N], inf;
int spfa(int s, int t) {
memset(d, 127, sizeof(d)); inf = d[t];
d[s] = 0; q.push(s); vis[s] = 0; while (!q.empty()) {
int x = q.front(); q.pop(); vis[x] = 0;
for(int i = 1; i <= m; ++i)
if ((x | b1[i]) == x && (x & b2[i]) == 0) {
int y = x & (~ f1[i]);
y |= f2[i];
if (d[y] > d[x] + cost[i]) {
d[y] = d[x] + cost[i];
if (!vis[y]) {
vis[y] = 1;
q.push(y);
}
}
}
} return d[t] == inf ? 0 : d[t];
} int main() {
memset(b1, 0, sizeof(b1));
memset(b2, 0, sizeof(b2));
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; ++i) {
scanf("%d %s %s", &cost[i], a, b);
for(int j = 0; j < strlen(a); ++j)
if (a[j] == '+') b1[i] |= 1 << j;
else if (a[j] == '-') b2[i] |= 1 << j;
for(int j = 0; j < strlen(b); ++j)
if (b[j] == '+') f2[i] |= 1 << j;
else if (b[j] == '-') f1[i] |= 1 << j;
} printf("%d\n", spfa((1 << n) - 1, 0)); return 0;
}
13.星际转移问题 2016-04-18
将每天转化为分层图，然后每天都跑最大流，若最大流大于等于k，则输出答案。特殊情况我还是面向数据编程，，，我怎么这么弱QAQ
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 2000003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} bool vis[N];
queue <int> q;
int point[N], cur[N], nxt[N], cap[N], d[N], to[N], S, T, cnt = 1; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int flow = 0, f;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0;
while (BFS()) {
for(int i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} struct node {int r, num, a[103];} B[203];
int n, m, k;
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
void mk(int &x) {x = (x == 0 ? n + 1 : (x == -1 ? n + 2 : x));}
int main() {
read(n); read(m); read(k);
S = 0; T = N - 3;
for(int i = 1; i <= m; ++i) {
read(B[i].r); read(B[i].num);
for(int j = 1; j <= B[i].num; ++j)
read(B[i].a[j]), mk(B[i].a[j]);
B[i].a[0] = B[i].a[B[i].num];
}
int earth = n + 1, moon = n + 2, gh = moon, Q = 0; ins(S, earth, k), ins(earth, S, 0);
for(int Day = 1; Day <= 30; ++Day) {
for(int i = 1; i < gh; ++i) {
ins((Day - 1) * gh + i, Day * gh + i, inf);
ins(Day * gh + i, (Day - 1) * gh + i, 0);
}
ins(Day * gh + moon, T, inf), ins(T, Day * gh + moon, 0);
for(int i = 1; i <= m; ++i) {
int last = B[i].a[Day % B[i].num], now = B[i].a[(Day + 1) % B[i].num];
ins((Day - 1) * gh + last, Day * gh + now, B[i].r);
ins(Day * gh + now, (Day - 1) * gh + last, 0);
}
Q += Dinic();
if (Q >= k) {
printf("%d\n", Day);
break;
}
} if (Q < k)
puts("0"); return 0;
}
14.孤岛营救问题 2016-04-18
在分层图上spfa，不是网络流，，，以后是不是遇到水的数据就应该考虑不同寻常的做法。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 2000003;
const int inf = 2139062143;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int cnt = 1, point[N], nxt[N], to[N], w[N], d[N]; void spfa(int s) {
memset(vis, 0, sizeof(vis));
memset(d, 127, sizeof(d));
q.push(s); vis[s] = 1; d[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
} int n, m, p, k, S, map[16][16][16][16];
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; w[cnt] = z; point[x] = cnt;
}
int main() {
read(n); read(m); read(p); read(k);
memset(map, -1, sizeof(map));
int x1, x2, y1, y2, z, dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
for(int i = 1; i <= k; ++i) {
read(x1); read(y1); read(x2); read(y2); read(z);
map[x1][y1][x2][y2] = map[x2][y2][x1][y1] = z;
} read(S);
for(int i = 1; i <= S; ++i) {
read(x1); read(y1); read(z);
for(int j = 0; j < (1 << p); ++j)
if (((1 << (z - 1)) & j) == 0)
ins(j * n * m + (x1 - 1) * m + y1, (j | (1 << (z - 1))) * n * m + (x1 - 1) * m + y1, 0);
} for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
for(int nu = 0; nu < 4; ++nu) {
x1 = i + dx[nu]; y1 = j + dy[nu];
if (x1 > 0 && x1 <= n && y1 > 0 && y1 <= m) {
if (map[i][j][x1][y1] == -1) {
for(int l = 0; l < (1 << p); ++l)
ins(l * n * m + (i - 1) * m + j, l * m * n + (x1 - 1) * m + y1, 1);
} else if (map[i][j][x1][y1] > 0) {
for(int l = 0; l < (1 << p); ++l)
if ((1 << (map[i][j][x1][y1] - 1)) & l)
ins(l * n * m + (i - 1) * m + j, l * n * m + (x1 -1) * m + y1, 1);
}
}
} spfa(1);
int Q = inf;
for(int i = 0; i <= (1 << p); ++i)
Q = min(Q, d[i * n * m]);
printf("%d\n", Q == inf ? -1 : Q); return 0;
}
15.汽车加油形式问题 2016-04-18
还是最短路，，，BFS暴力过掉，不知道还有什么其他做法。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} struct node {int x, y, gas, cos;};
queue <node> q;
int N, K, A, B, C, f[103][103][13], dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
short a[103][103]; int Q() {
node u, now;
memset(f, 127, sizeof(f));
f[1][1][K] = 0;
u.x = u.y = 1; u.gas = K; u.cos = 0;
q.push(u);
while (!q.empty()) {
u = q.front(); q.pop();
if (u.gas == 0) continue;
for(int i = 0; i < 4; ++i) {
now.x = u.x + dx[i]; now.y = u.y + dy[i];
if (now.x > 0 && now.x <= N && now.y > 0 && now.y <= N) {
now.gas = u.gas - 1; now.cos = u.cos;
if (now.x < u.x || now.y < u.y)
now.cos += B;
if (a[now.x][now.y]) {
now.gas = K; now.cos += A;
if (now.cos < f[now.x][now.y][now.gas])
f[now.x][now.y][now.gas] = now.cos, q.push(now);
} else {
if (now.cos < f[now.x][now.y][now.gas])
f[now.x][now.y][now.gas] = now.cos, q.push(now);
now.gas = K; now.cos += A + C;
if (now.cos < f[now.x][now.y][now.gas])
f[now.x][now.y][now.gas] = now.cos, q.push(now);
}
}
}
} int ret = 0x7fffffff;
for(int i = 0; i <= K; ++i)
ret = min(ret, f[N][N][i]);
return ret;
} int main() {
read(N); read(K); read(A); read(B); read(C);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
read(a[i][j]); printf("%d\n", Q()); return 0;
}
16.数字梯形问题 2016-04-18
最小费用最大流，相当于写了3道水题，不过Ctrl+C,Ctrl+V大法好！建图时结点直接用坐标表示略偷懒
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N], to[N], pre[N], from[N], cap[N], d[N], w[N], S, T, cnt = 1; bool spfa() {
for(int i = 0; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} int m, n, ss, nn, x[103][103];
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(m); read(n);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m + i - 1; ++j)
read(x[i][j]); nn = (m + n) * n; T = 2 * nn + 2; ss = T - 1; S = 0;
ins(S, ss, m, 0); ins(ss, S, 0, 0);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m + i - 1; ++j) {
ins((i - 1) * (n + m) + j, (i - 1) * (n + m) + j + nn, 1, - x[i][j]);
ins((i - 1) * (n + m) + j + nn, (i - 1) * (n + m) + j, 0, x[i][j]);
if (i == n) {
ins((i - 1) * (n + m) + j + nn, T, 1, 0);
ins(T, (i - 1) * (n + m) + j + nn, 0, 0);
} else {
if (i == 1) {
ins(ss, (i - 1) * (n + m) + j, 1, 0);
ins((i - 1) * (n + m) + j, ss, 0, 0);
}
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j, 1, 0);
ins(i * (n + m) + j, (i - 1) * (n + m) + j + nn, 0, 0);
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j + 1, 1, 0);
ins(i * (n + m) + j + 1, (i - 1) * (n + m) + j + nn, 0, 0);
}
}
int Q = mcmf();
printf("%d\n", - Q); memset(point, 0, sizeof(point));
ins(S, ss, m, 0); ins(ss, S, 0, 0);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m + i - 1; ++j) {
ins((i - 1) * (n + m) + j, (i - 1) * (n + m) + j + nn, inf, - x[i][j]);
ins((i - 1) * (n + m) + j + nn, (i - 1) * (n + m) + j, 0, x[i][j]);
if (i == n) {
ins((i - 1) * (n + m) + j + nn, T, inf, 0);
ins(T, (i - 1) * (n + m) + j + nn, 0, 0);
} else {
if (i == 1) {
ins(ss, (i - 1) * (n + m) + j, 1, 0);
ins((i - 1) * (n + m) + j, ss, 0, 0);
}
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j, 1, 0);
ins(i * (n + m) + j, (i - 1) * (n + m) + j + nn, 0, 0);
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j + 1, 1, 0);
ins(i * (n + m) + j + 1, (i - 1) * (n + m) + j + nn, 0, 0);
}
}
Q = mcmf();
printf("%d\n", - Q); memset(point, 0, sizeof(point));
ins(S, ss, m, 0); ins(ss, S, 0, 0);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m + i - 1; ++j) {
ins((i - 1) * (n + m) + j, (i - 1) * (n + m) + j + nn, inf, - x[i][j]);
ins((i - 1) * (n + m) + j + nn, (i - 1) * (n + m) + j, 0, x[i][j]);
if (i == n) {
ins((i - 1) * (n + m) + j + nn, T, inf, 0);
ins(T, (i - 1) * (n + m) + j + nn, 0, 0);
} else {
if (i == 1) {
ins(ss, (i - 1) * (n + m) + j, 1, 0);
ins((i - 1) * (n + m) + j, ss, 0, 0);
}
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j, inf, 0);
ins(i * (n + m) + j, (i - 1) * (n + m) + j + nn, 0, 0);
ins((i - 1) * (n + m) + j + nn, i * (n + m) + j + 1, inf, 0);
ins(i * (n + m) + j + 1, (i - 1) * (n + m) + j + nn, 0, 0);
}
}
Q = mcmf();
printf("%d\n", - Q); return 0;
}
17.运输问题 2016-04-19
最小费用最大流，，，
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N], cap[N], from[N], w[N], to[N], d[N], pre[N], S, T, cnt = 1; bool spfa() {
for(int i = 1; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} int m, n, x[503], c[503][503];
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(m); read(n);
S = 0; T = m + n + 1;
for(int i = 1; i <= m; ++i)
read(x[i]), ins(S, i, x[i], 0), ins(i, S, 0, 0);
for(int i = m + 1; i < T; ++i)
read(x[i]), ins(i, T, x[i], 0), ins(T, i, 0, 0);
for(int i = 1; i <= m; ++i)
for(int j = m + 1; j < T; ++j) {
read(c[i][j]);
ins(i, j, inf, c[i][j]);
ins(j, i, 0, - c[i][j]);
}
int Q = mcmf();
printf("%d\n", Q); memset(point, 0, sizeof(point)); cnt = 1;
for(int i = 1; i <= m; ++i)
ins(S, i, x[i], 0), ins(i, S, 0, 0);
for(int i = m + 1; i < T; ++i)
ins(i, T, x[i], 0), ins(T, i, 0, 0);
for(int i = 1; i <= m; ++i)
for(int j = m + 1; j < T; ++j) {
ins(i, j, inf, - c[i][j]);
ins(j, i, 0, c[i][j]);
}
Q = - mcmf();
printf("%d\n", Q); return 0;
}
18.分配问题 2016-04-19
最小费用最大流，，，，，，，，，，，，，，，，，
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N], cap[N], from[N], w[N], to[N], d[N], pre[N], S, T, cnt = 1; bool spfa() {
for(int i = 1; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} int n, c[503][503];
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(n);
S = 0; T = n + n + 1;
for(int i = 1; i <= n; ++i)
ins(S, i, 1, 0), ins(i, S, 0, 0);
for(int i = n + 1; i < T; ++i)
ins(i, T, 1, 0), ins(T, i, 0, 0);
for(int i = 1; i <= n; ++i)
for(int j = n + 1; j < T; ++j) {
read(c[i][j]);
ins(i, j, inf, c[i][j]);
ins(j, i, 0, - c[i][j]);
}
int Q = mcmf();
printf("%d\n", Q); memset(point, 0, sizeof(point)); cnt = 1;
for(int i = 1; i <= n; ++i)
ins(S, i, 1, 0), ins(i, S, 0, 0);
for(int i = n + 1; i < T; ++i)
ins(i, T, 1, 0), ins(T, i, 0, 0);
for(int i = 1; i <= n; ++i)
for(int j = n + 1; j < T; ++j) {
ins(i, j, inf, - c[i][j]);
ins(j, i, 0, c[i][j]);
}
Q = - mcmf();
printf("%d\n", Q); return 0;
}
19.负载平衡问题 2016-04-19
还是最小费用最大流，我第一次WA了，因为只是将$X_i$连了一条向$Y_i$的流量无穷大的边，但有可能出现一些货物运输跨过几个仓库的情况，于是便从$Y_i$向$X_i$连一流量无穷大的边，保证货物在运输一次之后可以继续运输。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 10003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], nxt[N], from[N], to[N], pre[N], cap[N], w[N], d[N], S, T, cnt = 1; bool spfa() {
for(int i = 1; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} int n, x, Qsum = 0, to1, to2;
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(n);
S = 0; T = (n << 1) + 1;
for(int i = 1; i <= n; ++i)
read(x), ins(S, i, x, 0), ins(i, S, 0, 0), Qsum += x;
for(int i = n + 1; i < T; ++i)
ins(i, T, Qsum / n, 0), ins(T, i, 0, 0);
for(int i = 1; i <= n; ++i) {
ins(i, i + n, inf / 2, 0);
ins(i + n, i, inf / 2, 0);
to1 = i == 1 ? n + n : i - 1 + n;
to2 = i == n ? 1 + n : i + 1 + n;
ins(i, to1, inf, 1);
ins(to1, i, 0, -1);
ins(i, to2, inf, 1);
ins(to2, i, 0, -1);
} int Q = mcmf();
printf("%d\n", Q); return 0;
}
20.深海机器人问题 2016-04-19
BYVoid的题解上说是线性规划网络优化，可是我并没有看出来线性规划用在哪里了，，，这道题建图时因为一条道路上的生物只能采集一次，所以得设流量限制为1，但因为在这条路上采集后其他机器人还可以再走，所以再连一条容量为无穷，费用为0的边，保证了后来的任何机器人都可以从这条路上走过而且不会计算费用233。
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], from[N], nxt[N], to[N], cap[N], d[N], pre[N], w[N], S, T, cnt = 1; bool spfa() {
for(int i = 0; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += d[T] * f;
}
return ret;
} int P, Q, a, b, r, x, y;
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(a); read(b); read(P); read(Q);
S = (P + 1) * (Q + 1) + 1; T = S + 1;
for(int i = 0; i <= P; ++i)
for(int j = 0; j < Q; ++j) {
read(x);
ins(i * (Q + 1) + j, i * (Q + 1) + j + 1, 1, - x);
ins(i * (Q + 1) + j + 1, i * (Q + 1) + j, 0, x);
ins(i * (Q + 1) + j, i * (Q + 1) + j + 1, inf, 0);
ins(i * (Q + 1) + j + 1, i * (Q + 1) + j, 0, 0);
}
for(int j = 0; j <= Q; ++j)
for(int i = 0; i < P; ++i) {
read(x);
ins(i * (Q + 1) + j, (i + 1) * (Q + 1) + j, 1, - x);
ins((i + 1) * (Q + 1) + j, i * (Q + 1) + j, 0, x);
ins(i * (Q + 1) + j, (i + 1) * (Q + 1) + j, inf, 0);
ins((i + 1) * (Q + 1) + j, i * (Q + 1) + j, 0, 0);
}
for(int i = 1; i <= a; ++i) {
read(r); read(x); read(y);
ins(S, x * (Q + 1) + y, r, 0);
ins(x * (Q + 1) + y, S, 0, 0);
}
for(int i = 1; i <= b; ++i) {
read(r); read(x); read(y);
ins(x * (Q + 1) + y, T, r, 0);
ins(T, x * (Q + 1) + y, 0, 0);
} int QQ = - mcmf();
printf("%d\n", QQ); return 0;
}
21.最长k可重区间集问题 2016-04-19
查了3h错，因为离散化完全写错了，还有这道题数据辣么水，为什么要写离散化(┙>∧<)┙へ┻┻。重写了离散化之后还是WA三个点，又查了1h+后在codevs的题解上发现数据错了(ﾟ皿ﾟﾒ)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 100003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], from[N], nxt[N], to[N], cap[N], w[N], d[N], pre[N], S, T, cnt = 1; bool spfa() {
for(int i = 1; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 0; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for(int i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
int mcmf() {
int ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += f * d[T];
}
return ret;
} struct node {
int l, r;
} a[1003];
int n, k, H[2003], id[2003], HH[2003], num = 1, cos, He[2003];
bool cmp2(int X, int Y) {return H[X] < H[Y];}
void ins(int x, int y, int z, int zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
int main() {
read(n); read(k);
for(int i = 1; i <= n; ++i)
read(H[(i << 1) - 1]), read(H[i << 1]);
for(int i = 1; i <= (n << 1); ++i)
id[i] = i;
sort(id + 1, id + (n << 1) + 1, cmp2);
for(int i = 1; i <= (n << 1); ++i) {
He[num] = H[id[i]];
HH[id[i]] = num;
if (H[id[i]] != H[id[i + 1]] && i != (n << 1)) ++num;
} S = 0; T = num + 1;
ins(S, 1, k, 0); ins(1, S, 0, 0);
ins(num, T, k, 0); ins(T, num, 0, 0);
for(int i = 1; i < num; ++i)
ins(i, i + 1, inf, 0), ins(i + 1, i, 0, 0);
for(int i = 1; i < (n << 1); i += 2) {
cos = He[HH[i + 1]] - He[HH[i]];
ins(HH[i], HH[i + 1], 1, - cos);
ins(HH[i + 1], H[i], 0, cos);
printf("%d %d : %d\n", HH[i], HH[i + 1], cos);
} int Q = - mcmf();
printf("%d\n", Q); return 0;
}
22.最长k可重线段集问题 2016-04-19
查错查了一个下午，发现各大OJ上此题AC率都是0，最后Menci神犇说数据有误，，，不管对不对，我还是先把自己愚蠢的代码贴上来吧
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const long long N = 1000003;
const long long inf = 0x7fffffff;
long long getint() {
long long k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <long long> q;
bool vis[N];
long long point[N], from[N], nxt[N], to[N], cap[N], d[N], w[N], pre[N], S, T, cnt = 1; bool spfa() {
for(long long i = 0; i <= T; ++i) vis[i] = 0, d[i] = inf;
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
long long u = q.front(); q.pop(); vis[u] = 0;
for(long long i = point[u]; i; i = nxt[i])
if (cap[i] && d[to[i]] > d[u] + w[i]) {
d[to[i]] = d[u] + w[i];
pre[to[i]] = i;
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
return d[T] != inf;
}
long long mcmf() {
long long ret = 0, f, u;
while (spfa()) {
f = inf;
for(u = T; u != S; u = from[pre[u]]) f = min(f, cap[pre[u]]);
for(u = T; u != S; u = from[pre[u]]) cap[pre[u]] -= f, cap[pre[u] ^ 1] += f;
ret += d[T] * f;
}
return ret;
} long long n, k, num = 1, W[1003], H[2003], id[2003], HH[2003];
void ins(long long x, long long y, long long z, long long zz) {
nxt[++cnt] = point[x]; from[cnt] = x; to[cnt] = y; cap[cnt] = z; w[cnt] = zz; point[x] = cnt;
}
long long sqr(long long x) {return x * x;}
bool cmp(long long X, long long Y) {return H[X] < H[Y];}
int main() {
long long x1, x2, y1, y2;
read(n); read(k);
for(long long i = 1; i <= n; ++i) {
read(x1); read(y1); read(x2); read(y2);
if (x1 > x2) swap(x1, x2), swap(y1, y2);
H[(i << 1) - 1] = x1; H[i << 1] = x2;
W[i] = floor(sqrt(sqr(x1 - x2) + sqr(y1 - y2)));
}
for(long long i = 1; i <= (n << 1); ++i)
id[i] = i;
sort(id + 1, id + (n << 1) + 1, cmp);
for(long long i = 1; i <= (n << 1); ++i) {
HH[id[i]] = num;
if (H[id[i]] != H[id[i + 1]] && i != (n << 1)) ++num;
}
S = 0; T = (num << 1) + 1;
ins(S, 1, k, 0); ins(1, S, 0, 0);
ins(num << 1, T, k, 0); ins(T, num << 1, 0, 0);
for(long long i = 1; i < (num << 1); ++i)
ins(i, i + 1, inf, 0), ins(i + 1, i, 0, 0);
for(long long i = 1; i <= n; ++i) {
long long le = HH[(i << 1) - 1], ri = HH[i << 1];
if (le == ri) {
ins((le << 1) - 1, le << 1, 1, - W[i]);
ins(le << 1, (le << 1) - 1, 0, W[i]);
} else {
ins(le << 1, (ri << 1) - 1, 1, - W[i]);
ins((ri << 1) - 1, le << 1, 0, W[i]);
}
} long long Q = - mcmf();
printf("%d\n", Q); return 0;
}
23.火星探险问题 2016-04-19
数据还是有问题！！！和深海机器人问题差不多，我就不做了吧，，，毕竟A不了
24.骑士共存问题 2016-04-19
典型最大权闭合图，染色后建图，，，zyf神犇说这是道水题←此话没有特别意思
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define read(x) x=getint()
using namespace std;
const int N = 1000003;
const int inf = 0x7fffffff;
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
} queue <int> q;
bool vis[N];
int point[N], cur[N], d[N], cap[N], nxt[N], to[N], S, T, cnt = 1; bool BFS() {
memset(vis, 0, sizeof(vis));
q.push(S); vis[S] = 1; d[S] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for(int i = point[u]; i; i = nxt[i])
if (!vis[to[i]] && cap[i]) {
d[to[i]] = d[u] + 1;
vis[to[i]] = 1;
q.push(to[i]);
}
}
return vis[T];
}
int DFS(int u, int a) {
if (u == T || !a) return a;
int flow = 0, f;
for(int &i = cur[u]; i; i = nxt[i])
if (d[to[i]] == d[u] + 1 && (f = DFS(to[i], min(a, cap[i]))) > 0) {
flow += f; a -= f; cap[i] -= f; cap[i ^ 1] += f;
if (!a) break;
}
return flow;
}
int Dinic() {
int flow = 0, i;
while (BFS()) {
for(i = 0; i <= T; ++i) cur[i] = point[i];
flow += DFS(S, inf);
}
return flow;
} bool pd[203][203];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int n, m, x, y;
void ins(int x, int y, int z) {
nxt[++cnt] = point[x]; to[cnt] = y; cap[cnt] = z; point[x] = cnt;
}
int main() {
read(n); read(m);
for(int i = 1; i <= m; ++i) {
read(x); read(y);
pd[x][y] = 1;
}
S = 0; T = n * n + 1;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if (!pd[i][j])
if ((i + j) % 2 ==0) {
ins(S, (i - 1) * n + j, 1);
ins((i - 1) * n + j, S, 0);
} else {
ins((i - 1) * n + j, T, 1);
ins(T, (i - 1) * n + j, 0);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if (!pd[i][j] && (i + j) % 2 == 0)
for(int k = 0; k < 8; ++k) {
x = i + dx[k]; y = j + dy[k];
if (x < 1 || x > n || y < 1 || y > n || pd[x][y])
continue;
int now = (x - 1) * n + y;
ins((i - 1) * n + j, now, inf);
ins(now, (i - 1) * n + j, 0);
} int Q = Dinic();
printf("%d\n", n * n - m - Q); return 0;
}
2016-04-19：线性规划与网络流24题就告一段落了，因为8机器人路径规划问题有点困难，暂时先放一放，还有最长k可重线段集问题和火星探险问题2道题的测试数据存在较大问题，没有办法AC，所以那三道题就先被我抛弃了QAQ。说好的线性规划呢？做完了连线性规划的影子都没见到，还是我太弱根本不懂线性规划QuQ。今天是停课第二天，我有没有取得进步自己也说不清楚，走一步看一步吧。CTSC2016， SDOI2016 Round2 Bless All!