【BZOJ3218】【UOJ#77】a + b Problem

题目

思路&做法

明显的最小割（其实是之前做过一道类似的题）

S向每一个格子连容量为\(b_i\)的边
每一个格子向T连容量为\(w_i\)的边
对于格子\(i\)向满足条件的格子\(j(1 \leq j < i, l_i \leq a_j \leq r_i)\)连容量为\(p_i\)的边

但是考虑到这题恶心的数据范围，这样做很明显会TLE。

算法的瓶颈在第三步。我们发现\(j\)的范围看起来像是一个像二维偏序的东西，于是便可以用主席树来优化一下，对于每个节点\(i\)新建一个节点\(k\)，由i向k连容量为\(p_i\)的边，由\(k\)向主席树中\(j\)的范围的对应的节点连容量为\(inf\)的边。

代码

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

const int INF = 0x7F7F7F7F;

const int N = 50010, M = 1450010;

struct edge

{	int from, to, flow, cap;

	edge() { }

	edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), flow(_3), cap(_4) { }

};

struct Dinic

{	edge edges[M];

	int head[165022], nxt[M], tot;

	int L, R;

	inline void init()

	{	memset(head, -1, sizeof(head));

		tot = 0;

	}

	void add_edge(int x, int y, int z)

	{	edges[tot] = edge(x, y, 0, z);

		nxt[tot] = head[x];

		head[x] = tot++;

		edges[tot] = edge(y, x, 0, 0);

		nxt[tot] = head[y];

		head[y] = tot++;

	}

	int s, t;

	int d[165022];

	bool bfs()

	{	memset(d, -1, sizeof(d));

		queue<int> q;

		d[s] = 0;

		q.push(s);

		while (!q.empty())

		{	int x = q.front(); q.pop();

			for (int i = head[x]; ~i; i = nxt[i])

			{	edge & e = edges[i];

				if (e.cap > e.flow && d[e.to] == -1)

				{	d[e.to] = d[x] + 1;

					q.push(e.to);

				}

			}

		}

		return d[t] != -1;

	}

	int cur[165022];

	int dfs(int x, int a)

	{	if (x == t || a == 0) return a;

		int flow = 0, f;

		for (int & i = cur[x]; ~i; i = nxt[i])

		{	edge & e = edges[i];

			if (d[e.to] == d[x] + 1 && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0)

			{	e.flow += f;

				edges[i^1].flow -= f;

				a -= f;

				flow += f;

				if (a == 0) break;

			}

		}

		return flow;

	}

	int maxflow(int _s, int _t)

	{	s = _s, t = _t;

		int flow = 0;

		while (bfs())

		{	for (int i = L; i <= R; i++)

				cur[i] = head[i];

			flow += dfs(s, INF);

		}

		return flow;

	}

} dinic;

int n;

int root[N];

struct SegmentTree

{	int ls[N*20], rs[N*20], sz;

	void update(int & cur, int pre, int l, int r, int p, int node)

	{	cur = ++sz;

		if (l == r)

		{	if (pre) dinic.add_edge(cur, pre, INF);

			dinic.add_edge(cur, node, INF);

			return;

		}

		ls[cur] = ls[pre];

		rs[cur] = rs[pre];

		int mid = (l + r) >> 1;

		if (p <= mid)

			update(ls[cur], ls[pre], l, mid, p, node);

		else

			update(rs[cur], rs[pre], mid+1, r, p, node);

		dinic.add_edge(cur, ls[cur], INF);

		dinic.add_edge(cur, rs[cur], INF);

	}

	void link(int cur, int l, int r, int ql, int qr, int node)

	{	if (ql == l && qr == r)

			dinic.add_edge(node, cur, INF);

		else

		{	int mid = (l + r) >> 1;

			if (qr <= mid)

				link(ls[cur], l, mid, ql, qr, node);

			else if (ql > mid)

				link(rs[cur], mid+1, r, ql, qr, node);

			else

				link(ls[cur], l, mid, ql, mid, node),

				link(rs[cur], mid+1, r, mid+1, qr, node);

		}

	}

} st;

int a[N], w[N], b[N], L[N], R[N], p[N];

int num[N], total;

int main()

{	scanf("%d", &n);

	for (int i = 1; i <= n; i++)

	{	scanf("%d %d %d %d %d %d", &a[i], &b[i], &w[i], &L[i], &R[i], &p[i]);

		num[++total] = a[i];

		num[++total] = L[i];

		num[++total] = R[i];

	}

	sort(num+1, num+total+1);

	total = unique(num+1, num+total+1) - num - 1;

	for (int i = 1; i <= n; i++)

	{	a[i] = lower_bound(num+1, num+1+total, a[i]) - num;

		L[i] = lower_bound(num+1, num+1+total, L[i]) - num;

		R[i] = lower_bound(num+1, num+1+total, R[i]) - num;

	}

	int ans = 0;

	dinic.init();

	int S = n + n + 1, T = n + n + 2;

	st.sz = n + n + 2;

	for (int i = 1; i <= n; i++)

	{	dinic.add_edge(S, i, b[i]);

		dinic.add_edge(i, T, w[i]);

		dinic.add_edge(i, i+n, p[i]);

		if (i > 1)

			st.link(root[i-1], 1, total, L[i], R[i], i+n);

		st.update(root[i], root[i-1], 1, total, a[i], i);

		ans += b[i] + w[i];

	}

	dinic.L = 0, dinic.R = st.sz;

	ans -= dinic.maxflow(S, T);

	printf("%d\n", ans);

}

/*

10

0 1 7 3 9 2

7 4 0 9 10 5

1 0 4 2 10 2

7 9 1 5 7 2

6 3 5 3 6 2

6 6 4 1 8 1

6 1 6 0 6 5

2 2 5 0 9 3

5 1 3 0 2 5

5 6 7 1 1 2

*/

巴特西

【BZOJ3218】【UOJ#77】a + b Problem

题目

思路&做法

代码

最新文章

热门文章