「Bzoj1001」狼抓兔子

发表于 更新于 分类于 评论数： 阅读次数：

来源和评测点

BeiJing2006
Bzoj1001

题目

「题目大意」
现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：

左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4)。
有以下三种类型的道路：
1:(x,y)<==>(x+1,y)
2:(x,y)<==>(x,y+1)
3:(x,y)<==>(x+1,y+1)
道路上的权值表示这条路上最多能够通过的兔子数，道路是无向的。
左上角和右下角为兔子的两个窝，开始时所有的兔子都聚集在左上角(1,1)的窝里，现在它们要跑到右下解(N,M)的窝中去，狼王开始伏击这些兔子。
当然为了保险起见，如果一条道路上最多通过的兔子数为K，狼王需要安排同样数量的K只狼，
才能完全封锁这条道路。
你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。
「输入格式」
第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.
输入文件保证不超过10M
「输出格式」
输出一个整数，表示参与伏击的狼的最小数量.
「输入样例」
3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
「输出样例」
14

分析1

网络流教程和题目分类参见：
「OI之路」03图论算法-4网络流
其他最小割题目参见：Tag-最小割

一看就是最小割

代码1

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
/**************************************************************
	Problem: 1001
	User: Zory
	Language: C++
	Result: Accepted
	Time:1256 ms
	Memory:85196 kb
****************************************************************/
 
//最小割
#include<cstdio>
//#include<cstdlib>
#include<cstring>
//#include<cctype>
#include<cmath>
//#include<ctime>
//#include<queue>
#include<set>
//#include<stack>
//#include<iostream>
//#include<string>
//#include<iomanip>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymax(int a,int b)
{
	return a>b?a:b;
}
int mymin(int a,int b)
{
	return a>b?b:a;
}
/*int myabs(int a)
{
	return a>0?a:-a;
}
void myswap(int &x,int &y)
{
	int t=x;x=y;y=t;
}*/
int read()
{
	int s=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while(c>='0' and c<='9') s=s*10+c-'0',c=getchar();
	return s;
}
//*******************定义*******************
const int Maxn=1100000,Maxm=6100000;
int st,ed;
int hou[Maxn],h[Maxn];
struct nod
{
	int y,c;int gg;
}e[Maxm];
//*******************实现*******************
int ln;
void ins(int x,int y,int c)
{
	ln++;
	e[ln].y=y;e[ln].c=c;
	e[ln].gg=hou[x];hou[x]=ln;
}
int getoth(int x) { return (x%2==0)?x-1:x+1; }
int q[Maxn];
bool bfs()
{
	memset(h,0,sizeof(h));
	q[1]=st;h[st]=1;
	int tou=1,wei=1;
	while(tou<=wei)
	{
		int x=q[tou];
		for(int k=hou[x];k>0;k=e[k].gg)
		{
			int y=e[k].y;
			if(h[y]==0 and e[k].c>0 )
			{
				h[y]=h[x]+1;
				q[++wei]=y;
				if(y==ed) return 1;
			}
		}
		tou++;
	}
	return 0;
}
int dfs(int x,int s)
{
	if(x==ed) return s;
	int t=0;
	for(int k=hou[x];k>0;k=e[k].gg )
	{
		int y=e[k].y;
		if(h[y]==h[x]+1 and e[k].c>0 and t<s )
		{
			int b=dfs(y,mymin(e[k].c,s-t));
			e[k].c-=b;e[getoth(k)].c+=b;t+=b;
			if(s==t) return s;
		}
	}
	if(t==0) h[x]=0;
	return t;
}
//*******************接口*******************
int n,m;
int pt(int x,int y)
{
	return (x-1)*m+y;
}
//*******************主函数*******************
int tx[3]={0,1,1};int ty[3]={1,0,1};
int main(int argc, char *argv[])
{
	scanf("%d%d",&n,&m);
	ln=0;
	for(int k=0;k<=2;k++)
		for(int i=1;i<=((k==0)?n:n-1);i++)
			for(int j=1;j<=((k==1)?m:m-1);j++)
			{
				int x=pt(i,j),y=pt(i+tx[k],j+ty[k]),c=read();
				ins(x,y,c);ins(y,x,c);
			}
				 
	st=1;ed=pt(n,m);
	 
	int ans=0;
	while(bfs()) ans+=dfs(st,INF);
	printf("%d\n",ans);
}

分析2

可以将网格图转化为对偶图
可以参考论文：https://wenku.baidu.com/view/8f1fde586edb6f1aff001f7d

代码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
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
147
148
149
150
151
152
153
154
155
156
157
158
159
/**************************************************************
	Problem: 1001
	User: Zory
	Language: C++
	Result: Accepted
	Time:1536 ms
	Memory:126332 kb
****************************************************************/
 
//Dijkstra
#include<cstdio>
//#include<cstdlib>
#include<cstring>
//#include<cctype>
#include<cmath>
//#include<ctime>
#include<queue>
//#include<set>
//#include<stack>
//#include<iostream>
//#include<string>
//#include<iomanip>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymax(int a,int b)
{
	return a>b?a:b;
}
int mymin(int a,int b)
{
	return a>b?b:a;
}
/*int myabs(int a)
{
	return a>0?a:-a;
}
void myswap(int &x,int &y)
{
	int t=x;x=y;y=t;
}*/
int read()
{
	int s=0;char c=getchar();
	while(c<'0' or c>'9') c=getchar();
	while(c>='0' and c<='9') s=s*10+c-'0',c=getchar();
	return s;
}
//*******************定义*******************
const int Maxn=2100000,Maxm=8100000;
struct nod1
{
	int hou,ans;
}p[Maxn];
struct nod2
{
	int y,c;int gg;
}e[Maxm];
int st,ed;
//*******************实现*******************
int ln;
void ins(int x,int y,int c)
{
	ln++;
	e[ln].y=y;e[ln].c=c;
	e[ln].gg=p[x].hou;
	p[x].hou=ln;
	 
	ln++;
	e[ln].y=x;e[ln].c=c;
	e[ln].gg=p[y].hou;
	p[y].hou=ln;
}
typedef pair<int,int> P;
priority_queue< P,vector<P>,greater<P> > q;
void Dijkstra()
{
	while(!q.empty()) q.pop();
	p[st].ans=0;
	q.push(make_pair(0,st));
	 
	while(!q.empty())
	{
		P s=q.top();q.pop();
		int x=s.second;
		if(s.first>p[x].ans) continue;
		for(int k=p[x].hou;k>0;k=e[k].gg)
		{
			int y=e[k].y;
			if(p[y].ans>p[x].ans+e[k].c)
			{
				p[y].ans=p[x].ans+e[k].c;
				q.push(make_pair(p[y].ans,y));
			}
		}
	}
}
//*******************接口*******************
int a,b;
int pt(int x,int y)
{
	return (x-1)*b+y;
}
//*******************主函数*******************
int t[3][1100][1100];
int main(int argc, char *argv[])
{
	int n,m;scanf("%d%d",&n,&m);
	if(n==1 or m==1)
	{
		if(n>m) swap(n,m);
		int ans=INF;
		for(int i=1,a;i<m;i++)
		{
			scanf("%d",&a);
			ans=mymin(ans,a);
		}
		printf("%d",ans==INF?0:ans);
		return 0;
	}
		 
	for(int k=0;k<=2;k++)
		for(int i=1;i<=(k==0?n:n-1);i++)
			for(int j=1;j<=(k==1?m:m-1);j++)
				t[k][i][j]=read();
			 
	ln=0;
	a=(n-1)*2,b=m-1;
	int cnt=a*b;
	for(int i=1;i<=cnt+2;i++)
	{
		p[i].ans=INF;
		p[i].hou=0;
	}
 
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++)
			if(i%2==0)
			{
				ins(pt(i,j),pt(i-1,j),t[2][i/2][j]);
			}
			else
			{
				if(i>1) ins(pt(i,j),pt(i-1,j),t[0][(i+1)/2][j]);
				if(j<b) ins(pt(i,j),pt(i+1,j+1),t[1][(i+1)/2][j+1]);
			}
			 
	st=cnt+1;ed=cnt+2;
	for(int i=2;i<=a;i+=2)
		ins(st,pt(i,1),t[1][i/2][1]),//左
		ins(pt(i-1,b),ed,t[1][i/2][m]);//右
	for(int j=1;j<=b;j++)
		ins(st,pt(a,j),t[0][n][j]),//下
		ins(pt(1,j),ed,t[0][1][j]);//上
 
	Dijkstra();
 
	printf("%d",p[ed].ans);
}
相关文章推荐

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址：http://zory.ink/posts/9c9f.html
转载请注明出处，谢谢！