BZOJ1412 [ZJOI2009]狼和羊的故事

题解

​ 对于相邻的,从1向2连条边,从1先0连边,从0向2连边。这些边权为1

​ 源点到1一条inf的边,2到汇点一条inf的边,然后跑最小割。

关于SAP和DINIC

​ 我第一个学的最大流算法是SAP——网上有些说是ISAP,然后为了简短,我都不写第一遍的BFS(据说时间不会因此特别慢)。

​ 然后后来我听说了DINIC算法,于是差不多会写,但是因为还是SAP熟练,所以一般不写,也差不多不会写了。

​ 后来看ZKW费用流怎么这么像DINIC,于是打算restudy(写)DINIC。

(UPDATE:大概我的眼睛和大脑不同步,或者网上的题解太黑心。是EK改SPFA的优化像Dinic而已……听说zkw实现基于KM和ISAP的增广。)

​ 看了网上很多讨论,都说毕竟只是一个实现的工具,重要是建图。

​ 毕竟SAP(+当前弧优化,+GAP优化)的复杂度比DINIC要优。

​ 但是听说DINIC短。这无可厚非。

​ 那就写DINIC吧。

为了比较,我把DINIC和SAP都写了一遍。在BZOJ上测试——以下分析请手动忽略0.72KB的头文件。

我写的SAP(没有一开始的BFS,不然真的太长(其实只是码力不足的借口)

​ 长度:3714KB。平均测试时间:108ms。取样:3次(防止评测机不稳定,然而三次都是108)

我写的DINIC

​ 长度2337KB。平均测试时间:112ms。取样:9次(最快一次96ms2333)

貌似$hzwer$的DINIC平均92ms。

网上某ISAP:104ms。

网上某DINIC:64ms。%%%——还只有1600KB。
UPDATE:我把自己的代码改成反向(加了2B)的BFS貌似只用了84ms。——嗯,以后都用反向吧。

话说BZOJ的rank榜单第一第二的15ms是什么?最高标号预留推进?然而听说很麻烦。可怎么只有1600KB?

貌似ISAP跑出来都很稳定的样子。测了好几遍都不边。

如此说来,我写的程序自带大常数。

贴上我丑陋的以上测试中最慢的代码。

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
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define gc getchar
#define pc putchar
inline int read(){int x=0,f=1;char c=gc();for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(;c>='0'&&c<='9';c=gc())x=x*10+c-48;return x*f;}
inline void write(int x){if(x < 0) putchar('-'),x = -x;if (x>=10) write(x / 10);putchar((x % 10)+'0');}
inline void writeln(int x){write(x);puts("");}
const int oo = 0x7fffffff;const int inf = oo;
#define mem(x,v) memset(x,v,sizeof(x))
typedef unsigned long long ull;
#define rep(i,a,b) for(register int i=(a);i<(b);++i)
#define N 105*105
//-------------------------------------------一下主题部分
const int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
struct Edge{int to,nxt,cap;Edge(int to=0,int nxt=0,int cap=0):to(to),nxt(nxt),cap(cap){};}edge[N*5*2];
int first[N],q[N],dis[N],cur[N],nume;
inline void Addedge(int a,int b,int c){
edge[nume]=Edge(b,first[a],c);first[a]=nume++;
edge[nume]=Edge(a,first[b],0);first[b]=nume++;
}
int S,T;
//------------------一下Dinic部分
inline bool bfs(){
register int front,rear,v,u,e;
mem(dis,-1);front=rear=0;q[rear++]=S;dis[S]=0;
while(front<rear){
u=q[front++];
for(e=first[u];~e;e=edge[e].nxt){
int v=edge[e].to;
if(edge[e].cap&&!~dis[v])
dis[v]=dis[u]+1,q[rear++]=v;
}
}
return dis[T]!=-1;
}
inline int dfs(int u,int flow){
if(u==T)return flow;
for (int&e=cur[u];~e;e=edge[e].nxt){
int v=edge[e].to,d;
if(edge[e].cap&&dis[v]==dis[u]+1&&(d=dfs(v,min(flow,edge[e].cap)))){
edge[e].cap-=d,edge[e^1].cap+=d;
return d;
}
}
return 0;
}
int n,m,a[105][105];
inline int dinic(){
int ans=0,flow;
while(bfs()){
rep(i,0,n*m+2)cur[i]=first[i];
while(flow=dfs(S,inf))ans+=flow;
}
return ans;
}
//-----------------------以上Dinic部分
int main(){
n = read(),m = read();
S = 0,T = n*m+1;
mem(first,-1),nume=0;
rep(i,0,n)rep(j,0,m){
a[i][j] = read();int pos = i*m+j+1;
if(a[i][j]==2) Addedge(pos,T,inf);
if(a[i][j]==1) Addedge(S,pos,inf);
rep(d,0,4){
int x=i+dx[d],y=j+dy[d];
if(x<0||y<0||x>=n||y>=m) continue;
int _pos = x*m+y+1;
if(a[i][j]!=2&&a[x][y]!=1) Addedge(pos,_pos,1);
}
}
writeln(dinic());
return 0;
}

我的Dinic写的确实有点丑。网上很多多路增广的做法。不管也就是常数的问题。

其实效率差别可能在某些时候有一些差别吧?但是正常的情况下总不会特意来卡。

说到底了还是建图最重要。

文章目录
  1. 1. 题解
  2. 2. 关于SAP和DINIC