Codeforces 727D T-shirts Distribution

简单的最大流
每个块拆成进出两个点中间连流量为费用的边
所有出点向上下左右的入点连流量为无穷的边
RC所在的点权值改成无穷,其出点作为汇点
从超级源向所有边界上的点连流量为无穷的边
最小割即为答案

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
include<iostream>
include<cstdio>
include<queue>
include<algorithm>
include<cstring>
include<cmath>
using namespace std;
#define maxn 5005
#define maxm 50005
#define rever(x) (mem+((x-mem)^1))
#define INF 2147483647
struct edge
{
int s,t,v;
edge* next;
}mem[maxm*2],*head[maxn];
int cnt=-1;
void add_edge(int s,int t,int v)
{ mem[++cnt].s=s;mem[cnt].t=t;mem[cnt].v=v;mem[cnt].next=head[s];head[s]=mem+cnt; mem[++cnt].s=t;mem[cnt].t=s;mem[cnt].v=0;mem[cnt].next=head[t];head[t]=mem+cnt;
}
int n,m;
int S,T;
int numbs[maxn];
int d[maxn];
edge* cur[maxn],*revpath[maxn];
void bfs()
{
queue<int> q;
while(!q.empty()) q.pop();
for (int i=0;i<=n;i++) d[i]=maxn-1;
d[T]=0;q.push(T);
while(!q.empty())
{
int u=q.front();
q.pop();
for (edge* it=head[u];it;it=it->next)
{
edge *now=rever(it);
if (now->v==0||d[now->s]<n) continue;
d[now->s]=d[u]+1;
q.push(now->s);
}
}
memset(numbs,0,sizeof(numbs));
for (int i=0;i<=n;i++) numbs[d[i]]++;
}
int isap()
{
int flow=0;
for (int i=0;i<=n;i++) cur[i]=head[i];
int u=S;
while(d[S]<n)
{
if (u==T)
{
int augflow=2147483647;
for (int i=S;i!=T;i=cur[i]->t)
augflow=min(augflow,cur[i]->v);
for (int i=S;i!=T;i=cur[i]->t)
{
cur[i]->v-=augflow;
rever(cur[i])->v+=augflow;
}
flow+=augflow;u=S;
}
edge *e;
for (e=cur[u];e;e=e->next)
if (e->v&&d[u]==(d[e->t]+1)) break;
if (e)
{
cur[u]=e;
revpath[e->t]=rever(e);
u=e->t;
}
else
{
numbs[d[u]]--;
if (numbs[d[u]]==0) break;
cur[u]=head[u];
int mindist=n;
for (edge* it=head[u];it;it=it->next)
if (it->v) mindist=min(mindist,d[it->t]);
d[u]=mindist+1;
numbs[d[u]]++;
if (u!=S) u=revpath[u]->t;
}
}
return flow;
}
int N,M,R,C,A;
inline int fi(int x,int y) {return ((x-1)*M+y)*2-1;}
inline int se(int x,int y) {return ((x-1)*M+y)*2;}
bool vis[50005];
void find()
{
queue<int> q;
q.push(S);vis[S]=1;
while(!q.empty())
{
int now=q.front();q.pop();
for (edge* it=head[now];it;it=it->next)
if (!vis[it->t]&&it->v) {q.push(it->t);vis[it->t]=1;}
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d%d%d%d",&N,&M,&R,&C);
cnt=-1;S=0;T=se(R,C);n=N*M*2;
memset(head,0,sizeof(head));
for (int i=1;i<=N;i++)
for (int j=1;j<=M;j++)
{
scanf("%d",&A);
if (i==R&&j==C) {add_edge(fi(i,j),se(i,j),INF);continue;}
add_edge(fi(i,j),se(i,j),A);
if (i==1||i==N||j==1||j==M) add_edge(S,fi(i,j),INF);
if (i!=N) add_edge(se(i,j),fi(i+1,j),INF);
if (i!=1) add_edge(se(i,j),fi(i-1,j),INF);
if (j!=M) add_edge(se(i,j),fi(i,j+1),INF);
if (j!=1) add_edge(se(i,j),fi(i,j-1),INF);
}
bfs();
printf("%d\n",isap());
find();
for (int i=1;i<=N;i++)
{
for (int j=1;j<=M;j++)
printf("%c",vis[fi(i,j)]^vis[se(i,j)]?'X':'.');
printf("\n");
}
return 0;
}