Codeforces 1045. A. Last chance(網絡流 + 線段樹優化建邊)

題意

給你 \(n\) 個武器，\(m\) 個敵人，問你最多消滅多少個敵人，并輸出方案。

總共有三種武器。

• SQL 火箭 - 能消滅給你集合中的一個敵人 \(\sum |S| \le 100000\) ；
• 認知光束 - 可以消滅 \([l, r]\) 區間中的一個敵人；
• OMG 火箭筒 - 消滅給你集合中的 \(0\) 個或者 \(2\) 個敵人，集合大小為 \(3\) ，且火箭筒消滅的集合互不重合。

\(n, m \le 5000\) 。

題解

現場的時候直覺告訴我是網絡流，但是這個數據范圍，以及 CodeForces 從不出網絡流的傳言，不敢剛。。

其實這題還是個網絡流，因為可以看出來還是個是個二分圖求最大匹配的模型（對于前兩種武器來說）。

首先對于第一種武器，可以直接在二分圖上暴力連邊。

第二種武器，我們可以考慮線段樹優化建邊就行了。（就是樹上的邊從父親向兒子連 \(inf\) 就行了）

第三種武器，看起來只有 \(0,2\) 兩種取值很奇怪，其實我們可以把它當成有 \(0,1,2\) 三種取值。

也就是說這個點可以匹配 \(0\sim 2\) 個點。

為什么取 \(1\) 時候是對的呢？因為我們總可以在集合中找另外一個點，把原來消滅它的武器換成這個武器就行了。

然后就可以建完了，至于時間復雜度 ，題解給了一個 \(O(nm \log m)\) 的復雜度，其實我覺得是 \(O(flow)\) 。。

---

然后輸出方案有些麻煩，首先考慮前兩種武器，第一種武器可以直接先匹配，第二種武器我們在線段樹上自底向上依次分配可行的節點就行了，這個用一個 std :: vector 作為遞歸函數返回值返回值比較好寫。

然后考慮第三種武器，只需要對于 \(flow = 1\) 的情況再找一個匹配了的點，替換消滅的武器就行了。

總結

然后對于一些無法取值的流量，我們可以考慮先取，然后通過構造使得這個流量滿足條件。

網絡流輸出方案的時候考慮退流會退到最開始的哪個地方就行了。

代碼

#include <bits/stdc++.h>#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define All(x) (x).begin(), (x).end()using namespace std;template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}inline int read() {int x(0), sgn(1); char ch(getchar());for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);return x * sgn;
}void File() {
#ifdef zjp_shadowfreopen ("a.in", "r", stdin);freopen ("a.out", "w", stdout);
#endif
}int n, m;const int inf = 0x3f3f3f3f;template<int Maxn, int Maxm>
struct Dinic {int Head[Maxn], Next[Maxm], cap[Maxm], to[Maxm], e;Dinic() { e = 1; }inline void add_edge(int u, int v, int flow) {to[++ e] = v; Next[e] = Head[u]; Head[u] = e; cap[e] = flow;}inline void Add(int u, int v, int flow) {add_edge(u, v, flow); add_edge(v, u, 0);}int S, T, dis[Maxn];bool Bfs() {queue<int> Q; Q.push(S); Set(dis, 0); dis[S] = 1;while (!Q.empty()) {int u = Q.front(); Q.pop();for (int i = Head[u], v = to[i]; i; v = to[i = Next[i]])if (cap[i] && !dis[v]) dis[v] = dis[u] + 1, Q.push(v);}return dis[T];}int cur[Maxn];int Dfs(int u, int flow) {if (u == T || !flow) return flow;int res = 0, f;for (int &i = cur[u]; i; i = Next[i]) {int v = to[i];if (dis[v] == dis[u] + 1 && (f = Dfs(v, min(flow, cap[i])))) {cap[i] -= f, cap[i ^ 1] += f, res += f;if (!(flow -= f)) break;}}if (!res) dis[u] = 0;return res;}int Run() {int sum_flow = 0;while (Bfs())Cpy(cur, Head), sum_flow += Dfs(S, inf);return sum_flow;}};const int N = 5050;Dinic<(int)1e5, (int)4e5> D;int tot;#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r#define Travel(i, u, v) for(int i = D.Head[u], v = D.to[i]; i; v = D.to[i = D.Next[i]])int ans[N], Bef;template<int Maxn>
struct Segment_Tree {int id[Maxn];void Build(int o, int l, int r) {if (l == r) { id[o] = l; return ; }id[o] = ++ tot;int mid = (l + r) >> 1;Build(lson); Build(rson);D.Add(id[o], id[o << 1], id[o << 1] <= m ? 1 : inf);D.Add(id[o], id[o << 1 | 1], id[o << 1 | 1] <= m ? 1 : inf);}inline void Connect(int o, int l, int r, int ql, int qr, int Id) {if (ql <= l && r <= qr) { D.Add(Id, id[o], 1); return ; }int mid = (l + r) >> 1;if (ql <= mid) Connect(lson, ql, qr, Id);if (qr > mid) Connect(rson, ql, qr, Id);}vector<int> find(int o, int l, int r) {if (l == r) return vector<int>();vector<int> tmp;int mid = (l + r) >> 1;vector<int> ls = find(lson), rs = find(rson);set_union(All(ls), All(rs), inserter(tmp, tmp.end()));Travel(i, id[o], v)if (v <= m && !D.cap[i]) tmp.push_back(v);Travel(i, id[o], v) if (D.cap[i] && v > Bef) {int cur = tmp[tmp.size() - 1]; tmp.pop_back();ans[cur] = v - Bef;}return tmp;}};Segment_Tree<N << 2> T;vector<int> V1, V2, V3;int Ref[N], from[N], go[N];void Get_Ans() {for (int u : V1) {Travel(i, Ref[u], v)if (v <= m && D.cap[i ^ 1]) ans[v] = u;}T.find(1, 1, m);for (int u : V3) {int flow = D.cap[from[u]];Travel(i, Ref[u], v)if (v != D.S && !D.cap[i]) ans[v] = u;if (flow == 1)Travel(i, Ref[u], v)if (v != D.S && D.cap[i]) { ans[v] = u; break; }}
}int main () {File();n = read(), m = read();tot = m; T.Build(1, 1, m); Bef = tot;D.S = tot + n + 1; D.T = tot + n + 2;For (i, 1, m) D.Add(i, D.T, 1), go[i] = D.e - 1;For (i, 1, n) {int opt = read();D.Add(D.S, Ref[i] = ++ tot, 1 + (opt == 2)); from[i] = D.e - 1;if (opt == 0) {int k = read(); V1.push_back(i);while (k --) D.Add(tot, read(), 1);} else if (opt == 1) {int l = read(), r = read(); V1.push_back(i);T.Connect(1, 1, m, l, r, tot);} else {int a = read(), b = read(), c = read();V3.push_back(i);D.Add(tot, a, 1);D.Add(tot, b, 1);D.Add(tot, c, 1);}}printf ("%d\n", D.Run());Get_Ans();For (i, 1, m) if (ans[i])printf ("%d %d\n", ans[i], i);return 0;}