http://www.lydsy.com/JudgeOnline/problem.php?id=1001
1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 24017 Solved: 6068
Description
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
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只狼，
才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input
第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.
输入文件保证不超过10M
Output
输出一个整数，表示参与伏击的狼的最小数量.
Sample Input
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
Sample Output
14
HINT
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
【解析】：
解法1：网络流dinic算法，但需要很多地方优化才能不超时，比如
1.dfs过程中，如果某一步，从某点递归返回的最大流没有正数值，则增广路已经找完，直接把标号d[s]=-1，就能终止递归。
2.bfs标号过程中，只要遇到汇点，就立即return，不做后面的无用功
解法2：把每个环路围成的区域看做一个点，建好图，从右上角往左下角跑一边最短路，就能把图切开。
【代码1】：（dinic）
1. #include <stdio.h>
2. #include <math.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include <iostream>
6. #include <algorithm>
7. #include <queue>
8. #define mset(a,i) memset(a,i,sizeof(a))
9. #define S1(n) scanf("%d",&n)
10. #define S2(n,m) scanf("%d%d",&n,&m)
11. #define P(n) printf("%d\n",n)
12. using namespace std;
13. typedef long long ll;
14. const int INF=0x3f3f3f3f;
15. const int MAX=1e6+5;
16. int n,m;
17. struct node{
18. int u,v,w,next;
19. }edge[6*MAX];
20. int head[MAX];
21. int d[MAX];//给点标号
22. void add(int u,int v,int w) //链式前向星建图
23. {
24. static int cnt=0;
25. edge[cnt].v=v;
26. edge[cnt].w=w;
27. edge[cnt].next=head[u];
28. head[u]=cnt++;
29. }
30. int bfs(int s,int t)
31. {
32. mset(d,0);
33. d[s]=1;
34. int> q;
35. q.push(s);
36. while(!q.empty())
37. {
38. int u=q.front();
39. q.pop();
40. if(u==t) return 1; //到达汇点
41. for(int i=head[u];i!=-1;i=edge[i].next) //搜增广路
42. {
43. int v=edge[i].v; //下一可连通点
44. int w=edge[i].w; //当前流量
45. if(w&&d[v]==0) //temp1没走到
46. {
47. //点加1
48. if(v==t) //找到增广路
49. return 1;
50. //入队列
51. }
52. }
53. }
54. return 0;
55. }
56. int dfs(int s,int t,int maxflow=INF)
57. {
58. if(s==t)
59. return maxflow;
60. int i,j,ret=0;
61. for(i=head[s];i!=-1;i=edge[i].next)
62. {
63. int v=edge[i].v; //下一个可连通点
64. int w=edge[i].w; //当前点的流量
65. if(w&&d[v]==d[s]+1)
66. {
67. int temp=dfs(v,t,min(maxflow-ret,w)); //下一点，取最大流跟当前流量小的一个
68. //正向相减
69. //反向弧相加
70. //最大流
71. if(ret==maxflow) //下一点最大流等于这一点
72. return ret;
73. }
74. }
75. if(!ret)
76. d[s]=-1;
77. return ret;
78. }
79.
80. int dinic(int s,int t)
81. {
82. int ans=0;
83. while(bfs(s,t))
84. {
85. //dfs返回每次的数量
86. }
87. return ans;
88. }
89.
90. int main()
91. {
92. S2(n,m);
93. mset(head,-1);
94. int s,t,cap;
95. for(int i=0;i<n;i++)//横边
96. for(int j=1;j<m;j++)
97. {
98. s=i*m+j;t=s+1;
99. S1(cap);
100. add(s,t,cap);
101. add(t,s,cap);
102. }
103. for(int i=0;i<n-1;i++)//纵边
104. for(int j=1;j<=m;j++)
105. {
106. s=i*m+j;t=s+m;
107. S1(cap);
108. add(s,t,cap);
109. add(t,s,cap);
110. }
111. for(int i=0;i<n-1;i++)//斜边
112. for(int j=1;j<m;j++)
113. {
114. s=i*m+j;t=s+m+1;
115. S1(cap);
116. add(s,t,cap);
117. add(t,s,cap);
118. }
119. int ans=dinic(1,n*m);
120. P(ans);
121. return 0;
122. }
【代码2】（spfa）
1. #include <stdio.h>
2. #include <math.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include <time.h>
6. #include <iostream>
7. #include <algorithm>
8. #include <string>
9. #include <queue>
10. #include <stack>
11. #include <vector>
12. #include <set>
13. #include <list>
14. #include <map>
15. #define mset(a,i) memset(a,i,sizeof(a))
16. #define S1(n) scanf("%d",&n)
17. #define S2(n,m) scanf("%d%d",&n,&m)
18. #define P(n) printf("%d\n",n);
19. #define FIN freopen("input.txt","r",stdin)
20. #define FOUT freopen("output.txt","w",stdout)
21. #define gcd(a,b) __gcd(a,b)
22. using namespace std;
23. typedef long long ll;
24. const double eps=1e-6;
25. const int INF=0x3f3f3f3f;
26. const int mod=1e9+7;
27. const int MAX=1e6+5;
28. const double PI=acos(-1);
29. int dir[5][2]={0,1,0,-1,1,0,-1,0};
30. ll qpow(ll n,ll m){n%=mod;ll ans=1;while(m){if(m%2)
31. return ans;}
32. ll inv(ll b){return b==1?1:(mod-mod/b)*inv(mod%b)%mod;}
33. ll inv2(ll b){return qpow(b,mod-2);}
34. struct node{
35. int s,t,len,next;
36. }edge[6000010];
37. int head[2000100];
38. int n,m,len;
39. int dis[2000100];
40. int tail=1;
41. void add(int s,int t,int l)
42. {
43. edge[tail].s=s;
44. edge[tail].t=t;
45. edge[tail].len=l;
46. edge[tail].next=head[s];
47. head[s]=tail++;
48. }
49. int spfa(int s,int t)
50. {
51. mset(dis,INF);
52. dis[s]=0;
53. int> q; //装 起点
54. q.push(s);
55. while(!q.empty())
56. {
57. int u=q.front();
58. q.pop();
59. for(int i=head[u];i!=-1;i=edge[i].next)
60. {
61. int v=edge[i].t;
62. if(dis[v]>dis[u]+edge[i].len)
63. {
64. dis[v]=dis[u]+edge[i].len;
65. q.push(v);
66. }
67. }
68. }
69. return dis[t];
70. }
71. int main()
72. {
73. S2(n,m);
74. if(n==1&&m==1){
75. "0");
76. return 0;
77. }
78. mset(head,-1);
79. int end=2*(m-1)*(n-1)+1;
80. for(int i=1;i<m;i++){
81. S1(len);
82. add(0,i,len);
83. add(i,0,len);
84. //printf("%d -> %d\n",0,i);
85. }
86. for(int i=1;i<n-1;i++)
87. {
88. for(int j=1;j<m;j++){
89. S1(len);
90. int d=2*(m-1)*i+j;
91. int u=d-(m-1);
92. add(u,d,len);
93. add(d,u,len);
94. //printf("%d -> %d\n",u,d);
95. }
96. }
97. if(n>1)
98. for(int i=1;i<m;i++){
99. S1(len);
100. int u=end-(m-i);
101. add(u,end,len);
102. add(end,u,len);
103. //printf("%d -> %d\n",u,end);
104. }
105.
106. for(int i=0;i<n-1;i++)
107. {
108. S1(len);
109. int r=2*(m-1)*(i+1)-(m-2);
110. if(m==1)r=0;
111. add(r,end,len);
112. add(end,r,len);
113. //printf("%d -> %d\n",r,end);
114. for(int j=1;j<m-1;j++){
115. S1(len);
116. int l=2*(m-1)*i+j;
117. int r=l+m;
118. add(l,r,len);
119. add(r,l,len);
120. //printf("%d -> %d\n",l,r);
121. }
122. if(m<=1)continue;
123. S1(len);
124. int l=2*(m-1)*i+m-1;
125. add(0,l,len);
126. add(l,0,len);
127. //printf("%d -> %d\n",0,l);
128. }
129.
130. for(int i=0;i<n-1;i++)
131. {
132. for(int j=1;j<m;j++){
133. S1(len);
134. int u=2*(m-1)*i+j;
135. int d=u+m-1;
136. add(u,d,len);
137. add(d,u,len);
138. //printf("%d -> %d\n",u,d);
139. }
140. }
141. int ans=spfa(0,end);
142. P(ans);
143. return 0;
144. }
http://www.lydsy.com/JudgeOnline/problem.php?id=1001
1001: [BeiJing2006]狼抓兔子
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 24017 Solved: 6068
Description
现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的，
而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形：
左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路
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只狼，
才能完全封锁这条道路，你需要帮助狼王安排一个伏击方案，使得在将兔子一网打尽的前提下，参与的
狼的数量要最小。因为狼还要去找喜羊羊麻烦.
Input
第一行为N,M.表示网格的大小，N,M均小于等于1000.
接下来分三部分
第一部分共N行，每行M-1个数，表示横向道路的权值.
第二部分共N-1行，每行M个数，表示纵向道路的权值.
第三部分共N-1行，每行M-1个数，表示斜向道路的权值.
输入文件保证不超过10M
Output
输出一个整数，表示参与伏击的狼的最小数量.
Sample Input
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
Sample Output
14
HINT
2015.4.16新加数据一组，可能会卡掉从前可以过的程序。
【解析】：
解法1：网络流dinic算法，但需要很多地方优化才能不超时，比如
1.dfs过程中，如果某一步，从某点递归返回的最大流没有正数值，则增广路已经找完，直接把标号d[s]=-1，就能终止递归。
2.bfs标号过程中，只要遇到汇点，就立即return，不做后面的无用功
解法2：把每个环路围成的区域看做一个点，建好图，从右上角往左下角跑一边最短路，就能把图切开。
【代码1】：（dinic）
1. #include <stdio.h>
2. #include <math.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include <iostream>
6. #include <algorithm>
7. #include <queue>
8. #define mset(a,i) memset(a,i,sizeof(a))
9. #define S1(n) scanf("%d",&n)
10. #define S2(n,m) scanf("%d%d",&n,&m)
11. #define P(n) printf("%d\n",n)
12. using namespace std;
13. typedef long long ll;
14. const int INF=0x3f3f3f3f;
15. const int MAX=1e6+5;
16. int n,m;
17. struct node{
18. int u,v,w,next;
19. }edge[6*MAX];
20. int head[MAX];
21. int d[MAX];//给点标号
22. void add(int u,int v,int w) //链式前向星建图
23. {
24. static int cnt=0;
25. edge[cnt].v=v;
26. edge[cnt].w=w;
27. edge[cnt].next=head[u];
28. head[u]=cnt++;
29. }
30. int bfs(int s,int t)
31. {
32. mset(d,0);
33. d[s]=1;
34. int> q;
35. q.push(s);
36. while(!q.empty())
37. {
38. int u=q.front();
39. q.pop();
40. if(u==t) return 1; //到达汇点
41. for(int i=head[u];i!=-1;i=edge[i].next) //搜增广路
42. {
43. int v=edge[i].v; //下一可连通点
44. int w=edge[i].w; //当前流量
45. if(w&&d[v]==0) //temp1没走到
46. {
47. //点加1
48. if(v==t) //找到增广路
49. return 1;
50. //入队列
51. }
52. }
53. }
54. return 0;
55. }
56. int dfs(int s,int t,int maxflow=INF)
57. {
58. if(s==t)
59. return maxflow;
60. int i,j,ret=0;
61. for(i=head[s];i!=-1;i=edge[i].next)
62. {
63. int v=edge[i].v; //下一个可连通点
64. int w=edge[i].w; //当前点的流量
65. if(w&&d[v]==d[s]+1)
66. {
67. int temp=dfs(v,t,min(maxflow-ret,w)); //下一点，取最大流跟当前流量小的一个
68. //正向相减
69. //反向弧相加
70. //最大流
71. if(ret==maxflow) //下一点最大流等于这一点
72. return ret;
73. }
74. }
75. if(!ret)
76. d[s]=-1;
77. return ret;
78. }
79.
80. int dinic(int s,int t)
81. {
82. int ans=0;
83. while(bfs(s,t))
84. {
85. //dfs返回每次的数量
86. }
87. return ans;
88. }
89.
90. int main()
91. {
92. S2(n,m);
93. mset(head,-1);
94. int s,t,cap;
95. for(int i=0;i<n;i++)//横边
96. for(int j=1;j<m;j++)
97. {
98. s=i*m+j;t=s+1;
99. S1(cap);
100. add(s,t,cap);
101. add(t,s,cap);
102. }
103. for(int i=0;i<n-1;i++)//纵边
104. for(int j=1;j<=m;j++)
105. {
106. s=i*m+j;t=s+m;
107. S1(cap);
108. add(s,t,cap);
109. add(t,s,cap);
110. }
111. for(int i=0;i<n-1;i++)//斜边
112. for(int j=1;j<m;j++)
113. {
114. s=i*m+j;t=s+m+1;
115. S1(cap);
116. add(s,t,cap);
117. add(t,s,cap);
118. }
119. int ans=dinic(1,n*m);
120. P(ans);
121. return 0;
122. }
【代码2】（spfa）
1. #include <stdio.h>
2. #include <math.h>
3. #include <stdlib.h>
4. #include <string.h>
5. #include <time.h>
6. #include <iostream>
7. #include <algorithm>
8. #include <string>
9. #include <queue>
10. #include <stack>
11. #include <vector>
12. #include <set>
13. #include <list>
14. #include <map>
15. #define mset(a,i) memset(a,i,sizeof(a))
16. #define S1(n) scanf("%d",&n)
17. #define S2(n,m) scanf("%d%d",&n,&m)
18. #define P(n) printf("%d\n",n);
19. #define FIN freopen("input.txt","r",stdin)
20. #define FOUT freopen("output.txt","w",stdout)
21. #define gcd(a,b) __gcd(a,b)
22. using namespace std;
23. typedef long long ll;
24. const double eps=1e-6;
25. const int INF=0x3f3f3f3f;
26. const int mod=1e9+7;
27. const int MAX=1e6+5;
28. const double PI=acos(-1);
29. int dir[5][2]={0,1,0,-1,1,0,-1,0};
30. ll qpow(ll n,ll m){n%=mod;ll ans=1;while(m){if(m%2)
31. return ans;}
32. ll inv(ll b){return b==1?1:(mod-mod/b)*inv(mod%b)%mod;}
33. ll inv2(ll b){return qpow(b,mod-2);}
34. struct node{
35. int s,t,len,next;
36. }edge[6000010];
37. int head[2000100];
38. int n,m,len;
39. int dis[2000100];
40. int tail=1;
41. void add(int s,int t,int l)
42. {
43. edge[tail].s=s;
44. edge[tail].t=t;
45. edge[tail].len=l;
46. edge[tail].next=head[s];
47. head[s]=tail++;
48. }
49. int spfa(int s,int t)
50. {
51. mset(dis,INF);
52. dis[s]=0;
53. int> q; //装 起点
54. q.push(s);
55. while(!q.empty())
56. {
57. int u=q.front();
58. q.pop();
59. for(int i=head[u];i!=-1;i=edge[i].next)
60. {
61. int v=edge[i].t;
62. if(dis[v]>dis[u]+edge[i].len)
63. {
64. dis[v]=dis[u]+edge[i].len;
65. q.push(v);
66. }
67. }
68. }
69. return dis[t];
70. }
71. int main()
72. {
73. S2(n,m);
74. if(n==1&&m==1){
75. "0");
76. return 0;
77. }
78. mset(head,-1);
79. int end=2*(m-1)*(n-1)+1;
80. for(int i=1;i<m;i++){
81. S1(len);
82. add(0,i,len);
83. add(i,0,len);
84. //printf("%d -> %d\n",0,i);
85. }
86. for(int i=1;i<n-1;i++)
87. {
88. for(int j=1;j<m;j++){
89. S1(len);
90. int d=2*(m-1)*i+j;
91. int u=d-(m-1);
92. add(u,d,len);
93. add(d,u,len);
94. //printf("%d -> %d\n",u,d);
95. }
96. }
97. if(n>1)
98. for(int i=1;i<m;i++){
99. S1(len);
100. int u=end-(m-i);
101. add(u,end,len);
102. add(end,u,len);
103. //printf("%d -> %d\n",u,end);
104. }
105.
106. for(int i=0;i<n-1;i++)
107. {
108. S1(len);
109. int r=2*(m-1)*(i+1)-(m-2);
110. if(m==1)r=0;
111. add(r,end,len);
112. add(end,r,len);
113. //printf("%d -> %d\n",r,end);
114. for(int j=1;j<m-1;j++){
115. S1(len);
116. int l=2*(m-1)*i+j;
117. int r=l+m;
118. add(l,r,len);
119. add(r,l,len);
120. //printf("%d -> %d\n",l,r);
121. }
122. if(m<=1)continue;
123. S1(len);
124. int l=2*(m-1)*i+m-1;
125. add(0,l,len);
126. add(l,0,len);
127. //printf("%d -> %d\n",0,l);
128. }
129.
130. for(int i=0;i<n-1;i++)
131. {
132. for(int j=1;j<m;j++){
133. S1(len);
134. int u=2*(m-1)*i+j;
135. int d=u+m-1;
136. add(u,d,len);
137. add(d,u,len);
138. //printf("%d -> %d\n",u,d);
139. }
140. }
141. int ans=spfa(0,end);
142. P(ans);
143. return 0;
144. }