? ? 時(shí)間來不及了，先貼代碼吧！有時(shí)間再寫。

? ?好苦逼啊，WA了若干次，還有一次RE，一次TLE。

? ?雖然主要運(yùn)用的算法和資料都由師兄提供了。還是太弱了，太天真了。

? ?首先，數(shù)據(jù)范圍就WA了，RE了，TLE了。

? ?然后構(gòu)圖上有bug。最后還是仿著師兄的把構(gòu)圖重新寫了。加油吧！

? 這道題的主要思路首先應(yīng)該是網(wǎng)絡(luò)流中的最小割，但由于數(shù)據(jù)范圍太大，直接用最小割的算法會(huì)TLE，而且沒有正確地利用題目特征，這道題的圖是個(gè)S-T圖，我們可以建出原圖的對(duì)偶圖，然后跑一次dijkstra（）。詳情請(qǐng)參考《淺析最大最小定理在信息學(xué)競(jìng)賽中的應(yīng)用》。

? ?一個(gè)網(wǎng)格圖中求最小割，很特殊的是這個(gè)圖是一個(gè)平面圖，最小割=最大流=對(duì)偶圖中最短路（平面圖）。

1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #include<cstring> 5 #define maxn 2100009 6 #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_queue<node> 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(xx+2*j,tx,x); 81 //cout<<tx<<" "<<xx+2*j+1<<" "<<x<<endl; 82 } 83 else if( i == n-1 ) { 84 add_edge(sx,xy+2*j-1,x); 85 //cout<<xy+2*j<<" "<<sx<<" "<<x<<endl; 86 } 87 else{ 88 add_edge(xx+2*j,xy+2*j-1,x); 89 //cout<<xy+2*j<<" "<<xx+2*j+1<<" "<<x<<endl; 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,xx+2*j-1,x); 99 //cout<<sx<<" "<<xx<<" "<<x<<endl; 100 } 101 else if( j == m ){ 102 add_edge(tx,xx+2*j-2,x); 103 //cout<<tx<<" "<<xx+2*j-1<<" "<<x<<endl; 104 } 105 else { 106 add_edge(xx+2*j-2,xx+2*j-1,x); 107 //cout<<xx+2*j<<" "<<xx+2*j-1<<" "<<x<<endl; 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(xx+2*j,xx+2*j-1,x); 116 //cout<<xx+2*j<<" "<<xx+2*j+1<<" "<<endl; 117 } 118 } 119 dijkstra(); 120 cout<<d[tx]<<endl; 121 return 0; 122 }

? ? 不過，也想請(qǐng)大神把我指出下面這份代碼錯(cuò)哪了？

1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #include<cstring> 5 #define maxn 2100009 6 #define sx 2100000 7 #define tx 2100001 8 #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_queue<node> 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(xx+2*j+1,tx,x); 82 //cout<<tx<<" "<<xx+2*j+1<<" "<<x<<endl; 83 } 84 else if( i == n-1 ) { 85 add_edge(sx,xy+2*j,x); 86 //cout<<xy+2*j<<" "<<sx<<" "<<x<<endl; 87 } 88 else{ 89 add_edge(xx+2*j+1,xy+2*j,x); 90 //cout<<xy+2*j<<" "<<xx+2*j+1<<" "<<x<<endl; 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 //cout<<sx<<" "<<xx<<" "<<x<<endl; 101 } 102 else if( j == m-1 ){ 103 add_edge(tx,xx+2*j-1,x); 104 //cout<<tx<<" "<<xx+2*j-1<<" "<<x<<endl; 105 } 106 else { 107 add_edge(xx+2*j,xx+2*j-1,x); 108 //cout<<xx+2*j<<" "<<xx+2*j-1<<" "<<x<<endl; 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(xx+2*j,xx+2*j+1,x); 117 //cout<<xx+2*j<<" "<<xx+2*j+1<<" "<<endl; 118 } 119 } 120 dijkstra(); 121 cout<<d[tx]<<endl; 122 return 0; 123 }

?

1001: [BeiJing2006]狼抓兔子

Time Limit:?15 Sec??Memory Limit:?162 MB
Submit:?14595??Solved:?3490
[Submit][Status][Discuss]

Description

現(xiàn)在小朋友們最喜歡的"喜羊羊與灰太狼",話說灰太狼抓羊不到，但抓兔子還是比較在行的，而且現(xiàn)在的兔子還比較笨，它們只有兩個(gè)窩，現(xiàn)在你做為狼王，面對(duì)下面這樣一個(gè)網(wǎng)格的地形：

?

左上角點(diǎn)為(1,1),右下角點(diǎn)為(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) 道路上的權(quán)值表示這條路上最多能夠通過的兔子數(shù)，道路是無向的. 左上角和右下角為兔子的兩個(gè)窩，開始時(shí)所有的兔子都聚集在左上角(1,1)的窩里，現(xiàn)在它們要跑到右下解(N,M)的窩中去，狼王開始伏擊這些兔子.當(dāng)然為了保險(xiǎn)起見，如果一條道路上最多通過的兔子數(shù)為K，狼王需要安排同樣數(shù)量的K只狼，才能完全封鎖這條道路，你需要幫助狼王安排一個(gè)伏擊方案，使得在將兔子一網(wǎng)打盡的前提下，參與的狼的數(shù)量要最小。因?yàn)槔沁€要去找喜羊羊麻煩.

Input

第一行為N,M.表示網(wǎng)格的大小，N,M均小于等于1000.接下來分三部分第一部分共N行，每行M-1個(gè)數(shù)，表示橫向道路的權(quán)值. 第二部分共N-1行，每行M個(gè)數(shù)，表示縱向道路的權(quán)值. 第三部分共N-1行，每行M-1個(gè)數(shù)，表示斜向道路的權(quán)值. 輸入文件保證不超過10M

Output

輸出一個(gè)整數(shù)，表示參與伏擊的狼的最小數(shù)量.

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

轉(zhuǎn)載于:https://www.cnblogs.com/83131yyl/p/5046130.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1001 狼抓兔子 终于过了！的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。