【BZOJ 3577】玩手机

Qizy Sparse Table, Tricks, 图论, 数据结构, 最大流, 网络流, 解题报告

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3577
神犇题解：http://www.cnblogs.com/clrs97/p/4403242.html

解题报告

之前一直都是线段树优化建图
这题需要用$ST$表来优化建图

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; 
int head[N],nxt[M],to[M],flow[M],n1[2][70][70];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v, int f) {
	assert(u); assert(v);
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
	int dis[N],cur[N];
	queue<int> que;
	public:
		inline int MaxFlow() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(cur));
				ret += DFS(S, INF);
			}
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis, 60, sizeof(dis));
			dis[S] = 0;
			for (que.push(S); !que.empty(); que.pop()) {
				int w = que.front();
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > INF) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] <= INF;
		}
		inline int DFS(int w, int f) {
			if (w == T) {
				return f;
			} else {
				int ret = 0;
				for (int &i = cur[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] == dis[w] + 1) {
						int tmp = DFS(to[i], min(f, flow[i]));
						ret += tmp; f -= tmp;
						flow[i] -= tmp; flow[i ^ 1] += tmp;
						if (!f) {
							break;
						}
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	X = read(); Y = read(); 
	A = read(); B = read();
	S = ++tot; T = ++tot;
	E = 1; 
	for (int i = 1; i <= X; ++i) {
		for (int j = 1; j <= Y; ++j) {
			n1[0][i][j] = ++tot;
			n1[1][i][j] = ++tot;
			AddEdge(n1[0][i][j], n1[1][i][j], read());
		}
	}
	for (int i = X; i; --i) {
		for (int j = Y; j; --j) {
			for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
				n2[0][i][j][a] = ++tot;
				n2[1][i][j][a] = ++tot;
				if (!a) {
					AddEdge(n2[0][i][j][a], n1[0][i][j], INF);
					AddEdge(n1[1][i][j], n2[1][i][j][a], INF);	
				} else {
					int llen = len >> 1;
					AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);
					
					AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
				} 
			}	
		}
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
		p0 = ++tot; p1 = ++tot;
		w = read(); 
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(S, p0, INF);
		AddEdge(p0, p1, w);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(p1, n2[0][x1][y1][lg], INF);
		AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
		p0 = ++tot;	p1 = ++tot;
		w = read();
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(p0, p1, w);
		AddEdge(p1, T, INF);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(n2[1][x1][y1][lg], p0, INF);
		AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
	}
	assert(tot < N);
	assert(E < M);
	printf("%d\n", Dinic.MaxFlow());
	return 0;
}

24 thoughts to “【BZOJ 3577】玩手机”

  2. 884798 223770Greetings! This really is my 1st comment here so I just wanted to give a quick shout out and tell you I genuinely enjoy reading by means of your blog posts. Can you recommend any other blogs/websites/forums that deal with exactly the same topics? Thank you so significantly! 360956

    Reply

  3. 122538 782910Naturally I like your web-site, nevertheless you require to check the spelling on several of your posts. Many of them are rife with spelling issues and I discover it extremely silly to inform you. On the other hand I will surely come again again! 567060

    Reply

  9. 551089 540731Youre so correct. Im there with you. Your weblog is surely worth a read if anyone comes throughout it. Im lucky I did because now Ive obtained a whole new view of this. I didnt realise that this issue was so critical and so universal. You completely put it in perspective for me. 616888

    Reply

  10. 740738 844166Must tow line this caravan together with van trailer home your entire family fast get exposed to the issues along with reversing create tight placement. awnings 8592

    Reply

  12. 649006 351706Most appropriate the human race messages work to show your and present exclusive chance with particular couple. Beginer appear system in advance of raucous men and women will most likely always be aware most of the golden value off presentation, which is actually a persons truck. greatest man jokes 90773

    Reply

  13. 398507 876577Its genuinely a cool and helpful piece of information. Im glad that you basically shared this beneficial information with us. Please stay us informed like this. Thank you for sharing. 920037

    Reply

  14. I was suggested this blog by my cousin. I am not sure whether this post is written by him as nobody else know such detailed about my difficulty. You’re incredible! Thanks!

    Reply

  15. I’ve been absent for some time, but now I remember why I used to love this web site. Thank you, I will try and check back more often. How frequently you update your site?

    Reply

  16. 5792901449Você já viu a maneira mais efetivo de aumentar de elo em LOL? Absolutamente, não é se estressando em partidas ranqueadas. A melhor escolha é pedir um elojob lol, um trabalho oferecido por um jogador high elo, com melhor sequência de conquistas e entre os superiores do jogo, que subirá a força da sua conta.5255479639

    Reply

  17. 3288187314No low elo costumam ficar os jogadores que não estão se sentindo tão animados com o jogo, por essa causa, a taxa de desistências no meio das partidas (os AFKs), de mensagens de rage e de mortes propositais é bem maior.9994021343

    Reply

  19. 6901848655No Ferro, Bronze e Prata costumam ficar os jogadores que não estão se sentindo tão animados com o game, por esse motivo, a taxa de desistências no meio das partidas (os AFKs), de mensagens de hate e de mortes propositais é bem maior.8867607412

    Reply

  24. 5440361742 No League of Legends, se um player descobre que outro pode ser um elo job ou um smurf (como se chamam aqueles que têm contas em elos mais altos, mas jogam em contas com elos mais fracos) é possível denunciar e fazer com que aquela conta seja conferida. Se isso acontecer, você pode perder sua conta. 3600293711

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *