P8291 [省选联考 2022] 学术社区 题解

Description

以下涉及的所有字符串判等操作都对大小写敏感，例如 1oushang、Loushang、LOUSHANG 是互不相同的字符串。

小 I 正在整理学术社区中的一个帖子。帖子中一共有 NN 个网友发过消息，他们的网名分别为 n1,n2,…,nNn_1, n_2, \ldots, n_N。帖子中总共有 MM 条消息，对于第 ii 条消息，我们用三个字符串 si,1,si,2,si,3s_{i,1}, s_{i,2}, s_{i,3} 构成的三元组描述它，其中 si,1s_{i,1} 表示这条消息发出者的网名，而 si,2s_{i,2} 和 si,3s_{i,3} 描述这条消息的内容。

对于第 ii 条消息，我们通过如下方式定义其属于楼下型消息、楼上型消息、学术型消息中的哪一种：

  • 若字符串 si,3s_{i, 3} 为 louxia，且 si,2s_{i, 2} 恰好与给出的某个网名相同（注意 si,2=si,1s_{i,2} = s_{i,1} 是允许的），则称这条消息是楼下型消息，si,2s_{i,2} 对应这条消息提到的网友；
  • 若字符串 si,3s_{i,3} 为 loushang，且 si,2s_{i,2} 恰好与给出的某个网名相同（注意 si,2=si,1s_{i,2} = s_{i,1} 是允许的），则称这条消息是楼上型消息，si,2s_{i,2} 对应这条消息提到的网友；
  • 若以上两个条件都不满足，则称这条消息是学术消息。

定义一个对所有消息的重排方案为一个 11 到 MM 的排列 a1,a2,a3,…,aMa_1, a_2, a_3, \ldots, a_M，表示第一条消息是 (sa1,1,sa1,2,sa1,3)(s_{a_1,1}, s_{a_1,2}, s_{a_1,3})，第二条消息是 (sa2,1,sa2,2,sa2,3)(s_{a_2,1}, s_{a_2,2}, s_{a_2,3})，依此类推。

对于一个重排方案 a1,a2,a3,…,aMa_1, a_2, a_3, \ldots, a_M 中的第 ii（1≤i≤M1 \le i \le M）条消息 (sai,1,sai,2,sai,3)(s_{a_i,1}, s_{a_i,2}, s_{a_i,3})，如下定义其是否是符合实际情况的：

  • 若这条消息是楼下型消息，则这条消息是符合实际情况的当且仅当 i≠1i \ne 1 且 sai−1,1=sai,2s_{a_{i - 1}, 1} = s_{a_i, 2}，即上一条消息存在且它的发出者与这条消息提到的网友一致。
  • 若这条消息是楼上型消息，则这条消息是符合实际情况的当且仅当 i≠Mi \ne M 且 sai+1,1=sai,2s_{a_{i + 1}, 1} = s_{a_i, 2}，即下一条消息存在且它的发出者与这条消息提到的网友一致。
  • 若这条消息是学术消息，则无论如何这条消息一定不是符合实际情况的，这是因为小 I 只想灌水不想学术。

在以上定义下，小 I 希望找到一个重排方案，使得该重排方案中符合实际情况的消息数量最多。你需要帮他找到这个方案以及这个方案中符合实际情况的消息数量。

为了方便你的解题，小 I 还告诉了你帖子中消息的一个特殊限制：因为学术社区会禁言在社区中只灌水不学术的人，所以在小 I 给出的帖子里，每一个在帖子中发过言的人都一定会在帖子中发出至少一条学术消息。

1≤N≤M≤77777,1≤∑M≤2.5×1051\leq N\leq M\leq 77777,1\leq\sum M\leq 2.5\times 10^5。

Solution

首先考虑特殊性质 ABC 怎么做。

考虑把问题放到有向图上做。先建一个超级源点 T，对于每个楼下型消息 AA 在 BB 楼下在有向图上连一条 B→AB\to A 的边，对于 AA 发出的学术消息就连一条 A→TA\to T 的边。容易发现此时每个点的入度一定小于等于出度，所以对每个点 xx 连 outx−inxout_x-in_x 条 T→xT\to x 的边，然后跑欧拉回路，把回路去掉无用边即为最终方案。

然后是特殊性质 AC。

由于不一定每个非学术消息都满足条件，所以现在的有向图就不保证 inx≤outxin_x\leq out_x 了，但是会发现如果 inx>outxin_x>out_x，那么至少有 inx−outxin_x-out_x 个消息不合法，所以把所有这样的消息去掉可以得到一个上界，同时可以构造这个上界的方案：如果 inx>outxin_x>out_x，则连 inx−outxin_x-out_x 条 x→Tx\to T 的边，如果 inx<outxin_x<out_x 则连 outx−inxout_x-in_x 条 T→xT\to x 条边，然后跑欧拉回路即为方案，正确性显然。

然后是特殊性质 BC。

现在既有楼上型消息也有楼下型消息，但是由于 B 性质的存在，所以最终方案的形态一定是形如一段楼上型消息+学术消息+一段楼下型消息的组合拼起来，所以可以建两个图 G1,G2G_1,G_2。

对于楼上型消息 AA 在 BB 楼上，就在 G1G_1 连一条 A→BA\to B 的边，如果 AA 在 BB 楼下，就在 G2G_2 连一条 B→AB\to A 的边，对于 AA 发出的学术消息则连一条 A1→A2A_1\to A_2 的边。容易发现 G1G_1 中的点入度不大于出度，G2G_2 中的点入度不小于出度，所以对于 G1G_1 中的点 xx 连 outx−inxout_x-in_x 条 T→xT\to x 的边，G2G_2 中的 xx 连 inx−outxin_x-out_x 条 x→Tx\to T 的边，然后跑欧拉回路即可。

然后是特殊性质 C。

此时 G1G_1 中 inxin_x 可能大于 outxout_x，G2G_2 中 inxin_x 可能小于 outxout_x，可以通过特殊性质 AC 的做法得到一个答案的上界，但此时不一定最优。

因为如果删除一条 AA 在 BB 楼上的消息，并将其变成学术消息，会让 outA2out_{A_2} 加一，inB1in_{B_1} 减一，如果原来 inA2>outA2in_{A_2}>out_{A_2} 且 inB1<outB1in_{B_1}<out_{B_1}，答案的上界就可以增大一。

这启发我们建出一个网络流图，源点 SS 向所有 A1A_1 连流量为 outA1−inA1out_{A_1}-in_{A_1} 的边，A2A_2 向汇点 TT 连流量为 inA2−outA2in_{A_2}-out_{A_2} 的边，对于一条 AA 在 BB 楼上的消息，就连 B1→A2B_1\to A_2 流量为 11 的边，AA 在 BB 楼下的消息连 A1→B2A_1\to B_2 流量为 11 的边。

然后跑最大流可以得到改为学术消息的原来非学术消息，把这些改了之后做类似特殊性质 AC 的做法即可。

如果没有特殊性质 C，则中间的转接部分可能形如 A→B→AA\to B\to A，但是可以证明优先把这样的二元环缩起来一定最优，缩完后这些二元环连和学术消息类似的边即可。

时间复杂度：O(mm)O(m\sqrt 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
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 8e5 + 5;

int n, m, t;
int in[kMaxN * 2], out[kMaxN * 2], res[kMaxN], cur[kMaxN * 2];
bool del[kMaxN];
std::tuple<int, int, int> e[kMaxN], _e[kMaxN];
std::vector<int> vec[kMaxN], stk;
std::map<std::string, int> mp;
std::vector<std::pair<int, int>> G[kMaxN * 2];

namespace Dinic {
struct Edge {
  int v, w, id, pre;
} e[kMaxN * 10];

int tot = 1, n, s, t;
int tail[kMaxN * 2], cur[kMaxN * 2], dep[kMaxN * 2];

void init(int _n, int _s, int _t) {
  for (int i = 1; i <= n; ++i) tail[i] = cur[i] = dep[i] = 0;
  for (int i = 1; i <= tot; ++i) e[i] = {0, 0, 0};
  tot = 1, n = _n, s = _s, t = _t;
}
void adde(int u, int v, int w, int id) { e[++tot] = {v, w, id, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w, int id) { adde(u, v, w, id), adde(v, u, 0, id); }

bool bfs() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i)
    cur[i] = tail[i], dep[i] = 1e9;
  q.emplace(s), dep[s] = 0;
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v, w = e[i].w;
      if (w && dep[v] == 1e9) {
        dep[v] = dep[u] + 1, q.emplace(v);
      }
    }
  }
  return dep[t] != 1e9;
}
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] = 1e9;
      lim -= fl, flow += fl;
      e[i].w -= fl, e[i ^ 1].w += fl;
      if (!lim) break;
    }
  }
  return flow;
}
int maxflow() {
  int ans = 0;
  for (; bfs(); ans += dfs(s, 1e9)) {}
  return ans;
}
std::vector<int> getdel() {
  std::vector<int> vec;
  int flow = maxflow();
  for (int i = 1; i <= ::n; ++i) {
    for (int id = tail[i]; id; id = e[id].pre) {
      int j = e[id].v;
      if (j >= ::n + 1 && j <= 2 * ::n && !e[id].w) {
        vec.emplace_back(e[id].id);
      }
    }
  }
  return vec;
}
} // namespace Dinic

void init() {
  t = 0, stk.clear(), mp.clear();
  for (int i = 1; i <= m; ++i) del[i] = 0, vec[i].clear();
  for (int i = 1; i <= 2 * n + 1; ++i) G[i].clear(), cur[i] = in[i] = out[i] = 0;
}

void prework() {
  static std::tuple<int, int, int> tmp[kMaxN];
  std::set<std::tuple<int, int, int, int>> st;
  int _m = 0;
  for (int i = 1; i <= m; ++i) {
    auto [op, u, v] = e[i];
    if (op == 0 || op == 1) {
      auto it = st.lower_bound({op ^ 1, v, u, 0});
      if (it != st.end() && std::get<0>(*it) == (op ^ 1) && std::get<1>(*it) == v && std::get<2>(*it) == u) {
        if (op == 0) {
          tmp[++_m] = {2, u, v};
          vec[_m] = {std::get<3>(*it), i};
        } else {
          tmp[++_m] = {2, v, u};
          vec[_m] = {i, std::get<3>(*it)};
        }
        st.erase(it);
      } else {
        st.emplace(op, u, v, i);
      }
    } else {
      tmp[++_m] = {op, u, u};
      vec[_m] = {i};
    }
  }
  for (auto [op, u, v, i] : st) {
    tmp[++_m] = {op, u, v};
    vec[_m] = {i};
  }
  m = _m;
  for (int i = 1; i <= m; ++i) e[i] = tmp[i];
}

void getdeg(bool o = 0) {
  if (!o) {
    for (int i = 1; i <= 2 * n; ++i) in[i] = out[i] = 0;
  }
  for (int i = 1; i <= m; ++i) {
    if (del[i]) continue;
    auto [op, u, v] = e[i];
    if (op == 0) {
      ++out[u], ++in[v];
      if (o) G[u].emplace_back(v, i);
    } else if (op == 1) {
      ++out[v + n], ++in[u + n];
      if (o) G[v + n].emplace_back(u + n, i);
    } else {
      ++out[u], ++in[v + n];
      if (o) G[u].emplace_back(v + n, i);
    }
  }
}

void dfs(int u) {
  for (int i = cur[u]; i < (int)G[u].size(); i = cur[u]) {
    auto [v, id] = G[u][i];
    cur[u] = i + 1;
    dfs(v);
    stk.emplace_back(id);
  }
}

int getcnt() {
  int cnt = 0;
  for (int i = 1; i <= t; ++i) {
    auto [op, u, v] = _e[res[i]];
    if (op == 0 && i < t && v == std::get<1>(_e[res[i + 1]]) || op == 1 && i > 1 && v == std::get<1>(_e[res[i - 1]]))
      ++cnt;
  }
  return cnt;
}

void dickdreamer() {
  std::cin >> n >> m;
  init();
  for (int i = 1; i <= n; ++i) {
    std::string s;
    std::cin >> s;
    mp[s] = i;
  }
  for (int i = 1; i <= m; ++i) {
    std::string s1, s2, s3;
    std::cin >> s1 >> s2 >> s3;
    if (s3 == "loushang" && mp.count(s2)) {
      e[i] = {0, mp[s1], mp[s2]};
    } else if (s3 == "louxia" && mp.count(s2)) {
      e[i] = {1, mp[s1], mp[s2]};
    } else {
      int id = mp[s1];
      e[i] = {2, id, id};
    }
    _e[i] = e[i];
  }
  for (int i = 1; i <= m; ++i) vec[i] = {i};
  prework();
  // for (int i = 1; i <= m; ++i) {
  //   for (auto x : vec[i]) std::cout << x << ' ';
  //   std::cout << '\n';
  // }
  // std::cout << '\n';
  int S = 2 * n + 1, T = 2 * n + 2;
  Dinic::init(2 * n + 2, S, T);
  getdeg();
  // for (int i = 1; i <= 2 * n; ++i) std::cerr << in[i] << ' ' << out[i] << '\n';
  for (int i = 1; i <= n; ++i)
    if (in[i] > out[i])
      Dinic::add(S, i, in[i] - out[i], 0);
  for (int i = n + 1; i <= 2 * n; ++i)
    if (out[i] > in[i])
      Dinic::add(i, T, out[i] - in[i], 0);
  for (int i = 1; i <= m; ++i) {
    auto [op, u, v] = e[i];
    // std::cout << op << ' ' << u << ' ' << v << '\n';
    if (op == 0) {
      Dinic::add(v, u + n, 1, i);
    } else if (op == 1) {
      Dinic::add(u, v + n, 1, i);
    }
  }
  auto dvec = Dinic::getdel();
  for (int i = 1; i <= 2 * n; ++i) in[i] = out[i] = 0;
  for (auto i : dvec) {
    auto [op, u, v] = e[i];
    G[u].emplace_back(u + n, i), ++out[u], ++in[u + n];
    del[i] = 1;
  }
  getdeg(1);
  for (int i = 1; i <= 2 * n; ++i) {
    // if (i <= n) assert(in[i] <= out[i]);
    // else assert(in[i] >= out[i]);
    if (in[i] <= out[i]) {
      for (; in[i] < out[i];)
        G[2 * n + 1].emplace_back(i, 0), ++out[2 * n + 1], ++in[i];
    } else {
      for (; out[i] < in[i];)
        G[i].emplace_back(2 * n + 1, 0), ++out[i], ++in[2 * n + 1];
    }
  }
  // for (int i = 1; i <= 2 * n + 1; ++i) assert(in[i] == out[i]);
  dfs(2 * n + 1);
  for (auto x : stk) {
    for (auto i : vec[x]) res[++t] = i;
  }
  std::reverse(res + 1, res + 1 + t);
  std::cout << getcnt() << '\n';
  for (int i = 1; i <= t; ++i) std::cout << res[i] << " \n"[i == t];
}

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;
}
P8291 [省选联考 2022] 学术社区 题解
https://sobaliuziao.github.io/2025/01/26/post/62172b9c.html
作者
Egg_laying_master
发布于
2025年1月26日
许可协议