【平面图最大流转最短路】狼抓兔子

图论, 网络流

传送门：BZOJ1001 BeiJing2006什么鬼比赛？

思路一：直接最大流（听说慢？）

思路二：平面图最大流转最短路。就是说这张图的割一定是由连续的几个三角形区域构成的，相当于一条从左下方到右上方的路径，边权等于跨过的边的容量。跑最短路。

注意：本菜鸡写代码较弱，导致需要特判n==1 || m==1的情况。（对拍愣是没拍出来，对拍的dalao貌似并没有些特判，结果A了）

思路二代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 1000000000
#define M 2100030
int n,m,s,t,x,tot,ans;
int dis[M],head[M],q[M];
bool vis[M];
struct edge{int v,dist,nxt;}e[4*M];
void add(int x,int y,int z){
	e[++tot].v=y; e[tot].dist=z; e[tot].nxt=head[x]; head[x]=tot;
	e[++tot].v=x; e[tot].dist=z; e[tot].nxt=head[y]; head[y]=tot;
}
void spfa(int s,int t){
	for (int i=0;i<=t;i++) dis[i]=INF;
	int tt=0,ww=1;
	q[1]=s; dis[s]=0; vis[s]=1;
	while (tt!=ww){
		tt=tt%M+1; int v=q[tt]; vis[v]=0;
		for (int i=head[v];i;i=e[i].nxt)
			if (dis[e[i].v]>dis[v]+e[i].dist){
				dis[e[i].v]=dis[v]+e[i].dist;
				if (!vis[e[i].v]){vis[e[i].v]=1; ww=ww%M+1; q[ww]=e[i].v;}
			}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	if (n==1){
	    ans=INF;
	    for (int i=1;i<m;i++){scanf("%d",&x); ans=min(ans,x);}
	    printf("%d\n",ans); return 0;
	}
	if (m==1){
	    ans=INF;
	    for (int i=1;i<n;i++){scanf("%d",&x); ans=min(ans,x);}
	    printf("%d\n",ans); return 0;
	}
	s=n*m*2+1; t=s+1;
	
	for (int i=1;i<m;i++){
		scanf("%d",&x);
		add(i,t,x);
	}
	for (int i=2;i<n;i++)
		for (int j=1;j<m;j++){
			scanf("%d",&x);
			add((i*2-2)*(m-1)+j,(i*2-3)*(m-1)+j,x);
		}
	for (int i=1;i<m;i++){
		scanf("%d",&x);
		add(s,(n*2-3)*(m-1)+i,x);
	}
	
	for (int i=1;i<n;i++){
		scanf("%d",&x); add(s,(i*2-1)*(m-1)+1,x);
		for (int j=2;j<m;j++){
			scanf("%d",&x);
			add((i*2-2)*(m-1)+j-1,(i*2-1)*(m-1)+j,x);
		}
		scanf("%d",&x); add((i*2-2)*(m-1)+m-1,t,x);
	}
	
	for (int i=1;i<n;i++)
		for (int j=1;j<m;j++){
			scanf("%d",&x);
			add((i*2-1)*(m-1)+j,(i*2-2)*(m-1)+j,x);
		}
	
	spfa(s,t);
	
	printf("%d\n",dis[t]);
	
	return 0;
}