再一次感觉网络流太神奇了qwq

题目链接:[星际转移问题](P4009 汽车加油行驶问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

受到之前那道[汽车加油行驶问题](P4009 汽车加油行驶问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))按汽油剩余量建图的启发,这题自然而然的就想到了按时间建图,但是怎么按时间建图又成了一个难点.

首先判断是否有解,地球与月亮联通时必定有解. 这一步可以用并查集来判断

1
2
3
4
5
6
7
8
9
DSU dsu(n + 5);
for (int i = 1; i <= m; ++ i) {
    for (auto &x : s[i]) cin >> x, ++ x;
    for (int j = 0; j < k - 1; ++ j) dsu.merge(s[i][j], s[i][j + 1]);
}
if (dsu.find(0) != dsu.find(1)) {
    cout << 0 << '\n';
    return 0;
}

由于数据范围很小,我们可以枚举时间,然后跑最大流看是否等于总人数$K$

本题的所有角色编号

  • 源点: $S$

  • 汇点: $T$

  • 地球: $1$

  • 月球: $0$

  • 空间站: $0 \backsim n+1$ $($默认地球和月球也是空间站$)$

  • 太空船: $n+2 \backsim n+1+m$

所以除开源汇点外,节点个数$cnt$为$n+m+2$,对于时间$T$对应的节点编号为$index+T \times (n+m+2)$

现在是最重要的建图环节$!!!$ 设现在枚举到时间$T$

  • 源点向$0$时刻的地球连边, $T$时刻的月球连边

    1
    2
    d.AddEdge(d.S, 1, k);
    d.AddEdge(0 + cnt * T, d.T, k);

  • 任意时刻,人都有三个选择

    1. 太空船 $\rightarrow$空间站

      1
      2
      // j时刻人从空间站到飞船
      d.AddEdge(s[i][now] + j * cnt, i + n + 1 + j * cnt, cap[i]);

    2. 空间站$\rightarrow$太空船

      1
      2
      // j时刻人从飞船到空间站
      d.AddEdge(i + n + 1 + j * cnt, s[i][now] + j * cnt, cap[i]);

    3. 停留(这个选择是最容易忽视的)太空船或空间站的部分人数从上一时刻到下一时刻不变

      这一点是受到[餐巾计划问题](P1251 餐巾计划问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))将脏抹布留到明天再洗的启发

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      for (int j = 0; j <= T; ++ j) {
          int now = j % s[i].size();
          if (j) {
              // 空间站上的人停留
              for (int p = 0; p <= n + 1; ++ p) {
                  d.AddEdge(p + (j - 1) * cnt, p + j * cnt, INF);
              }
              // 飞船上的人停留
              for (int p = n + 2; p <= n + 1 + m; ++ p) {
                  d.AddEdge(p + (j - 1) * cnt, p + j * cnt, cap[i]);
              }
          }
      }

最后判断最大流是否等于$K$结束枚举

完整代码

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 3e4 + 5, INF = 0x3f3f3f3f;
struct Edge {
    int from, to, cap, flow;

    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
    int n, m, S, T;
    vector< Edge > edges;
    vector< int > G[N];
    int d[N], cur[N];
    bool vis[N];

    Dinic(int S, int T) : S(S), T(T) {}
    
    void AddEdge(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }

    bool BFS() {
        memset(vis, false, sizeof(vis));
        queue<int> Q;
        Q.push(S);
        d[T] = 0;
        vis[S] = true;
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); ++ i) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[T];
    }

    int DFS(int x, int a) {
        if (x == T || a == 0) return a;
        int flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); ++ i) {
            Edge& e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow() {
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(S, INF);
        }
        return flow;
    }
};
struct DSU {
    vector< int > f;
    DSU(int n) : f(n) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) f[x] = y;
    }
};
int cap[25];
vector< int > s[25];
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, m, k;
    cin >> n >> m >> k;
    DSU dsu(n + 5);
    for (int i = 1; i <= m; ++ i) {
        cin >> cap[i];
        int k;
        cin >> k;
        s[i].resize(k);
        for (auto &x : s[i]) cin >> x, ++ x;
        for (int j = 0; j < k - 1; ++ j) dsu.merge(s[i][j], s[i][j + 1]);
    }
    if (dsu.find(0) != dsu.find(1)) {
        cout << 0 << '\n';
        return 0;
    }
    for (int T = 1; ; ++ T) {
        // 0 moon
        // 1 earth
        // 0~n+1 space station
        // n+2~n+1+m space ship
        int cnt = n + m + 2;
        Dinic d(cnt * (T + 1) + 1, cnt * (T + 1) + 2);
        d.AddEdge(d.S, 1, k);
        d.AddEdge(0 + cnt * T, d.T, k);
        for (int i = 1; i <= m; ++ i) {
            for (int j = 0; j <= T; ++ j) {
                int now = j % s[i].size();
                if (j) {
                    // 空间站上的人停留
                    for (int p = 0; p <= n + 1; ++ p) {
                        d.AddEdge(p + (j - 1) * cnt, p + j * cnt, INF);
                    }
                    // 飞船上的人停留
                    for (int p = n + 2; p <= n + 1 + m; ++ p) {
                        d.AddEdge(p + (j - 1) * cnt, p + j * cnt, cap[i]);
                    }
                }
                // 人从空间站到飞船
                d.AddEdge(s[i][now] + j * cnt, i + n + 1 + j * cnt, cap[i]);
                // 人从飞船到空间站
                d.AddEdge(i + n + 1 + j * cnt, s[i][now] + j * cnt, cap[i]);
            }
        }
        if (d.Maxflow() == k) {
            cout << T << '\n';
            return 0;
        }
    }
    return 0;
}

总算是把网络流24题肝完了2333