网站如何排名,做新媒体应该关注什么网站,手机个人简历模板下载,织梦音乐网站程序时间来不及了#xff0c;先贴代码吧#xff01;有时间再写。 好苦逼啊#xff0c;WA了若干次#xff0c;还有一次RE#xff0c;一次TLE。 虽然主要运用的算法和资料都由师兄提供了。还是太弱了#xff0c;太天真了。 首先#xff0c;数据范围就WA了#xff0c;RE了先贴代码吧有时间再写。 好苦逼啊WA了若干次还有一次RE一次TLE。 虽然主要运用的算法和资料都由师兄提供了。还是太弱了太天真了。 首先数据范围就WA了RE了TLE了。 然后构图上有bug。最后还是仿着师兄的把构图重新写了。加油吧 这道题的主要思路首先应该是网络流中的最小割但由于数据范围太大直接用最小割的算法会TLE而且没有正确地利用题目特征这道题的图是个S-T图我们可以建出原图的对偶图然后跑一次dijkstra。详情请参考《浅析最大最小定理在信息学竞赛中的应用》。 一个网格图中求最小割很特殊的是这个图是一个平面图最小割最大流对偶图中最短路平面图。 1 #includecstdio2 #includeiostream3 #includequeue4 #includecstring5 #define maxn 21000096 #define rep(i,j,k) for(int i j; i k; i)7 using namespace std;8 9 int read()10 {11 int s 0, t 1; char c getchar();12 while( !isdigit(c) ) {13 if( c - ) t -1; c getchar();14 }15 while( isdigit(c) ){16 s s * 10 c - 0; c getchar();17 } 18 return s * t;19 }20 21 int d[maxn], n, m, sx, tx;22 bool done[maxn] {0}; 23 24 struct node{25 int d, u;26 bool operator (const node rhs) const{27 return d rhs.d;28 }29 };30 31 struct edge{32 int to, key;33 edge* next;34 };35 36 edge *pt, edges[maxn*3], *head[maxn];37 38 void add_edge(int x,int y,int val){39 pt-to y;pt-key val;40 pt-next head[x];41 head[x] pt;42 pt-to x, pt-key val;43 pt-next head[y];44 head[y] pt; 45 }46 priority_queuenode Q;47 48 void dijkstra()49 {50 memset(d,127,sizeof(d));51 d[sx] 0;52 Q.push((node){0,sx});53 while( !Q.empty() ){54 node x Q.top(); Q.pop();55 int u x.u;56 if( done[u] ) continue;57 done[u] 1;58 for( edge*i head[u]; i ; i i-next ){59 int y i-to, key i-key;60 if( d[y] d[u]key ) {61 d[y] d[u]key;62 Q.push((node){d[y],y});63 }64 }65 }66 }67 68 int main()69 {70 //freopen(out.txt,w,stdout);71 pt edges;72 n read(), m read(); 73 sx 0, tx (n-1)*(m-1) * 2 1;74 rep(i,0,n-1) {75 int xx (2*m-2)*i;76 int xy (2*m-2)*(i-1);77 rep(j,1,m-1){78 int x read();79 if( !i ) {80 add_edge(xx2*j,tx,x);81 //couttx xx2*j1 xendl;82 } 83 else if( i n-1 ) {84 add_edge(sx,xy2*j-1,x);85 //coutxy2*j sx xendl;86 }87 else{88 add_edge(xx2*j,xy2*j-1,x);89 //coutxy2*j xx2*j1 xendl;90 }91 }92 }93 rep(i,0,n-2){94 int xx 2*(m-1)*(i);95 rep(j,1,m){96 int x read();97 if( j 1 ){98 add_edge(sx,xx2*j-1,x);99 //coutsx xx xendl;
100 }
101 else if( j m ){
102 add_edge(tx,xx2*j-2,x);
103 //couttx xx2*j-1 xendl;
104 }
105 else {
106 add_edge(xx2*j-2,xx2*j-1,x);
107 //coutxx2*j xx2*j-1 xendl;
108 }
109 }
110 }
111 rep(i,0,n-2){
112 int xx 2*(m-1)*(i);
113 rep(j,1,m-1){
114 int x read();
115 add_edge(xx2*j,xx2*j-1,x);
116 //coutxx2*j xx2*j1 endl;
117 }
118 }
119 dijkstra();
120 coutd[tx]endl;
121 return 0;
122 } 不过也想请大神把我指出下面这份代码错哪了 1 #includecstdio2 #includeiostream3 #includequeue4 #includecstring5 #define maxn 21000096 #define sx 21000007 #define tx 21000018 #define rep(i,j,k) for(int i j; i k; i)9 using namespace std;10 11 int read()12 {13 int s 0, t 1; char c getchar();14 while( !isdigit(c) ) {15 if( c - ) t -1; c getchar();16 }17 while( isdigit(c) ){18 s s * 10 c - 0; c getchar();19 } 20 return s * t;21 }22 23 int d[maxn], n, m;24 bool done[maxn] {0}; 25 26 struct node{27 int d, u;28 bool operator (const node rhs) const{29 return d rhs.d;30 }31 };32 33 struct edge{34 int to, key;35 edge* next;36 };37 38 edge *pt, edges[maxn*3], *head[maxn];39 40 void add_edge(int x,int y,int val){41 pt-to y;pt-key val;42 pt-next head[x];43 head[x] pt;44 pt-to x, pt-key val;45 pt-next head[y];46 head[y] pt; 47 }48 priority_queuenode Q;49 50 void dijkstra()51 {52 memset(d,127,sizeof(d));53 d[sx] 0;54 Q.push((node){0,sx});55 while( !Q.empty() ){56 node x Q.top(); Q.pop();57 int u x.u;58 if( done[u] ) continue;59 done[u] 1;60 for( edge*i head[u]; i ; i i-next ){61 int y i-to, key i-key;62 if( d[y] d[u]key ) {63 d[y] d[u]key;64 Q.push((node){d[y],y});65 }66 }67 }68 }69 70 int main()71 {72 //freopen(out.txt,w,stdout);73 pt edges;74 n read(), m read(); 75 rep(i,0,n-1) {76 int xx (2*m-2)*i;77 int xy (2*m-2)*(i-1);78 rep(j,0,m-2){79 int x read();80 if( !i ) {81 add_edge(xx2*j1,tx,x);82 //couttx xx2*j1 xendl;83 } 84 else if( i n-1 ) {85 add_edge(sx,xy2*j,x);86 //coutxy2*j sx xendl;87 }88 else{89 add_edge(xx2*j1,xy2*j,x);90 //coutxy2*j xx2*j1 xendl;91 }92 }93 }94 rep(i,0,n-2){95 int xx 2*(m-1)*(i);96 rep(j,0,m-1){97 int x read();98 if( !j ){99 add_edge(sx,xx,x);
100 //coutsx xx xendl;
101 }
102 else if( j m-1 ){
103 add_edge(tx,xx2*j-1,x);
104 //couttx xx2*j-1 xendl;
105 }
106 else {
107 add_edge(xx2*j,xx2*j-1,x);
108 //coutxx2*j xx2*j-1 xendl;
109 }
110 }
111 }
112 rep(i,0,n-2){
113 int xx 2*(m-1)*(i);
114 rep(j,0,m-2){
115 int x read();
116 add_edge(xx2*j,xx2*j1,x);
117 //coutxx2*j xx2*j1 endl;
118 }
119 }
120 dijkstra();
121 coutd[tx]endl;
122 return 0;
123 } 1001: [BeiJing2006]狼抓兔子 Time Limit: 15 Sec Memory Limit: 162 MBSubmit: 14595 Solved: 3490[Submit][Status][Discuss] 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转载于:https://www.cnblogs.com/83131yyl/p/5046130.html
