网络流 24 题 trick 记录（含代码）
Posted Updated Notes19 minutes read (About 2826 words)

网络流 24 题 trick 记录（含代码）

只要默认前面 $m$ 个都是外国的，然后剩下的都是英国的，接着暴力建图跑 Dinic 即可。
貌似只需要弄一个源点 $0$ 和汇点 $n+1$ 即可。

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
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, cnt = 1;
int head[N], dep[N];
bool vis[N];

struct Edge {
  int to, nxt, val;
} e[N];

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w;
  head[u] = cnt; return ;
}

bool check() {
  for (int i=0; i<=n+1; ++i) dep[i] = 0;
  dep[0] = 2; queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (!dep[to] && e[i].val) {
        dep[to] = dep[cur] + 1, sp.push(to);
        if (to==n+1) return true;
      }
    }
  }
  return false;
}

int dfs(int cur, int Max) {
  if (cur==n+1) return Max;
  int increase = Max;
  for (int i=head[cur]; i&&increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].val && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].val));
      e[i].val -= res, e[i^1].val += res;
      if (!res) dep[to] = 0;
      increase -= res;
    }
  }
  return Max-increase;
}

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

int main() {
  read(m), read(n);
  while (1) {
    int u, v; read(u), read(v);
    if (u==-1 && v==-1) break;
    addEdge(u, v, inf);
    addEdge(v, u, 0);
  }
  for (int i=1; i<=m; ++i)
    addEdge(0, i, 1), addEdge(i, 0, 0);
  for (int i=m+1; i<=n; ++i)
    addEdge(i, n+1, 1), addEdge(n+1, i, 0);
  int ans = 0;
  while(check()) ans += dfs(0, inf);
  cout << ans << endl;
  for (int i=2; i<=cnt; i+=2) {
    if (!e[i^1].val) continue;
    if (!e[i].to || !e[i^1].to) continue;
    if (e[i].to==n+1) continue;
    if (e[i^1].to==n+1) continue;
    printf("%d %d\n", e[i^1].to, e[i].to);
  }
  return 0;
}

这道题最重要的是连边。
那么很显然的拆点技巧，将一天拆成服务和收工两个点，即 i+N 和 i，后前两个点。
那么源点为 0，汇点为 2*N+1。

  • 要购买餐巾

显然从源点处购买，直接建边 add(0,i+N,inf,p)。

  • 偷懒先不洗餐巾

显然直接延到下一天，add(i,i+1,inf,0)。

  • 快洗

显然直接丢到 $m$ 天后，add(i,i+N+m,inf,f)。

  • 慢洗

同理丢到 $n$ 天后，add(i,i+N+n,inf,s)。

然后每一天要跑至少为 r[i] 的流量，直接源点连收工，汇点连服务。

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

nt 的地方：DFS 要标记 cur，数组不要开小。
要是写对了正解然后数组开小了那就真的是个 zz。

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 long long
using namespace std;

const int MAXN = 2e3 + 10;
const int inf = 2e9;

int N, cnt = 1, head[MAXN*12];
int p, m, f, n, s, dist[MAXN*12];
bool inq[MAXN*2], vis[MAXN*2];
int cost;

struct Edge {
  int to, nxt, flow, val;
} e[MAXN*12];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w;
  head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w;
  head[v] = cnt; return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

bool spfa() {
  for (int i=0; i<=2*N+1; ++i)
    dist[i] = inf, inq[i] = false;
  dist[0] = 0, inq[0] = true;
  queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) inq[to] = true, sp.push(to);
      }
    }
  }
  return dist[2*N+1] < inf;
}

int dfs(int cur, int Max) {
  if (cur == 2*N+1) { vis[cur] = true; return Max; }
  int increase = Max; vis[cur] = true;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to] || to==MAXN) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      cost += res * e[i].val, increase -= res;
    }
  }
  return Max-increase;
}

signed main() {
  cin >> N;
  for (int i=1; i<=N; ++i) {
    int r; cin >> r;
    addEdge(0, i, r, 0);
    addEdge(i+N, 2*N+1, r, 0);
  }
  cin >> p >> m >> f >> n >> s;
  // begin point: i
  // ending point: i+N
  for (int i=1; i<=N; ++i) {
    addEdge(0, i+N, inf, p);
    if (i<N) addEdge(i, i+1, inf, 0);
    if (i+m<=N) addEdge(i, i+N+m, inf, f);
    if (i+n<=N) addEdge(i, i+N+n, inf, s);
  }
  while (spfa()) {
    for (int i=0; i<=2*N+1; ++i) vis[i] = false;
    dfs(0, inf);
  }
  cout << cost << endl;
  return 0;
}

这道题为什么要网络流啊。

难道不是直接暴力 BFS 寻找路径吗？

直接状压一下钥匙，然后每一次到达门就看有没有钥匙就可以了。

nt 的地方：x(x), y(y) 写成了 x(x), y(x) … …

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
#include <bits/stdc++.h>
using namespace std;

const int N = 11;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, p, k, s, door[N][N][N][N];
int cnt[N][N], key[N][N][N];
bool vis[N][N][1<<N];

struct spread {
  int x, y, Key, cost;
  spread(int x, int y, int Key, int cost):
    x(x), y(y), Key(Key), cost(cost) {}
  spread() {}
};

int keyset(int x, int y) {
  int S = 0;
  for (int i=1; i<=cnt[x][y]; ++i)
    S |= (1<<(key[x][y][i]-1));
  return S;
}

bool check(int x, int y, int k, int st) {
  if (x<1 || x>n) return false;
  if (y<1 || y>m) return false;
  if (k<0 || (k && !(st&(1<<(k-1))))) return false;
  return true;
}

int bfs() {
  int x = 1, y = 1;
  int S = keyset(x, y);
  queue <spread> que; que.push(spread(x, y, S, 0));
  vis[x][y][S] = true;
  while (!que.empty()) {
    spread cur = que.front(); que.pop();
    x = cur.x, y = cur.y, S = cur.Key;
    if (x==n && y==m) return cur.cost;
    for (int i=0; i<4; ++i) {
      int tox = x + dx[i], toy = y + dy[i];
      int Door = door[x][y][tox][toy];
      if (!check(tox, toy, Door, S)) continue;
      int to = S|keyset(tox, toy);
      if (vis[tox][toy][to]) continue;
      vis[tox][toy][to] = true;
      que.push(spread(tox, toy, to, cur.cost+1));
    }
  }
  return -1;
}

int main() {
  cin >> n >> m >> p >> k;
  while (k--) {
    int x, y, X, Y, G;
    cin >> x >> y >> X >> Y >> G;
    if (G) door[x][y][X][Y] = door[X][Y][x][y] = G;
    else door[x][y][X][Y] = door[X][Y][x][y] = -1;
  }
  cin >> s;
  while (s--) {
    int x, y, Q; cin >> x >> y >> Q;
    key[x][y][++cnt[x][y]] = Q;
  }
  cout << bfs() << endl;
  return 0;
}

众所周知最小路径覆盖 $=$ 顶点数 $-$ 最大匹配数，这个是很显然的。

Proof：因为对于每一个点一开始都可以作为一条路径，所以一开始就有 $n$ 条路径。因为每一次匹配相当于把两个点合并，所以路径条数相当于减掉了 $1$，所以最大匹配数就是合并的个数，所以最后就是 $n-$最大匹配数。
又因为二分图可以网络流乱搞，所以路径覆盖也可以网络流乱搞。

所以正常的 trick，拆点跑最大流。
路径输出比较正常，直接在 DFS 的时候找到起始点然后记录路径即可。

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
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
const int inf = 1e9;

int n, m, s, t, cnt = 1;
int dep[N], head[N]; bool inq[N];
int cost, path[N]; bool vis[N];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].flow = f; head[u] = cnt;

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0; head[v] = cnt;
  return ;
}

bool check() {
  for (int i=0; i<=t; ++i)
    dep[i] = inf, inq[i] = false;
  dep[s] = 0; queue <int> sp;
  sp.push(s); inq[s] = true;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t] ^ inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) { dep[to] = -1; continue; }
      e[i].flow -=  res, e[i^1].flow += res;
      path[cur] = to; if (cur) vis[to-n] = true;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  cin >> n >> m; t = 2*n+1;
  for (int i=1; i<=m; ++i) {
    int u, v; cin >> u >> v;
    addEdge(u, n+v, 1);
  }
  for (int i=1; i<=n; ++i) addEdge(s, i, 1);
  for (int i=1; i<=n; ++i) addEdge(i+n, t, 1);
  int ans = 0; while (check()) ans += dfs(s, inf);
  for (int i=1; i<=n; ++i) {
    if (vis[i]) continue;
    int cur = i; cout << i;
    while(path[cur] && path[cur]^t)
      cout << ' ' << path[cur]-n, cur = path[cur]-n;
    cout << endl;
  }
  cout << n-ans << endl;
  return 0;
}

听名字还挺高大上的。

其实就是个卡牌游戏啊，只不过每一次只可以交换环上相邻两个。
那么直接断环成链，拿原数减掉最后的固定答案然后前缀和加到 ans。

顺带卡了下常，12ms 最优解 Rank1。

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
#include <stdio.h>
int n, sum, ans, a[110], Sum[110];

int abs(int x) { return x>0? x:-x; }

void qsort(int l, int r) {
  int mid = Sum[(l+r)>>1];
  int i=l, j=r;
  do {
    while (Sum[i]<mid) ++i;
    while (Sum[j]>mid) --j;
    if(i<=j) {
      int u=Sum[i]; Sum[i]=Sum[j]; Sum[j]=u;
      i++, j--;
    }
  } while (i<=j);
  if (l<j) qsort(l, j);
  if (i<r) qsort(i, r);
  return ;
}

int main() {
  scanf("%d", &n);
  for (int i=1; i<=n; ++i)
    scanf("%d", &a[i]), sum += a[i];
  sum /= n;
  for (int i=1; i<=n; ++i)
    Sum[i] = Sum[i-1]+a[i]-sum, a[i] = Sum[i];
  qsort(1, n); int mid = n/2+1;
  for (int i=1; i<=n; ++i)
    ans += abs(Sum[mid]-Sum[i]);
  printf("%d\n", ans);
  return 0;
}

简单题。

首先看到点有限制，直接拆点。

那么因为没有给出单源点和汇点，分别建一个。

接着可以将 * 视为连向源点，所以边权为 $1$。
同理 # 视为连向汇点，边权为限制 $p$。

然后因为 . 只能踩一次，所以拆成两个点，两个点之间的限制为 $1$。
@ 可以踩无数次，所以连 INF。

接着因为周边四个点都可以扩展到（除起始点和水显然不可以扩展）。
所以连容量为 INF 的边。

然后跑一遍最大流。

记得多测 cnt 要赋成 $1$ 而不是 $0$。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, p, s, t, cnt = 1;
int dep[N], head[N]; char ch[40][40];

struct Edge {
  int to, nxt, flow;
} e[N];

void addEdge(int u, int v, int f) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, head[v] = cnt;
}

bool check(int x, int y) {
  return x<1 || x>n || y<1 || y>m;
}

void init() {
  cnt = 1; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) cin >> ch[i][j];
  memset(head, -1, sizeof head);
  return ;
}

int id(int x, int y) { return (x-1)*m+y; }
bool spfa() {
  for (int i=s; i<=t; ++i) dep[i] = inf;
  dep[s] = 0; queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t]^inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  while (scanf("%d%d%d", &n, &m, &p) != EOF) {
    init(); int siz = n*m;
    for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
        if (ch[i][j] == '~') continue;
        if (ch[i][j] == '*') addEdge(s, id(i,j), 1);
        if (ch[i][j] == '.') addEdge(id(i,j), id(i,j)+siz, 1);
        if (ch[i][j] == '#') addEdge(id(i,j), t, p);
        for (int k=0; k<4; ++k) {
          int tox = i+dx[k], toy = j+dy[k];
          if (check(tox, toy)) continue;
          if (ch[tox][toy] == '*' || ch[tox][toy] == '~') continue;
          if (ch[i][j] == '.') addEdge(id(i,j)+siz, id(tox, toy), inf);
          else addEdge(id(i,j), id(tox, toy), inf);
        }
      }
    }
    int ans = 0;
    while (spfa()) ans += dfs(s, inf);
    cout << ans << endl;
  }
  return 0;
}

这题也是个拆点模板。
首先 S 连向出点，T 连向入点，默认已经拆完点。
所以因为要使得成为循环格，所以要进行两两之间点的匹配。
即入度、出度均为 $1$。

所以跑二分图匹配最小费用即可。
建边的 value 只需要看当前点实际指的方向是否是枚举的方向。
如果是费用为 $0$，否则为 $1$。

最后要注意：cnt 要赋成 $1$！！11

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int inf = 114514;

int n, m, s, t, cnt = 1, cost;
int dist[N], head[N];
bool vis[N], inq[N];
char Map[20][20]; int To[20][20];

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

struct Edge {
  int to, nxt, flow, val;
} e[N];

void addEdge(int u, int v, int f, int w) {
  e[++cnt].to = v, e[cnt].nxt = head[u];
  e[cnt].flow = f, e[cnt].val = w, head[u] = cnt;
  e[++cnt].to = u, e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w, head[v] = cnt;
  return ;
}

bool spfa() {
  for (int i=s; i<=t; ++i)
    inq[i] = false, dist[i] = inf;
  dist[s] = 0, inq[s] = true;
  queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) { inq[to] = true; sp.push(to); }
      }
    }
  }
  return dist[t]^inf;
}

int dfs(int cur, int Max) {
  vis[cur] = true;
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to]||to==t) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res, cost += res * e[i].val;
    }
  }
  return Max-increase;
}

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

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      cin >> Map[i][j];
      if (Map[i][j]=='L') To[i][j] = 0;
      if (Map[i][j]=='R') To[i][j] = 1;
      if (Map[i][j]=='U') To[i][j] = 2;
      if (Map[i][j]=='D') To[i][j] = 3;
    }
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      for (int k=0; k<4; ++k) {
        int tox = i+dx[k], toy = j+dy[k];
        if (tox<1) tox = n; if (tox>n) tox = 1;
        if (toy<1) toy = m; if (toy>m) toy = 1;
        addEdge(id(i,j)+n*m, id(tox, toy), 1, k!=To[i][j]);
      }
    }
  }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      addEdge(s, id(i,j)+n*m, 1, 0);
      addEdge(id(i,j), t, 1, 0);
    }
  int ans = 0;
  while (spfa()) {
    for (int i=s; i<=t; ++i) vis[i] = false;
    ans += dfs(s, inf);
  }
  cout << cost << endl;
  return 0;
}
Follow

Links

Categories

Recents

Archives

Tags

DS5
Graph1
Math1
Network Flows1
Number Theory2
Others2
State Compression1

Subscribe for updates

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×