[題解] T'ill It's Over

前言

線段樹+網路最大流的建模題。

題目鏈接

題目大意

最初時有 \(n\) 個 \(1\) 。給定 \(op\) 、 \(l\) ，其中， \(l\) 為操作次數上限。你有四個操作：

  1. 若 \(op=1\) ，則接下來兩個整數 \(a,b\) ，表示可以將 \(a\) 變為 \(b\) 。
  2. 若 \(op=2\) ，則接下來三個整數 \(a_1,a_2,b_1\) ，表示可以將範圍在 \(a_1\) 到 \(a_2\) 的任意的數變為 \(b_1\) 。
  3. 若 \(op=3\) ，則接下來三個整數 \(a_1,b_1,b_2\) ，表示可以將 \(a_1\) 變為範圍在 \(b_1\) 到 \(b_2\) 的任意的數。
  4. 若 \(op=4\) ，則接下來四個整數 \(a_1,a_2,b_1,b_2\) ，表示可以將範圍在 \(a_1\) 到 \(a_2\) 的任意的數變為範圍在 \(b_1\) 到 \(b_2\) 的任意的數。

問最後能有多少個數字變為 \(k\) ，其中 \(1<=a,b,a1,b1,a2,b2<=k\) 。

思路

首先用暴力建圖跑網路流。如果看出使用網路流，則建圖就變得非常簡單了。

把所有單個數字的查詢都看為一個區間，那麼四個操作都將是區間的連邊。

使用一個類似於中轉站的兩個節點記為 \(tmp1\) 和 \(tmp2\) ，將 \(a\) 區間的所有值連向 \(tmp1\) ，將 \(tmp2\) 連向 \(b\) 區間的所有值，容量為無窮大。則 \(tmp1\) 到 \(tmp2\) 連一條容量為 \(l\) 的邊用來限制操作次數。

跑最大流即可得出答案。暴力建圖偽程式碼：

int tot = k;
int opt, l;
for(int i = 1; i <= m; i++) {
	scanf("%d %d", &opt, &l);
	if(opt == 1) {
		int a, b;
		scanf("%d %d", &a, &b);
		Addedge(a, b, l);
	}
	else if(opt == 2) {
		int a1, a2, b1;
		scanf("%d %d %d", &a1, &a2, &b1);
		int tmp1 = ++tot;
		int tmp2 = ++tot;
		for(int i = a1; i <= a2; i++)
			Addedge(i, tmp1, INF);
		Addedge(tmp2, b1, INF);
		Addedge(tmp1, tmp2, l);
	}
	else if(opt == 3) {
		int a1, b1, b2;
		scanf("%d %d %d", &a1, &b1, &b2);
		int tmp1 = ++tot;
		int tmp2 = ++tot;
		Addedge(a1, tmp1, INF);
		for(int i = b1; i <= b2; i++)
			Addedge(tmp2, i, INF);
		Addedge(tmp1, tmp2, l);
	}
	else {
		int a1, a2, b1, b2;
		scanf("%d %d %d %d", &a1, &a2, &b1, &b2);
		int tmp1 = ++tot;
		int tmp2 = ++tot;
		for(int i = a1; i <= a2; i++)
			Addedge(i, tmp1, INF);
		for(int i = b1; i <= b2; i++)
			Addedge(tmp2, i, INF);
		Addedge(tmp1, tmp2, l);
	}
}
t = tot + 1;
Addedge(s, 1, n);
Addedge(k, t, INF);

顯然，一次操作會產生最多 \(2k+2\) 條邊，在觀察這個數據範圍，過不了。親測 50 Pts。可能是常數太大。。。

由於是區間操作，可以想到使用數據結構來優化建圖。

使用線段樹，建立兩顆線段樹，如下圖。
在这里插入图片描述

\(s\) 連向第一棵線段樹的 \([1,1]\) 區間的點，容量為 \(n\) ，第二棵線段樹的 \([k,k]\) 區間的點連向 \(t\) ，容量為極大值，和暴力差不多。

可以把第二棵樹理解為是操作樹，是用來進行操作的。第一棵樹的兒子連向自己的父親，方便選定被操作前的範圍。第二棵的父親連向自己的兒子，方便選定操作後的範圍。以上邊的容量均為極大值。

最後第二棵樹的節點連向第一棵樹的對應點，方便操作後被再次操作。

最後跑一邊最大流 Dinic ，在隨機圖上 Dinic 普遍優於其他 \(O(nmlog(m))\) 的演算法。

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 1e6 + 5;
const int MAXM = 5e6 + 5;
struct Segment_Tree {
	int Left_Section, Right_Section, Data;
	#define LC(x) (x << 1)
	#define RC(x) (x << 1 | 1)
	#define L(x) tree[0][x].Left_Section
	#define R(x) tree[0][x].Right_Section
	#define D(x, y) tree[y][x].Data
};
Segment_Tree tree[2][MAXN];
struct Edge { 
	int Next, To, Cap;
};
Edge edge[MAXM << 1];
int head[MAXM << 1];
int edgetot = 1;
int tot;
int n, m, k, s, t;
queue<int> q;
int dep[MAXN], stt[MAXN];
int Begin, End;
void Addedge(int x, int y, int z) {
	edge[++edgetot].Next = head[x], edge[edgetot].To = y, edge[edgetot].Cap = z, head[x] = edgetot;
	edge[++edgetot].Next = head[y], edge[edgetot].To = x, edge[edgetot].Cap = 0, head[y] = edgetot;
}
void Build(int pos, int l, int r, int flag) {//初始化線段樹的節點資訊 
	D(pos, flag) = ++tot;//開闢新的節點 
	L(pos) = l;//初始化左區間 
	R(pos) = r;//初始化右區間 
	if(l == r) {
		if(flag && l == 1)//記錄左樹的1節點 
			Begin = D(pos, flag);
		if(!flag && l == k)//記錄右樹的k節點
			End = D(pos, flag);
		if(!flag)//右樹連左樹的對應節點 
			Addedge(D(pos, flag), D(pos, 1 - flag), INF);
		return;
	}
	int mid = (l + r) >> 1;
	Build(LC(pos), l, mid, flag);//初始化 
	Build(RC(pos), mid + 1, r, flag);//同上 
	if(flag) {//左樹兒子連父親 
		Addedge(D(LC(pos), flag), D(pos, flag), INF);
		Addedge(D(RC(pos), flag), D(pos, flag), INF);
	}
	else {//右樹父親連兒子 
		Addedge(D(pos, flag), D(LC(pos), flag), INF);
		Addedge(D(pos, flag), D(RC(pos), flag), INF);
	}
}
void Query(int pos, int l, int r, int tmp, int flag) {//區間連邊 
	if(l <= L(pos) && R(pos) <= r) {
		if(flag)
			Addedge(D(pos, flag), tmp, INF);//若是左樹則連接中轉站 
		else
			Addedge(tmp, D(pos, flag), INF);//若是右樹被中轉站連接 
		return;
	}
	if(l <= R(LC(pos)))
		Query(LC(pos), l, r, tmp, flag);//處理子樹 
	if(r >= L(RC(pos)))
		Query(RC(pos), l, r, tmp, flag);//同上 
}
bool bfs() {//Dinic板子，不詳寫 
	for(int i = s; i <= t; i++)
		dep[i] = 0;
	stt[s] = head[s];
	dep[s] = 1;
	q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int i = head[u]; i; i = edge[i].Next) {
			int v = edge[i].To;
			if(!dep[v] && edge[i].Cap) {
				dep[v] = dep[u] + 1;
				stt[v] = head[v];
				q.push(v);
			}
		}
	}
	return dep[t] != 0;
}
int dfs(int u, int flow) {//同上 
	if(u == t || !flow)
		return flow;
	int rest = flow;
	for(int i = stt[u]; i && rest; i = edge[i].Next) {
		stt[u] = i;
		int v = edge[i].To;
		if(dep[v] == dep[u] + 1 && edge[i].Cap) {
			int nextflow = dfs(v, min(rest, edge[i].Cap));
			if(!nextflow)
				dep[v] = -1;
			edge[i].Cap -= nextflow;
			edge[i ^ 1].Cap += nextflow;
			rest -= nextflow;
		}
	}
	return flow - rest;
}
int Dinic() {//同上 
	int res = 0;
	int flow;
	while(bfs())
		while(flow = dfs(s, INF))
			res += flow;
	return res;
}
int main() {
	scanf("%d %d %d", &n, &m, &k);
	Build(1, 1, k, 1); 
	Build(1, 1, k, 0);
	int opt, l;
	for(int i = 1; i <= m; i++) {
		scanf("%d %d", &opt, &l);
		int tmp1 = ++tot;
		int tmp2 = ++tot;
		if(opt == 1) {
			int a, b;
			scanf("%d %d", &a, &b);
			Query(1, a, a, tmp1, 1);
			Query(1, b, b, tmp2, 0);
		}
		else if(opt == 2) {
			int a1, a2, b1;
			scanf("%d %d %d", &a1, &a2, &b1);
			Query(1, a1, a2, tmp1, 1);
			Query(1, b1, b1, tmp2, 0);
		}
		else if(opt == 3) {
			int a1, b1, b2;
			scanf("%d %d %d", &a1, &b1, &b2);
			Query(1, a1, a1, tmp1, 1);
			Query(1, b1, b2, tmp2, 0);
		}
		else {
			int a1, a2, b1, b2;
			scanf("%d %d %d %d", &a1, &a2, &b1, &b2);
			Query(1, a1, a2, tmp1, 1);
			Query(1, b1, b2, tmp2, 0);
		}
		Addedge(tmp1, tmp2, l);
	}
	t = tot + 1;
	Addedge(s, Begin, n);//連接源點到左樹1的點 
	Addedge(End, t, INF);//連接右樹k的點到匯點 
	printf("%d", Dinic());
	return 0;
}
Tags:

VirMach 便宜 VPS