最近做了兩道floyd變種的題目,又加深了對floyd原理的理解.

第1題: bupt 1460 游覽路線
這樣可以得出算法的大致輪廓:在加入點(diǎn)k前更新dist[i,j]
但是問題是,此時的中間點(diǎn)只有1..k-1,那后面的點(diǎn)k+1..n會不會漏處理呢?
本質(zhì)上,這題求的是環(huán)的長度,而不是路徑長度.因此,假如存在一個更短的環(huán),它路徑上有k之后的點(diǎn)p1,p2,...,pm,設(shè)其中最后處理的那個點(diǎn)是pl.那么這個環(huán)一定會在向中間點(diǎn)集中加入pl的那次循環(huán)里枚舉到.
因此不存在漏解問題.

代碼如下:

1 #include <iostream>
2 using namespace std;
3 int N,M,ans;
4 //w是原圖矩陣,d是floyd最短路矩陣
5 int w[110][110],d[110][110];
6 int main(){
7     int i,j,k,a,b,c;
8     while(scanf("%d%d",&N,&M)!=EOF){
9         for(i=1;i<=N;i++)
10             for(j=1;j<=N;j++)
11                 w[i][j]=d[i][j]=0;
12         for(i=1;i<=M;i++){
13             scanf("%d%d%d",&a,&b,&c);
14             if(!w[a][b]||c<w[a][b]){
15                 w[a][b]=w[b][a]=c;
16                 d[a][b]=d[b][a]=c;
17             }
18         }
19         ans=0x7fffffff;
20         for(k=1;k<=N;k++){
21             //先枚舉map[i,k]+map[k,j]+floyd[i,j]
22             for(i=1;i<k;i++)
23                 for(j=i+1;j<k;j++)
24                     if(w[i][k]&&w[k][j]&&d[i][j])
25                         ans=min(ans,d[i][j]+w[i][k]+w[k][j]);
26             //再向中間點(diǎn)集中加入k并更新floyd矩陣
27             for(i=1;i<=N;i++){
28                 if(!d[i][k])continue;
29                 for(j=1;j<=N;j++){
30                     if(!d[k][j]||i==j)continue;
31                     if(!d[i][j]||d[i][j]>d[i][k]+d[k][j])
32                         d[i][j]=d[i][k]+d[k][j];
33                 }
34             }
35         }
36         if(ans<0x7fffffff)
37             printf("%d\n",ans);
38         else
39             puts("No solution.");
40     }
41     return 0;
42 }

posted on 2009-03-31 14:20 wolf5x 閱讀(178) 評論(0) 編輯收藏引用所屬分類: acm_icpc 、algorithm

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: pku 3697 USTC campus network O(M) 有向有環(huán)圖的最小路徑覆蓋 hdu 3311 steiner tree / 狀態(tài)壓縮spfa Two Professors (CERC 2008) 解題報(bào)告 Guarders: Maximal Cliques on Circular-arc Graph pku 2114 Boatherds (樹的分治) pku 3450 Corporate Identity (后綴數(shù)組,KMP擴(kuò)展,自動機(jī)) 幾道線性的題目 uva4031 Integer Transmission (DP) 字符串匹配后綴數(shù)組 trie圖(更新)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2009年9月

日

一

二

三

四

五

六

"Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don't let them become your life - for your life is much more interesting and colorful." -- Petr

留言簿(3)

隨筆分類(59)

隨筆檔案(43)

cows

Felicia
hhanger
javaman
Matrix67
Roba
watashi

留言簿(3)

隨筆分類(59)

隨筆檔案(43)

cows

搜索

最新評論

評論排行榜