yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P2762 太空飞行计划问题

发表于 更新于 分类于

P2762 太空飞行计划问题

题面

题目链接

解法

坑来坑去最后被读入给坑到了。

使用割模型，从源点连边到实验，流量为该实验可获得的钱$p_i$，再从仪器连边道汇点，流量为该仪器的价格$c_i$，最后将实验和仪器之间连边，流量为$+\infty$。

思考这种连边方式的含义。最小割后的残余网络中，与源点相连的点都是要取的，与汇点相连的点都是不取的，分别对应$S$集合和$T$集合。原网络所代表的状态是$m$个实验都做，但这显然是不合法的，所以跑一遍最小割后，就能保证不出现实验在$S$集合而对应仪器在$T$集合中的情况（因为无法割断实验和仪器之间的连边），需要注意的是，实验在$T$集合而对应仪器在$S$集合的方案是合法的。而所求的最小割就是使得方案合法的最小代价。

于是答案为$\sum\limits_{i=1}^{m}{p_i} - mincut$。

恶心的读入

因为不喜欢用cin所以研究如何用scanf优雅地读入整行，于是发现：

  • scanf("%[^\n]", buf)可以读入整行，其中buf是char数组。

所以用buf进行手写快读，代码如下：

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
/**
 * 从字符串`s`中读入数字到`x`，并返回`s`中当前数字下一位的指针
*/
template <class _Tp>
inline char* sread(char *s, _Tp &x) {
    bool sign = false;
    char ch = *s++;
    long double tmp = 1;
    for (; !isdigit(ch); ch = *s++)
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = *s++)
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = *s++; isdigit(ch); ch = *s++)
            tmp /= 10.0, x += tmp * (ch ^ 48);
    if (sign)
        x = -x;
    return --s; // 返回上一个位置的原因是快读会判断数字后一位并且将指针`s`移到数字后两位，这样无法判断字符串结束`'\0'`
}
signed main() {
    read(m), read(n);
    for (int i = 1; i <= m; ++i) {
        read(p[i]);
        scanf("%[^\n]%c", buf, &chr);
        char *pos = buf;
        for (k[i] = 0; (*pos) && ++k[i];)
            pos = sread(pos, a[i][k[i]]);
    }
    for (int i = 1; i <= n; ++i)
        read(c[i]);
    // ...
    return 0;
}

AC代码

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
143
144
145
146
147
148
149
150
151
152
/**
 * @file:           P2762.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P2762
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
template <class _Tp>
inline _Tp& read(_Tp &x) {
    bool sign = false;
    char ch = getchar();
    long double tmp = 1;
    for (; !isdigit(ch); ch = getchar())
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getchar())
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = getchar(); isdigit(ch); ch = getchar())
            tmp /= 10.0, x += tmp * (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline char* sread(char *s, _Tp &x) {
    bool sign = false;
    char ch = *s++;
    long double tmp = 1;
    for (; !isdigit(ch); ch = *s++)
        sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = *s++)
        x = x * 10 + (ch ^ 48);
    if (ch == '.')
        for (ch = *s++; isdigit(ch); ch = *s++)
            tmp /= 10.0, x += tmp * (ch ^ 48);
    if (sign)
        x = -x;
    return --s;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar((x % 10) ^ 48);
}
const int MAXN = 150;
const int MAXM = 3e4 + 10;
const int MAXS = 1 << 15;
const int INF = 0x3f3f3f3f3f3f3f3f;
struct Dinic {
    struct Edge {
        int v, flow;
    } edge[MAXM];
    int tot = 1, flow = 0;
    int head[MAXN], nxt[MAXM], lev[MAXN], cur[MAXN];
    void addedge(int u, int v, int flow) {
        edge[++tot] = {v, flow};
        nxt[tot] = head[u], head[u] = tot;
        edge[++tot] = {u, 0};
        nxt[tot] = head[v], head[v] = tot;
    }
    bool bfs(int s, int t) {
        memset(lev, -1, sizeof(lev));
        queue<int> que;
        que.push(s);
        lev[s] = 0;
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int i = head[u]; i; i = nxt[i]) {
                int v = edge[i].v;
                if (edge[i].flow && lev[v] == -1) {
                    lev[v] = lev[u] + 1;
                    que.push(v);
                }
            }
        }
        return lev[t] != -1;
    }
    int augment(int u, int t, int mx) {
        if (u == t || mx == 0)
            return mx;
        int ret = 0;
        for (int &i = cur[u]; i; i = nxt[i]) {
            int v = edge[i].v;
            if (lev[v] != lev[u] + 1)
                continue;
            int tmp = augment(v, t, min(mx, edge[i].flow));
            mx -= tmp, ret += tmp;
            edge[i].flow -= tmp, edge[i ^ 1].flow += tmp;
            if (mx == 0)
                break;
        }
        return ret;
    }
    int maxflow(int s, int t) {
        while (bfs(s, t)) {
            memcpy(cur, head, sizeof(cur));
            flow += augment(s, t, INF);
        }
        return flow;
    }
};
int n, m, p[MAXN], c[MAXN], k[MAXN], a[MAXN][MAXN];
char chr, buf[MAXS];
bool use1[MAXN], use2[MAXN];
vector<int> ans1, ans2;
Dinic mincut;
signed main() {
    read(m), read(n);
    for (int i = 1; i <= m; ++i) {
        read(p[i]);
        scanf("%[^\n]%c", buf, &chr);
        char *pos = buf;
        for (k[i] = 0; (*pos) && ++k[i];)
            pos = sread(pos, a[i][k[i]]);
    }
    for (int i = 1; i <= n; ++i)
        read(c[i]);
    int ss = 1, tt = 2;
    for (int i = 1; i <= n; ++i)
        mincut.addedge(i + 2, tt, c[i]);
    for (int i = 1; i <= m; ++i) {
        mincut.addedge(ss, i + n + 2, p[i]);
        for (int j = 1; j <= k[i]; ++j)
            mincut.addedge(i + n + 2, a[i][j] + 2, INF);
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i)
        ans += p[i];
    ans -= mincut.maxflow(ss, tt);
    for (int i = 1; i <= m; ++i)
        if (mincut.lev[i + n + 2] != -1)
            ans1.push_back(i);
    for (int i = 1; i <= n; ++i)
        if (mincut.lev[i + 2] != -1)
            ans2.push_back(i);
    for (int i = 0; i < ans1.size(); ++i)
        write(ans1[i]), putchar(" \n"[i == ans1.size() - 1]);
    for (int i = 0; i < ans2.size(); ++i)
        write(ans2[i]), putchar(" \n"[i == ans2.size() - 1]);
    write(ans), putchar('\n');
    return 0;
}