# Codeforces 1045. A. Last chance(网络流 + 线段树优化建边)

## 题意

• SQL 火箭 - 能消灭给你集合中的一个敌人 $$\sum |S| \le 100000$$
• 认知光束 - 可以消灭 $$[l, r]$$ 区间中的一个敌人；
• OMG 火箭筒 - 消灭给你集合中的 $$0$$ 个或者 $$2$$ 个敌人，集合大小为 $$3$$ ，且火箭筒消灭的集合互不重合。

$$n, m \le 5000$$

## 代码

#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;}

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() {
freopen ("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) {
}

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], 2); 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();

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) {
D.Add(D.S, Ref[i] = ++ tot, 1 + (opt == 2)); from[i] = D.e - 1;
if (opt == 0) {
} else if (opt == 1) {
T.Connect(1, 1, m, l, r, tot);
} else {
V3.push_back(i);
}
}

printf ("%d\n", D.Run());

Get_Ans();

For (i, 1, m) if (ans[i])
printf ("%d %d\n", ans[i], i);

return 0;

}

Codeforces 1045. A. Last chance(网络流 + 线段树优化建边)

(0)
(0)

0条