拆点
餐饮
农夫约翰一共烹制了 (F) 种食物，并提供了 (D) 种饮料。
约翰共有 (N) 头奶牛，其中第 (i) 头奶牛有 (F_i) 种喜欢的食物以及 (D_i) 种喜欢的饮料。
约翰需要给每头奶牛分配一种食物和一种饮料，并使得有吃有喝的奶牛数量尽可能大。
每种食物或饮料都只有一份，所以只能分配给一头奶牛食用（即，一旦将第 (2) 种食物分配给了一头奶牛，就不能再分配给其他奶牛了）。
开始想的错误思路是拆牛，超级源点连所有的牛
正解：
/*
* @Author: zhl
* @Date: 2020-10-20 11:09:59
*/
/*
* 拆点策略： 把一头牛拆成两头，从源点到实物到牛再到饮料再到汇点
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define repE(i,u) for(int i = head[u];~i;i = E[i].next)
using namespace std;
const int N = 5e2 + 10, M = 5e3 + 10, inf = 1e9;
struct Edge {
int to, flow, next;
}E[M << 1];
int head[N], tot;
void addEdge(int from, int to, int w) {
E[tot] = Edge{ to,w,head[from] };
head[from] = tot++;
E[tot] = Edge{ from,0,head[to] };
head[to] = tot++;
}
int n, m, s, t, P_nums;//图中总点数[0-P_nums]
int dis[N], cur[N];
bool bfs() {
rep(i, 0, P_nums)dis[i] = -1;
queue<int>Q;
Q.push(s); dis[s] = 0; cur[s] = head[s];
while (!Q.empty()) {
int u = Q.front(); Q.pop();
repE(i, u) {
int v = E[i].to;
if (dis[v] == -1 and E[i].flow) {
cur[v] = head[v];
dis[v] = dis[u] + 1;
Q.push(v);
if (v == t)return true;
}
}
}
return false;
}
int dfs(int u, int limit) {
if (u == t)return limit;
int k, res = 0;
for (int i = cur[u]; ~i and res < limit; i = E[i].next) {
int v = E[i].to;
cur[u] = i;
if (dis[v] == dis[u] + 1 and E[i].flow) {
k = dfs(v, min(limit, E[i].flow));
if (k == 0)dis[v] = -1;
E[i].flow -= k; E[i ^ 1].flow += k;
limit -= k; res += k;
}
}
return res;
}
int Dinic() {
int res = 0;
while (bfs())res += dfs(s, inf);
return res;
}
int f, d;
int main() {
scanf("%d%d%d", &n, &f, &d);
P_nums = f + d + 2 * n + 1;
memset(head, -1, sizeof(int) * (P_nums + 10));
rep(i, 1, n) {
int u = f + d + 2 * (i - 1) + 1;
addEdge(u, u + 1, 1);
int a, b, x;
scanf("%d%d", &a, &b);
rep(j, 1, a) { scanf("%d", &x); addEdge(x, u, 1); }
rep(j, 1, b) { scanf("%d", &x); addEdge(u + 1, f + x, 1); }
}
rep(i, 1, f)addEdge(0, i, 1);
rep(i, f + 1, f + d)addEdge(i, P_nums, 1);
s = 0, t = P_nums;
printf("%d
", Dinic());
}
给定正整数序列 (x_1 dots, x_n)
- 计算其最长不下降子序列的长度 (s) 。
- 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 (s) 的不下降子序列。
- 如果允许在取出的序列中多次使用 (x_1) 和 (x_n)（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个不同的长度为 (s) 的不下降子序列。
这里还是没有太吃透，有点朦胧
/*
* @Author: zhl
* @Date: 2020-10-21 15:19:08
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define repE(i,u) for(int i = head[u]; ~i; i = E[i].next)
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10, inf = 1e9;
struct Edge {
int to, next, flow;
}E[M << 1];
int head[N], tot;
void addEdge(int from, int to, int flow) {
E[tot] = Edge{ to,head[from],flow };
head[from] = tot++;
E[tot] = Edge{ from,head[to],0 };
head[to] = tot++;
}
int n, m, s, t, P_nums;
int dis[N], cur[N];
bool bfs() {
for (int i = 0; i <= P_nums; i++)dis[i] = -1;
queue<int>Q;
Q.push(s); cur[s] = head[s]; dis[s] = 0;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
repE(i, u) {
int v = E[i].to;
if (dis[v] == -1 and E[i].flow) {
dis[v] = dis[u] + 1;
cur[v] = head[v];
Q.push(v);
if (v == t)return true;
}
}
}
return false;
}
int dfs(int u, int limit) {
if (u == t)return limit;
int k, res = 0;
for (int i = cur[u]; ~i and res < limit; i = E[i].next) {
cur[u] = i;
int v = E[i].to;
if (dis[v] == dis[u] + 1 and E[i].flow) {
k = dfs(v, min(limit, E[i].flow));
if (!k)dis[v] = -1;
E[i].flow -= k; E[i ^ 1].flow += k;
limit -= k; res += k;
}
}
return res;
}
int Dinic() {
int res = 0;
while (bfs())res += dfs(s, inf);
return res;
}
int f[N], A[N];
int main() {
scanf("%d", &n);
P_nums = 2 * n + 1;
s = 0, t = 2 * n + 1;
memset(head, -1, sizeof(int) * (2 * n + 100));
rep(i, 1, n)scanf("%d", A + i);
if(n == 1){
puts("1");puts("1");puts("1");
return 0;
}
for (int i = n; i >= 1; i--) {
f[i] = 1;
for (int j = n; j > i; j--) {
if (A[i] <= A[j]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
int ans = 0;
rep(i, 1, n)ans = max(ans, f[i]);
printf("%d
", ans);
rep(i, 1, n)addEdge(i, i + n, 1);
rep(i, 1, n) {
if (f[i] == ans)addEdge(0, i, 1);
if (f[i] == 1)addEdge(i + n, 2 * n + 1, 1);
}
rep(i, 1, n) {
rep(j, i + 1, n) {
if (A[j] >= A[i] and f[j] + 1 == f[i]) {
addEdge(i + n, j, 1);
}
}
}
printf("%d
", Dinic());
memset(head, -1, sizeof(int) * (2 * n + 100));
tot = 0;
rep(i, 1, n)addEdge(i, i + n, 1);
rep(i, 1, n) {
if (f[i] == ans)addEdge(0, i, 1);
if (f[i] == 1)addEdge(i + n, 2 * n + 1, 1);
}
rep(i, 1, n) {
rep(j, i + 1, n) {
if (A[j] >= A[i] and f[j] + 1 == f[i]) {
addEdge(i + n, j, 1);
}
}
}
if(f[1] == ans){addEdge(0, 1, inf); addEdge(1, 1 + n, inf);}
if(f[n] == 1){addEdge(n, 2 * n, inf); addEdge(2 * n, 2 * n + 1, inf);}
printf("%d
", Dinic());
}
企鹅旅行
在南极附近的某个地方，一些企鹅正站在一些浮冰上。
作为群居动物，企鹅们喜欢聚在一起，因此，它们想在同一块浮冰上会合。
企鹅们不想淋湿自己，所以它们只能利用自己有限的跳跃能力，在一块块浮冰之间跳跃移动，从而聚在一起。
但是，最近的温度很高，浮冰上也有了裂纹。
每当企鹅在一块浮冰上发力跳到另一块浮冰上时，起跳的浮冰都会遭到破坏，落点的浮冰并不会因此受到影响。
当浮冰被破坏到一定程度时，浮冰就会消失。
现在已知每块浮冰可以承受的具体起跳次数。
请帮助企鹅找出它们可以会合的所有浮冰。
/*
* @Author: zhl
* @Date: 2020-10-21 16:43:14
*/
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define repE(i,u) for(int i = head[u];~i;i = E[i].next)
using namespace std;
const int N = 2e2 + 10, M = 2e6 + 10, inf = 1e9;
struct Edge {
int to, flow, next;
}E[M << 1];
int head[N], tot;
void addEdge(int from, int to, int w) {
E[tot] = Edge{ to,w,head[from] };
head[from] = tot++;
E[tot] = Edge{ from,0,head[to] };
head[to] = tot++;
}
int n, m, s, t, P_nums;//图中总点数[0-P_nums]
queue<int>Q;
int dis[N], cur[N];
bool bfs() {
rep(i, 0, P_nums)dis[i] = -1;
while (!Q.empty())Q.pop();
Q.push(s); dis[s] = 0; cur[s] = head[s];
while (!Q.empty()) {
int u = Q.front(); Q.pop();
repE(i, u) {
int v = E[i].to;
if (dis[v] == -1 and E[i].flow) {
cur[v] = head[v];
dis[v] = dis[u] + 1;
Q.push(v);
if (v == t)return true;
}
}
}
return false;
}
int dfs(int u, int limit) {
if (u == t)return limit;
int k, res = 0;
for (int i = cur[u]; ~i and res < limit; i = E[i].next) {
int v = E[i].to;
cur[u] = i;
if (dis[v] == dis[u] + 1 and E[i].flow) {
k = dfs(v, min(limit - res, E[i].flow));
if (k == 0)dis[v] = -1;
E[i].flow -= k; E[i ^ 1].flow += k;
res += k;
}
}
return res;
}
int Dinic() {
int res = 0, f;
while (bfs())while (f = dfs(s, inf)) res += f;
return res;
}
int T; double r;
int x[N], y[N], now[N], G[N];
int cal_dis(int i, int j) {
return 1.0 * (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%lf", &n, &r);
memset(head, -1, sizeof head);
tot = 0;
P_nums = 2 * n;
int sum = 0;
rep(i, 1, n) {
scanf("%d%d%d%d", x + i, y + i, now + i, G + i); sum += now[i];
addEdge(i, i + n, G[i]); addEdge(0, i, now[i]);
}
rep(i, 1, n)
rep(j, i + 1, n) {
//if (i == j)continue;
double d = cal_dis(i, j);
if (1.0 * d <= r * r) addEdge(i + n, j, inf), addEdge(j + n, i, inf);
}
int cnt = 0;
rep(i, 1, n) {
s = 0, t = i;
for (int i = 0; i < tot; i += 2) { E[i].flow += E[i ^ 1].flow; E[i ^ 1].flow = 0; }
if (Dinic() == sum) {
if (cnt)printf(" ");
printf("%d", i - 1);
cnt++;
}
}
if (!cnt)printf("-1");
puts("");
}
}
这里有个很神奇的操作
for (int i = 0; i < tot; i += 2) {
E[i].flow += E[i ^ 1].flow;
E[i ^ 1].flow = 0;
}
可以重置边的状态，不需要重新建边