蒟蒻求助
查看原帖
蒟蒻求助
179160
佐世保の时雨楼主2021/11/14 19:59

为什么只有25分呀???

// =============================================
// 暁の水平线に胜利を刻むのです!
// Author: 佐世保の时雨
// Blog: https://www.cnblogs.com/SasebonoShigure
// =============================================

#include <queue>
#include <cstdio>
#include <iostream>

using namespace std;

const int Maxn = 5e5 + 10;

int Head[Maxn], Total = 1;
long long Cost[Maxn << 2];
int Next[Maxn >> 2], To[Maxn << 2];

inline void Addedge (const int u, const int v, const long long c) {
	To[++ Total] = v, Cost[Total] = c, Next[Total] = Head[u], Head[u] = Total;
	To[++ Total] = u, Cost[Total] = 0, Next[Total] = Head[v], Head[v] = Total;
	return ;
}

queue <int> Q;

int n, m, Count, S, T, R, C, x, y, Answer;
int Pos[Maxn], Depth[Maxn];

inline bool Search () {
	while (!Q.empty () ) {
		Q.pop ();
	}
	
	for (int i = 1; i <= T; ++ i ) {
		Depth[i] = -1;
	}
	
	Depth[S] = 0, Q.push (S), Pos[S] = Head[S];
	
	while (!Q.empty () ) {
		int Index = Q.front ();
		Q.pop ();
		
		for (int i = Head[Index]; i; i = Next[i] ) {
			if (Cost[i] and Depth[To[i]] == -1 ) {
				Depth[To[i]] = Depth[Index] + 1;
				Pos[To[i]] = Head[To[i]];
				Q.push (To[i]);
				
				if (To[i] == T ) {
					return true;
				}
			}
		}
	}
	
	return false;
}

inline long long Solve (const int Index, const long long Rest) {
	if (Index == T ) {
		return Rest;
	}
	
	long long Flow = 0, Sum;
	
	for (int i = Pos[Index]; i and Rest > Flow; i = Next[i] ) {
		Pos[Index] = i;
		
		if (Cost[i] and Depth[To[i]] == Depth[Index] + 1 ) {
			Sum = Solve (To[i], min (Rest - Flow, Cost[i]));
			
			if (!Sum ) {
				Depth[To[i]] = -1;
				continue ;
			}
			
			Cost[i] -= Sum, Cost[i ^ 1] += Sum, Flow += Sum;
		}
	}
	
	return Flow;
}

inline long long Dinic () {
	long long Res = 0;
	
	while (Search () ) {
		Res += Solve (S, 1ll << 30);
	}
	
	return Res;
}

signed main () {
	scanf ("%d %d %d %d", &n, &m, &R, &C);
	S = 2 * n * m + 1, T = 2 * n * m + 2;
	const int Dict[4][2] = {{C, -R}, {R, -C}, {C, R}, {R, C}};
	
	for (int i = 1; i <= n; ++ i ) {
		getchar ();
		
		for (int j = 1; j <= m; ++ j ) {
			if (getchar () == 'x' ) {
				continue ;
			}
			
			Addedge (S, (i - 1) * m + j, 1);
			Addedge ((i - 1) * m + j + n * m, T, 1);
			
			for (int k = 0; k < 4; ++ k ) {
				x = i + Dict[k][0], y = j + Dict[k][1];
				
				if (x <= n and y > 0 and y <= m ) {
					Addedge ((i - 1) * m + j, (x - 1) * m + y + n * m, 1);
				}
			}
			
			++ Count;
		}
	}
	
	printf ("%lld\n", Count - Dinic ());
	return 0;
}

这份网络流的板子是之前用过的,应该没有错吧~~

2021/11/14 19:59
加载中...