为什么只有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;
}
这份网络流的板子是之前用过的,应该没有错吧~~