本章施工仍未完成

現在的時間是3.17 0:28，我困得要死

本來今天（昨天?）晚上的計劃是把整個四道題的題解寫出來，但是到現在還沒寫完T4的高效算法，簡直悲傷。

?

嘗試了用floyd寫T4，終于大功告成AC后，看到別人的解題報告說fl能過只是因為測試數據范圍小。

好像主要有三種解法，fl，dij，dfs

dfs暫時棄，dij寫到現在還沒完成，先把fl的放上來。

等攻下T4，再施工前面三道題

?

T4-Floyd:

讀完數據以后，只要把文化不兼容的城市的路都堵上，就可以用floyd了

可憐我之前堵路無方，寫了一大堆判定條件還沒見效……

AC代碼如下

?

1 /*NOIP普及組2012 t4 culture*/ 2 //根據多個解題報告所說，floyd算法能過只是因為數據范圍小 3 //我們需要dij或者dfs 4 #include<iostream> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 const int inf=10000000; 9 int c[5000];//文明[i]的文化 10 int fl[300][300];//文化拒絕 11 int mp[300][300];//圖 12 //int DFS(){ 13 14 //} 15 int main(){ 16 int i,j,n,k,m,s,t; 17 // freopen("culture.in","r",stdin); 18 // freopen("culture.out","w",stdout); 19 //in 20 scanf("%d%d%d%d%d",&n,&k,&m,&s,&t); 21 for(i=1;i<=n;i++){ 22 scanf("%d",&c[i]); 23 } 24 for(i=1;i<=n;i++) 25 for(j=1;j<=n;j++){ 26 if(i!=j)mp[i][j]=inf;//預處理 27 } 28 for(i=1;i<=k;i++) 29 for(j=1;j<=k;j++) 30 scanf("%d",&fl[i][j]);//讀入文化兼容情況 31 32 for(i=1;i<=m;i++){ 33 int u,v,d; 34 scanf("%d%d%d",&u,&v,&d); 35 mp[u][v]=min(mp[u][v],d);//兩座城市間若有多條道路，記錄最短的即可 36 mp[v][u]=mp[u][v];//雙向圖 37 } 38 for(i=1;i<=n;i++) 39 for(j=1;j<=n;j++){ 40 if(fl[c[i]][c[j]]==1)mp[j][i]=inf;//如果文化不兼容，相當于道路不通 41 //剛開始mp[j][i]誤打成mp[i][j]，費了半天時間查錯 42 //這部分原本想邊讀邊處理，但是發現會影響到雙向距離處理，只好單拿出來了 43 } 44 // 45 //floyd 不能走的路之前都處理成inf了，直接floyd就行 46 for(k=1;k<=n;k++) 47 for(i=1;i<=n;i++) 48 for(j=1;j<=n;j++){ 49 if(mp[i][k]+mp[k][j]<mp[i][j]){ 50 mp[i][j]=mp[i][k]+mp[k][j]; 51 } 52 } 53 // 54 if(mp[s][t]==inf)printf("-1"); 55 else printf("%d",mp[s][t]); 56 // fclose(stdin); 57 // fclose(stdout); 58 return 0; 59 60 }

?

轉載于:https://www.cnblogs.com/AwesomeOrion/p/5285834.html

總結

以上是生活随笔為你收集整理的NOIP2012普及组 (四年后的)解题报告 -SilverN的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。