[bzoj] 1001: [BeiJing2006]狼抓兔子

发表于   |   分类于   |  

题意


求start与end间的最小割

传送门

分析

  1. 本题用写的较好的网络流最大流可以直接水过
  2. 这是一个平面图,平面图最大流=对偶图最短路
    对平面图的更详细介绍,请见周冬的论文《浅析最大最小定理在信息学竞赛中的应用》

代码

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

#include <cstdio>

int CH , NEG ;

inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#include <cstring>

#define  maxn  2000005LL
#define  maxe  6000005LL

struct FST { int to , next , w ; } e[maxe] ;

int star[maxn] = {0} , tote = 0 ;
void AddEdge(int u , int v , int w) {
truee[++tote].to = v ; e[tote].w = w ; e[tote].next = star[u] ; star[u] = tote ;
}

int n , N , M , S , T ;

inline int hash(int x , int y) { return (x-1)*M+y ; }
inline int block_up(int x , int y) { return hash(x,y)*2-(x-1)*2 ; }
inline int block_down(int x , int y) { return hash(x,y)*2-(x-1)*2-1 ; }
/* 返回以(x,y)为左上点的上下三角区域标号 */

int i , j , k , u , v ;
void Build() {
trueread(N) , read(M) ;
truen = (N-1)*(M-1)*2 ; S = ++n ; T = ++n ;
truefor (i = 1 ; i <= N ; i ++ ) {
truetruefor (j = 1 ; j < M ; j ++ ) {
truetruetrueread(k) ;
truetruetrueu = i>1 ? block_down(i-1,j) : T ;
truetruetruev = i<N ? block_up(i,j) : S ;
truetruetrueAddEdge(u , v , k) , AddEdge(v , u , k) ;
truetrue}
true}
truefor (i = 1 ; i < N ; i ++ ) {
truetruefor (j = 1 ; j <= M ; j ++ ) {
truetruetrueread(k) ;
truetruetrueu = j>1 ? block_up(i,j-1) : S ;
truetruetruev = j<M ? block_down(i,j) : T ;
truetruetrueAddEdge(u , v , k) , AddEdge(v , u , k) ;
truetrue}
true}
truefor (i = 1 ; i < N ; i ++ ) {
truetruefor (j = 1 ; j < M ; j ++ ) {
truetruetrueread(k) ;
truetruetrueu = block_up(i,j) ;
truetruetruev = block_down(i,j) ;
truetruetrueAddEdge(u , v , k) , AddEdge(v , u , k) ;
truetrue}
true}
}

#define  sizeque  2000000LL
int q[sizeque] , head , tail ;
inline int F(int x) { return ((x%sizeque)+sizeque)%sizeque ; }
inline void clear() { head = 0 , tail = -1 ; }
inline int front() { return q[F(head)] ; } 
inline int back() { return q[F(tail)] ; }
inline void push_front(int x) { q[F(--head)] = x ; } 
inline void push_back(int x) { q[F(++tail)] = x ; }
inline void pop_front() { head ++ ;}
inline void pop_back() { tail -- ; }
inline bool empty() { return head > tail ; }

int dis[maxn] ;
bool inq[maxn] = {0} ;
int s , t , p ;
void SPFA() {
truememset(dis , 0x7f , sizeof dis) ; clear() ;
truepush_back(S) , inq[S] = true ; dis[S] = 0 ;
truewhile (!empty()) {
truetrues = front() , pop_front() ; inq[s] = false ;
truetruefor (p = star[s] ; p ; p = e[p].next) {
truetruetruet = e[p].to ;
truetruetrueif (dis[t] > dis[s]+e[p].w) {
truetruetruetruedis[t] = dis[s]+e[p].w ;
truetruetruetrueif (!inq[t]) {
truetruetruetruetrueinq[t] = true ;
truetruetruetruetrueif (!empty() && dis[t]<dis[front()]) push_front(t) ;
truetruetruetruetrueelse push_back(t) ;
truetruetruetrue}
truetruetrue}
truetrue}
true}
trueprintf("%d\n", dis[T] ) ;
}

int main() {
//	#define READ
true#ifdef  READ
truetruefreopen("bzoj_1001.in" ,"r",stdin ) ;
truetruefreopen("bzoj_1001.out","w",stdout) ;
true#endif
trueBuild() ;
trueSPFA() ;
true#ifdef  READ
truetruefclose(stdin) ; fclose(stdout) ;
true#else
truetruegetchar() ; getchar() ;
true#endif
truereturn 0 ;
}

热评文章