BZOJ1001 [BeiJing2006]狼抓兔子

把每一个三角形看作一个顶点,最大流转最短路,可以较快,当然也可以跑最大流。

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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxv = 1005*1005*2;
int first[maxv],nume;
int N,M,x;
struct Edge{
int to,nxt,dist;
}edge[maxv*3];
int q[maxv],front,rear,dist[maxv];
bool vis[maxv];
int spfa(int s,int t){
int u,v;
memset(dist,0x3f,sizeof(dist));
memset(vis,false,sizeof(vis));
front = rear = 0;
q[rear++] = s;
dist[s] = 0;vis[s] = true;
while (front!=rear){
u = q[front++];
if (front == maxv-1) front = 0;
for (int e = first[u];~e;e=edge[e].nxt) {
v = edge[e].to;
if (dist[v]>dist[u]+edge[e].dist){
dist[v] = dist[u]+edge[e].dist;
if (!vis[v]){
vis[v] = true;
q[rear++] = v;
if (rear == maxv-1) rear = 0;
}
}
}
vis[u] = false;
}
return dist[t];
}
void add_edge(int a,int b,int c){
edge[nume] . to = b;
edge[nume] . nxt = first[a];
edge[nume] . dist = c;
first[a] = nume++;
edge[nume] . to = a;
edge[nume] . nxt = first[b];
edge[nume] . dist = c;
first[b] = nume++;
}
int main(){
scanf("%d%d",&N,&M);
if (N==1||M==1){
int ans = 0x3fffffff;
for (int i=1;i<=max(N,M);i++){
scanf("%d",&x);
ans = min(ans,x);
}
printf("%d\n",ans);
return 0;
}
nume = 0;
memset(first,-1,sizeof(first));
for (int j=1;j<=M-1;j++){
scanf("%d",&x);
add_edge(0,j,x);
}
for (int i=1;i<=N-2;i++){
for (int j=1;j<=M-1;j++){
scanf("%d",&x);
add_edge(2*(i-1)*(M-1)+M-1+j,2*i*(M-1)+j,x);
}
}
for (int j=1;j<=M-1;j++){
scanf("%d",&x);
add_edge(2*(N-2)*(M-1)+M-1+j,2*(N-1)*(M-1)+1,x);
}
for (int i=1;i<=N-1;i++){
scanf("%d",&x);
add_edge(2*(i-1)*(M-1)+M-1+1,2*(N-1)*(M-1)+1,x);
for (int j=2;j<=M-1;j++){
scanf("%d",&x);
add_edge(2*(i-1)*(M-1)+j-1,2*(i-1)*(M-1)+M-1+j,x);
}
scanf("%d",&x);
add_edge(0,2*(i-1)*(M-1)+M-1,x);
}
for (int i=1;i<=(N-1);i++){
for (int j=1;j<=M-1;j++){
scanf("%d",&x);
add_edge(2*(i-1)*(M-1)+j,2*(i-1)*(M-1)+(M-1)+j,x);
}
}
printf("%d\n",spfa(0,2*(N-1)*(M-1)+1));
return 0;
}
文章目录