网络流

1. 最大匹配 = 最小点覆盖。

2. 最小割 = 最大匹配

3. 二分图最大独立集 = 点数 - 最大匹配。

4. 二分图最大团 = 补图最大独立集。

5. DAG 最小链覆盖 = n - 拆点后二分图最大匹配。

6. 最大权闭合子图 = 正权和 - 最小割

网络流 24 题

这个其实不是网络流…

直接设 kik_i 表示 ii 向 i+1i + 1 搬运量，然后可以得出等式 ki+ai−1−ai=avgk_i+a_{i-1}-a_i=avg，推下式子即可。

时间复杂度：O(nlog⁡n)O(n\log n)。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 105;

int n;
int a[kMaxN], c[kMaxN];

void dickdreamer() {
  std::cin >> n;
  int sum = 0, avg;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    sum += a[i];
  }
  avg = sum / n;
  std::vector<int> v = {0};
  int sc = 0;
  for (int i = 2; i <= n; ++i) {
    c[i] = a[i] - avg;
    sc += c[i];
    v.emplace_back(sc);
  }
  std::sort(v.begin(), v.end());
  int x = v[v.size() / 2], ans = 0;
  for (auto y : v)
    ans += abs(y - x);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

二分图最大匹配板子。

直接把试题放左边，类型放右边，让每个试题与它所属的类型连一条流量为 11 的边，源点向每个试题连流量为 11 的边，每个类型向汇点连流量为它所需个数的边，跑最大流即可。

输出方案就在残余网络上找满流的边即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e3 + 5, kMaxM = 3e4 + 5, kInf = 0x3f3f3f3f;

struct Edge {
  int v, w, pre;
} e[kMaxM];

int k, n, m, s, t, tot = 1;
int tail[kMaxN], cur[kMaxN], idx[kMaxN][kMaxN], dep[kMaxN];
bool vis[kMaxN];

void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = idx[u][v] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }

bool bfs() {
  for (int i = 1; i <= t; ++i)
    cur[i] = tail[i], vis[i] = 0, dep[i] = kInf;
  std::queue<int> q;
  q.emplace(s), dep[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v;
      if (!e[i].w || vis[v]) continue;
      dep[v] = dep[u] + 1, q.emplace(v), vis[v] = 1;
    }
  }
  return vis[t];
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = kInf;
      e[i].w -= fl, e[i ^ 1].w += fl;
      lim -= fl, flow += fl;
      if (!lim) break;
    }
  }
  return flow;
}

void dickdreamer() {
  std::cin >> k >> n;
  s = n + k + 1, t = n + k + 2;
  for (int i = 1; i <= k; ++i) {
    int x;
    std::cin >> x;
    add(i + n, t, x);
    m += x;
  }
  for (int i = 1; i <= n; ++i) {
    int p, x;
    std::cin >> p;
    for (; p; --p) {
      std::cin >> x;
      add(i, x + n, kInf);
    }
    add(s, i, 1);
  }
  int ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  if (ans < m) {
    std::cout << "No Solution!\n";
    return;
  }
  for (int i = 1; i <= k; ++i) {
    std::cout << i << ": ";
    for (int j = 1; j <= n; ++j)
      if (e[idx[i + n][j]].w)
        std::cout << j << ' ';
    std::cout << '\n';
  }
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

费用流板子

每个代表向每个餐桌连流量为 11 的边然后跑最大流即可。

最大权闭合子图板子。

考虑让答案为总和-最小割。

源点向所有实验 ii 连流量为其奖金的边，实验 ii 向它所有所需仪器连流量为 +∞+\infty 表示不能断这条边，然后仪器 jj 向汇点连流量为其费用的边。

那么由于断不了中间的边，所以对于实验 ii，要让它不连通，要么断掉源点连它的边，表示不做这个实验。要么断掉它所有所需仪器向汇点连的边，表示要买这些仪器。

会发现答案 = 奖金和 - 左边割 - 右边割 = 奖金和 - 最小割。

跑最大流即可。

输出方案就找在残余网络上和源点连通的实验说明它没割，和源点连通的仪器说明割了。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 105, kMaxM = 1e5 + 5, kInf = 1e9;

struct Edge {
  int v, w, pre;
} e[kMaxM];

int n, m, s, t, sum, tot = 1;
int tail[kMaxN], cur[kMaxN], idx[kMaxN][kMaxN], dep[kMaxN];
bool vis[kMaxN];

void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = idx[u][v] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }

bool bfs() {
  for (int i = 1; i <= t; ++i)
    cur[i] = tail[i], vis[i] = 0, dep[i] = kInf;
  std::queue<int> q;
  q.emplace(s), dep[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v;
      if (!e[i].w || vis[v]) continue;
      dep[v] = dep[u] + 1, q.emplace(v), vis[v] = 1;
    }
  }
  return vis[t];
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = kInf;
      e[i].w -= fl, e[i ^ 1].w += fl;
      lim -= fl, flow += fl;
      if (!lim) break;
    }
  }
  return flow;
}

void dickdreamer() {
  std::cin >> n >> m;
  s = n + m + 1, t = n + m + 2;
  for (int i = 1; i <= n; ++i) {
    int num = 0, fl = 0;
    std::string str;
    getline(std::cin, str);
    while (!str.size()) getline(std::cin, str);
    str += '\n';
    for (auto c : str) {
      if (isdigit(c)) {
        num = 10 * num + c - '0';
      } else {
        if (!fl) add(s, i, num), sum += num, fl = 1;
        else add(i, num + n, kInf);
        num = 0;
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    int val;
    std::cin >> val;
    add(i + n, t, val);
  }
  int ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  for (int i = 1; i <= n; ++i)
    if (dep[i] <= t)
      std::cout << i << ' ';
  std::cout << '\n';
  for (int i = 1; i <= m; ++i)
    if (dep[i + n] <= t)
      std::cout << i << ' ';
  std::cout << '\n' << sum - ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

最大独立集板子。

观察可知对棋盘黑白染色后，两个可以互相吃掉的马颜色一定不同，所以把黑的放左边，白的放右边，能互相吃掉的就连边，答案就是 n2−m−最大流n^2-m-最大流。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 4e4 + 5, kMaxM = 1e6 + 5, kInf = 1e9;
const int kD[][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

struct Edge {
  int v, w, pre;
} e[kMaxM];

int n, m, s, t, tot = 1;
int cnt[2], idx[205][205], tail[kMaxN], cur[kMaxN], dep[kMaxN];
bool ob[205][205], vis[kMaxN];

void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }

bool bfs() {
  std::queue<int> q;
  for (int i = 1; i <= t; ++i)
    vis[i] = 0, dep[i] = kInf, cur[i] = tail[i];
  q.emplace(s), dep[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v;
      if (!e[i].w || vis[v]) continue;
      vis[v] = 1, dep[v] = dep[u] + 1, q.emplace(v);
    }
  }
  return vis[t];
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = kInf;
      e[i].w -= fl, e[i ^ 1].w += fl;
      lim -= fl, flow += fl;
      if (!lim) break;
    }
  }
  return flow;
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int x, y;
    std::cin >> x >> y;
    ob[x][y] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (ob[i][j]) continue;
      idx[i][j] = ++cnt[(i + j) & 1];
    }
  }
  s = cnt[0] + cnt[1] + 1, t = cnt[0] + cnt[1] + 2;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (ob[i][j]) continue;
      if ((i + j) & 1) idx[i][j] += cnt[0];
    }
  }
  for (int i = 1; i <= cnt[0]; ++i)
    add(s, i, 1);
  for (int i = 1; i <= cnt[1]; ++i)
    add(i + cnt[0], t, 1);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (ob[i][j] || ((i + j) & 1)) continue;
      for (auto [dx, dy] : kD) {
        int ti = i + dx, tj = j + dy;
        if (ti < 1 || ti > n || tj < 1 || tj > n || ob[ti][tj]) continue;
        add(idx[i][j], idx[ti][tj], 1);
      }
    }
  }
  int ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  std::cout << cnt[0] + cnt[1] - ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

考虑黑白染色，然后把相邻的点连一条流量为 +∞+\infty 的边，然后源点向黑点连流量为其权值的边，白点向汇点也连流量为其权值的边。

然后答案就是总和 - 最小割。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e4 + 5, kMaxM = 1e5 + 5, kInf = 1e9;
const int kD[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

struct Edge {
  int v, w, pre;
} e[kMaxM];

int n, m, s, t, sum, tot = 1;
int cnt[2], a[105][105], idx[105][105];
int tail[kMaxN], cur[kMaxN], dep[kMaxN];
bool vis[kMaxN];

int getid(int x, int y) {
  return (x - 1) * m + y;
}

void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }

bool bfs() {
  std::queue<int> q;
  for (int i = 1; i <= t; ++i)
    vis[i] = 0, dep[i] = kInf, cur[i] = tail[i];
  q.emplace(s), dep[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v;
      if (!e[i].w || vis[v]) continue;
      vis[v] = 1, dep[v] = dep[u] + 1, q.emplace(v);
    }
  }
  return vis[t];
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = kInf;
      e[i].w -= fl, e[i ^ 1].w += fl;
      lim -= fl, flow += fl;
      if (!lim) break;
    }
  }
  return flow;
}

void dickdreamer() {
  std::cin >> n >> m;
  s = n * m + 1, t = n * m + 2;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      std::cin >> a[i][j];
      sum += a[i][j];
      if ((i + j) & 1) add(s, getid(i, j), a[i][j]);
      else add(getid(i, j), t, a[i][j]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (!((i + j) & 1)) continue;
      for (auto [dx, dy] : kD) {
        int ti = i + dx, tj = j + dy;
        if (ti < 1 || ti > n || tj < 1 || tj > m) continue;
        add(getid(i, j), getid(ti, tj), kInf);
      }
    }
  }
  int ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  std::cout << sum - ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

第一问直接 DP。

对于第二问，设 fif_{i} 表示以 ii 开头的最长不下降子序列，那么如果 j>ij>i 并且 aj≥ai,fj=fi−1a_j\geq a_i,f_j=f_i-1 就连一条从 ii 到 jj 的边，容易发现形成了一张 DAG。

定义一个合法的链表示 f起点=mx,f终点=1f_{起点}=mx,f_{终点}=1，原题就转化为问能把 DAG 划分为最多多少条互不相交的链。

考虑把由于每个点最多出现 11 次，那么就把每个点拆成入点和出点，入点向出点连一条长度为 11 的边，如果有一条 i→ji\to j 的边，就连一条出点 ii 到入点 jj 的流量为 11 的边。

然后源点向 fi=mxf_i=mx 的入点 ii 连一条流量为 11 的边，表示可以从这里开始。fj=1f_j=1 的出点 jj 向汇点连一条流量为 11 的边，表示可以从这里结束。

跑最大流就是答案。

对于第三问直接把源点向入点 11、入点 11 向出点 11、入点 nn 向出点 nn 和出点 nn 向汇点的流量改成 +∞+\infty 再跑最大流即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1005, kMaxM = 1e6 + 5, kInf = 1e9;

struct Edge {
  int v, w, pre;
} e[kMaxM];

int n, s, t, tot = 1;
int a[kMaxN], f[kMaxN];
int tail[kMaxN], cur[kMaxN], dep[kMaxN];
bool vis[kMaxN];

void init() {
  tot = 1;
  memset(tail, 0, sizeof(tail));
}

void adde(int u, int v, int w) { e[++tot] = {v, w, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w) { adde(u, v, w), adde(v, u, 0); }

bool bfs() {
  std::queue<int> q;
  for (int i = 1; i <= t; ++i)
    vis[i] = 0, dep[i] = kInf, cur[i] = tail[i];
  q.emplace(s), dep[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v;
      if (!e[i].w || vis[v]) continue;
      vis[v] = 1, dep[v] = dep[u] + 1, q.emplace(v);
    }
  }
  return vis[t];
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = kInf;
      e[i].w -= fl, e[i ^ 1].w += fl;
      lim -= fl, flow += fl;
      if (!lim) break;
    }
  }
  return flow;
}

void dickdreamer() {
  std::cin >> n;
  s = 2 * n + 1, t = 2 * n + 2;
  for (int i = 1; i <= n; ++i)
    std::cin >> a[i];
  if (n == 1) { std::cout << "1\n1\n1\n"; return; }
  int mx = 0;
  for (int i = n; i; --i) {
    f[i] = 1;
    for (int j = i + 1; j <= n; ++j) {
      if (a[j] >= a[i] && f[j] + 1 > f[i])
        f[i] = f[j] + 1;
    }
    mx = std::max(mx, f[i]);
  }
  std::cout << mx << '\n';
  for (int i = 1; i <= n; ++i) {
    if (f[i] == mx) add(s, i, 1);
    if (f[i] == 1) add(i + n, t, 1);
    add(i, i + n, 1);
    for (int j = i + 1; j <= n; ++j)
      if (a[j] >= a[i] && f[j] + 1 == f[i])
        add(i + n, j, 1);
  }
  int ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  std::cout << ans << '\n';
  init();
  for (int i = 1; i <= n; ++i) {
    if (f[i] == mx) add(s, i, (i == 1 ? kInf : 1));
    if (f[i] == 1) add(i + n, t, (i == n ? kInf : 1));
    add(i, i + n, (i == 1 || i == n) ? kInf : 1);
    for (int j = i + 1; j <= n; ++j)
      if (a[j] >= a[i] && f[j] + 1 == f[i])
        add(i + n, j, 1);
  }
  ans = 0;
  for (; bfs(); ans += dfs(s, kInf)) {}
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

考虑费用流，然后把每天拆成早上和晚上。

早上表示当天所有的干净餐巾，晚上表示当天所有的脏餐巾。

为了保证每天都有足够的餐巾，就要让早上 ii 向汇点连一条流量为 rir_i 的边，那么这样的话流量就少了 rir_i，考虑从源点向晚上 ii 连一条流量为 rir_i 且费用为 00 的边，补上丢失的流量，可以理解为顾客把 rir_i 个脏餐巾还给了饭店。

然后就让早上 ii 向早上 i+1i+1 连一条流量为 +∞+\infty 费用为 00 的边表示今天没用的餐巾可以留到明天用。晚上 ii 向晚上 i+1i+1 连一条流量 +∞+\infty 费用为 00 的边表示这些餐巾可以延迟送洗。

源点向早上 ii 连一条流量为 +∞+\infty 费用为 pp 的边，表示可以买新餐巾。晚上 ii 向早上 i+mi+m 连一条流量为 +∞+\infty 费用为 ff 的边，表示可以把脏餐巾送到快洗店。同理，晚上 ii 向早上 i+ni+n 连一条流量为 +∞+\infty 费用为 ss 的边，表示可以把脏餐巾送到慢洗店。

然后跑最小费用最大流即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e4 + 5, kMaxM = 1e5 + 5, kInf = 1e9;

struct Edge {
  int v, flow, cost, pre;
} e[kMaxM];

int n, s, t, tot = 1, ans;
int _p, _m, _f, _n, _s, r[kMaxN];
int tail[kMaxN], cur[kMaxN], dis[kMaxN];
bool inq[kMaxN], vis[kMaxN];

int getid(int x, int op) { // 0 : 早, 1 : 晚
  return x + op * n;
}

void adde(int u, int v, int f, int c) { e[++tot] = {v, f, c, tail[u]}, tail[u] = tot; }
void add(int u, int v, int f, int c) { adde(u, v, f, c), adde(v, u, 0, -c); }

bool spfa() {
  for (int i = 1; i <= t; ++i) {
    inq[i] = vis[i] = 0;
    cur[i] = tail[i];
    dis[i] = kInf;
  }
  std::queue<int> q;
  q.emplace(s), dis[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v, w = e[i].cost, f = e[i].flow;
      if (!f) continue;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) q.emplace(v), vis[v] = 1;
      }
    }
  }
  return dis[t] != kInf;
}

int dfs(int u, int lim) {
  if (u == t || !lim) {
    ans += dis[t] * lim;
    return lim;
  }
  vis[u] = 1;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v;
    if (dis[v] == dis[u] + e[i].cost && e[i].flow && !vis[v]) {
      int fl = dfs(v, std::min(lim, e[i].flow));
      e[i].flow -= fl, e[i ^ 1].flow += fl;
      flow += fl, lim -= fl;
      if (!lim) break;
    }
  }
  vis[u] = 0;
  return flow;
}

void dickdreamer() {
  std::cin >> n;
  s = 2 * n + 1, t = 2 * n + 2;
  for (int i = 1; i <= n; ++i) {
    std::cin >> r[i];
    add(s, getid(i, 1), r[i], 0);
    add(getid(i, 0), t, r[i], 0);
    if (i < n) {
      add(getid(i, 0), getid(i + 1, 0), kInf, 0);
      add(getid(i, 1), getid(i + 1, 1), kInf, 0);
    }
  }
  std::cin >> _p >> _m >> _f >> _n >> _s;
  for (int i = 1; i <= n; ++i) {
    add(s, getid(i, 0), kInf, _p);
    if (i <= n - _m) add(getid(i, 1), getid(i + _m, 0), kInf, _f);
    if (i <= n - _n) add(getid(i, 1), getid(i + _n, 0), kInf, _s);
  }
  for (; spfa(); dfs(s, kInf)) {}
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

原题可以转化为找两条点数最多的从 11 到 nn 从小到大走的路径，且这两条路径除了 11 和 nn，其余点不交。

套路拆点，然后最大流钦定找到 22 跳路径，最大费用用来找到尽可能多的点。

入点向出点连一条 (1,1)(1,1) 的边，特别的 11 和 nn 是 (2,1)(2,1)。

然后如果 uu 和 vv 有边，那么就出点 uu 和入点 vv 连一条 (1,0)(1, 0) 的边。

然后源点向入点 11 连一条 (2,0)(2, 0) 的边，出点 nn 向汇点也连 (2,0)(2,0) 的边，表示要找到两条合法路径。

然后跑最大费用最大流。

容易发现总点数是最大费用 - 2。

输出方案就在残余网络上找，如果 (出u,入v)(出u,入v) 满流了，就说明走了 (u,v)(u,v) 这条路径。

于是直接 dfs 两遍即可。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 205, kMaxM = 1e5 + 5, kInf = 1e9;

struct Edge {
  int v, flow, cost, pre;
} e[kMaxM];

int n, m, s, t, tot = 1;
int tail[kMaxN], cur[kMaxN], dis[kMaxN], ed[kMaxN][kMaxN];
std::string name[kMaxN];
bool vis[kMaxN];
std::map<std::string, int> idx;
std::vector<int> v[2];

void adde(int u, int v, int f, int c) { e[++tot] = {v, f, c, tail[u]}, tail[u] = tot, ed[u][v] = tot; }
void add(int u, int v, int f, int c) { adde(u, v, f, c), adde(v, u, 0, -c); }

bool spfa() {
  for (int i = 1; i <= t; ++i) {
    vis[i] = 0, dis[i] = -kInf, cur[i] = tail[i];
  }
  std::queue<int> q;
  q.emplace(s), dis[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v, w = e[i].cost, f = e[i].flow;
      if (!f) continue;
      if (dis[v] < dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) q.emplace(v), vis[v] = 1;
      }
    }
  }
  return dis[t] != -kInf;
}

int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  vis[u] = 1;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v;
    if (dis[v] == dis[u] + e[i].cost && e[i].flow && !vis[v]) {
      int fl = dfs(v, std::min(lim, e[i].flow));
      if (!fl) dis[v] = kInf;
      e[i].flow -= fl, e[i ^ 1].flow += fl;
      flow += fl, lim -= fl;
      if (!lim) break;
    }
  }
  vis[u] = 0;
  return flow;
}

bool check(int u, int v) {
  return e[ed[u][v + n] ^ 1].flow;
}

void _dfs(int u, int o) {
  if (u == n) return;
  v[o].emplace_back(u);
  vis[u] = 1;
  for (int i = u + 1; i <= n; ++i) {
    if (!vis[i] && check(u, i)) {
      return _dfs(i, o);
    }
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  s = 2 * n + 1, t = 2 * n + 2;
  for (int i = 1; i <= n; ++i) {
    std::string str;
    std::cin >> str;
    name[i] = str;
    idx[str] = i;
    add(i + n, i, 1 + (i == n), 1);
  }
  for (int i = 1; i <= m; ++i) {
    std::string s, t;
    int u, v;
    std::cin >> s >> t;
    u = idx[s], v = idx[t];
    if (u > v) std::swap(u, v);
    add(u, v + n, kInf, 0);
  }
  add(s, 1, 2, 0), add(n, t, 2, 0);
  int flow = 0;
  for (; spfa(); flow += dfs(s, kInf)) {}
  if (flow < 2) {
    std::cout << "No Solution!\n";
    return;
  }
  assert(flow == 2);
  memset(vis, 0, sizeof(vis));
  _dfs(1, 0), _dfs(1, 1);
  std::reverse(v[1].begin(), v[1].end());
  std::cout << v[0].size() + v[1].size() << '\n';
  for (auto x : v[0]) std::cout << name[x] << '\n';
  std::cout << name[n] << '\n';
  for (auto x : v[1]) std::cout << name[x] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}
网络流
https://sobaliuziao.github.io/2023/09/16/post/89b04f08.html
作者
Egg_laying_master
发布于
2023年9月16日
许可协议