BZOJ5120无限之环-费用流

传送门

题意:

看原题吧,想不出比原题更好的描述了- -

Solution:

​ 一开始思考过用网络流,但是想不出如何建图,最后还是去看了题解QwQ,建图思路很妙啊,我们先把每个点拆成四个小点,分别对应上,下,左,右,然后对应每种水管在点内分别建图(细节大家可以结合代码思考一下),由于这是一个二分图(拆点之前),所以说我们对每个点进行黑白染色,这样便可以确定每个点是连向T还是从S连过来,点与点之间都要建流量为1,费用为0的边,最后跑费用流即可,注意这里我们的流量表示的是“最大能匹配到的水管数量”,同时注意我们连边的顺序。

代码:

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
140
141
142
143
144
145
146
#include<cstdio>
#include<iostream>
using namespace std;
const int NM=2010;
const int N=8010;
struct edg{
int flow,v,to,next;
}e[20*N];
int tot=0;
int head[N];
int n,m,size=1,S,T;
int id[NM][NM][4];
int kx[4]={-1,0,1,0};
int ky[4]={0,1,0,-1};
int pre[N],prv[N];
bool vis[N];
int dis[N];
int q[N*N];
void adde(int i,int j,int v,int f)
{
size++;e[size].to=j;e[size].next=head[i];e[size].flow=f;e[size].v=v;head[i]=size;
size++;e[size].to=i;e[size].next=head[j];e[size].flow=0;e[size].v=-v;head[j]=size;
}
void add(int i,int j,int v,int f,int b)
{
if (b) adde(i,j,v,f);
else if (i==S) adde(j,T,v,f);
else adde(j,i,v,f);
}
void work(int i,int j,int type,int pos,int b)
{
if (type==1)
{
add(S,id[i][j][pos],0,1,b);
add(id[i][j][pos],id[i][j][(pos+1)%4],1,1,b);
add(id[i][j][pos],id[i][j][(pos+2)%4],2,1,b);
add(id[i][j][pos],id[i][j][(pos+3)%4],1,1,b);
}
else if (type==2)
{
add(S,id[i][j][pos],0,1,b);
add(S,id[i][j][(pos+1)%4],0,1,b);
add(id[i][j][pos],id[i][j][(pos+2)%4],1,1,b);
add(id[i][j][(pos+1)%4],id[i][j][(pos+3)%4],1,1,b);
}
else if (type==3)
{
add(S,id[i][j][pos],0,1,b);
add(S,id[i][j][(pos+1)%4],0,1,b);
add(S,id[i][j][(pos+2)%4],0,1,b);
add(id[i][j][pos],id[i][j][(pos+3)%4],1,1,b);
add(id[i][j][(pos+1)%4],id[i][j][(pos+3)%4],2,1,b);
add(id[i][j][(pos+2)%4],id[i][j][(pos+3)%4],1,1,b);
}
else if (type==4)
{
add(S,id[i][j][pos],0,1,b);
add(S,id[i][j][(pos+2)%4],0,1,b);
}
else
{
add(S,id[i][j][pos],0,1,b);
add(S,id[i][j][(pos+1)%4],0,1,b);
add(S,id[i][j][(pos+2)%4],0,1,b);
add(S,id[i][j][(pos+3)%4],0,1,b);
}
}
bool SPFA()
{
for (int i=S;i<=T;i++)
vis[i]=0,dis[i]=1e9;
int h=0,t=0;
int x,y;
q[++t]=S;
vis[S]=1;
dis[S]=0;
while (h<t)
{
x=q[++h];vis[x]=0;
for (int i=head[x];i;i=e[i].next)
{
y=e[i].to;
if (e[i].flow&&dis[y]>dis[x]+e[i].v)
{
dis[y]=dis[x]+e[i].v;
pre[y]=x;
prv[y]=i;
if (!vis[y])
{
q[++t]=y;
vis[y]=1;
}
}
}
}
return (dis[T]!=1e9);
}
int main()
{
scanf("%d%d",&n,&m);
S=0;T=n*m*4+1;
int sum=0;
for (int x,i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d",&x);
for (int k=0;k<4;k++)
id[i][j][k]=++tot;
if (x==1) work(i,j,1,0,(i+j)&1),sum++;
else if (x==2) work(i,j,1,1,(i+j)&1),sum++;
else if (x==3) work(i,j,2,0,(i+j)&1),sum+=2;
else if (x==4) work(i,j,1,2,(i+j)&1),sum++;
else if (x==5) work(i,j,4,0,(i+j)&1),sum+=2;
else if (x==6) work(i,j,2,1,(i+j)&1),sum+=2;
else if (x==7) work(i,j,3,0,(i+j)&1),sum+=3;
else if (x==8) work(i,j,1,3,(i+j)&1),sum+=1;
else if (x==9) work(i,j,2,3,(i+j)&1),sum+=2;
else if (x==10) work(i,j,4,1,(i+j)&1),sum+=2;
else if (x==11) work(i,j,3,3,(i+j)&1),sum+=3;
else if (x==12) work(i,j,2,2,(i+j)&1),sum+=2;
else if (x==13) work(i,j,3,2,(i+j)&1),sum+=3;
else if (x==14) work(i,j,3,1,(i+j)&1),sum+=3;
else if (x==15) work(i,j,5,0,(i+j)&1),sum+=4;
}
for (int i=1,j,_x,_y;i<=n;i++)
for (j=1;j<=m;j++)
if ((i+j)&1)
for (int k=0;k<4;k++)
{
_x=i+kx[k],_y=j+ky[k];
if (_x>=1&&_x<=n&&_y>=1&&_y<=m)
adde(id[i][j][k],id[_x][_y][(k+2)%4],0,1);
}
int ansv=0,ansf=0;
while (SPFA())
{
int F=1e9;
for (int i=T;i!=S;i=pre[i])
F=min(F,e[prv[i]].flow);
ansv+=F*dis[T];
ansf+=F;
for (int i=T;i!=S;i=pre[i])
e[prv[i]].flow-=F,e[prv[i]^1].flow+=F;
}
printf("%d",(ansf==sum/2)?ansv:-1);
}
作者

Fizzmy

发布于

2018-01-05

更新于

2020-11-06

许可协议

评论