电子商务网站设计模板,网站开发开发需求文档,网站建设哪个公司好,房屋网站Description 现在小朋友们最喜欢的喜羊羊与灰太狼,话说灰太狼抓羊不到#xff0c;但抓兔子还是比较在行的#xff0c;而且现在的兔子还比较笨#xff0c;它们只有两个窝#xff0c;现在你做为狼王#xff0c;面对下面这样一个网格的地形#xff1a; 左上角点… Description 现在小朋友们最喜欢的喜羊羊与灰太狼,话说灰太狼抓羊不到但抓兔子还是比较在行的而且现在的兔子还比较笨它们只有两个窝现在你做为狼王面对下面这样一个网格的地形 左上角点为(1,1),右下角点为(N,M)(上图中N4,M5).有以下三种类型的道路 1:(x,y)(x1,y) 2:(x,y)(x,y1) 3:(x,y)(x1,y1) 道路上的权值表示这条路上最多能够通过的兔子数道路是无向的. 左上角和右下角为兔子的两个窝开始时所有的兔子都聚集在左上角(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 Source 这个刚看一眼以为是道网络流裸题(ISAP 跑无向图最小割)但看数据范围马上枪毙。 后来r_64大神犇教了一个平面图转对偶图求最小割的方法时间复杂度是跑最短路的。 具体做法如下 先将源点与汇点连接一条边此边不与其他任何边相交再将所有的平面surface看做一个点平面与平面的边界看做一条边边权即为边界的边权(之前连的除外边权inf)。仔细想想原图的最小割即为两个外围的大平面的最短路。 代码如下 1 #includecstring2 #includequeue3 #includecstdio4 #includecstdlib5 using namespace std;6 7 #define maxn 10108 #define source 09 #define sink (2*(n-1)*(m-1)1)
10 const int inf 130;
11 int side[maxn*maxn*2],toit[maxn*maxn*6],n,m,dis[maxn*maxn*2];
12 int cnt 1,next[maxn*maxn*6],len[maxn*maxn*6];
13 bool in[maxn*maxn*2];
14
15 inline void add(int a,int b,int c)
16 {
17 toit[cnt] b;
18 next[cnt] side[a];
19 side[a] cnt;
20 len[cnt] c;
21 }
22
23 inline void ins(int a,int b,int c)
24 {
25 add(a,b,c); add(b,a,c);
26 }
27
28 inline void build()
29 {
30 int a,i,j;
31 for (i 1;i n;i)
32 {
33 for (j 1;j m;j)
34 {
35 scanf(%d,a);
36 int up,down;
37 if (i 1) up sink;
38 else up (i-2)*(m-1)j;
39 if (i n) down source;
40 else down (n-1)*(m-1)(i-1)*(m-1)j;
41 ins(up,down,a);
42 }
43 }
44 for (i 1;i n;i)
45 for (j 1;j m;j)
46 {
47 scanf(%d ,a);
48 int le,ri;
49 if (j 1) le source;
50 else le (n-1)*(m-1)(i-1)*(m-1)j-1;
51 if (j m) ri sink;
52 else ri (i-1)*(m-1)j;
53 ins(le,ri,a);
54 }
55 for (i 1;i n;i)
56 for (j 1;j m;j)
57 {
58 scanf(%d ,a);
59 int le,ri;
60 le (i-1)*(m-1)j;
61 ri (i-1)*(m-1)(n-1)*(m-1)j;
62 ins(le,ri,a);
63 }
64 }
65
66 inline int spfa()
67 {
68 queue int team;
69 in[source] true; memset(dis,0x7,sizeof(dis));
70 dis[source] 0; team.push(source);
71 int now,i;
72 while (!team.empty())
73 {
74 now team.front(); team.pop();
75 for (i side[now];i;i next[i])
76 if (dis[toit[i]] dis[now] len[i])
77 {
78 dis[toit[i]] dis[now] len[i];
79 if (!in[toit[i]])
80 in[toit[i]] true,team.push(toit[i]);
81 }
82 in[now] false;
83 }
84 return dis[sink];
85 }
86
87 int main()
88 {
89 freopen(1001.in,r,stdin);
90 freopen(1001.out,w,stdout);
91 scanf(%d %d,n,m);
92 build();
93 printf(%d\n,spfa());
94 fclose(stdin); fclose(stdout);
95 return 0;
96 } 转载于:https://www.cnblogs.com/mmlz/p/4191431.html
