引水工程（第八届）
引水工程
時間限制：2000?ms ?|? 內存限制：65535?KB 難度：3 描述南水北調工程是優化水資源配置、促進區域協調發展的基礎性工程，是新中國成立以來投資額最大、涉及面最廣的戰略性工程，事關中華民族長遠發展。“南水北調工程”，旨在緩解中國華北和西北地區水資源短缺的國家戰略性工程。就是把中國長江流域豐盈的水資源抽調一部分送到華北和西北地區。我國南澇北旱，南水北調工程通過跨流域的水資源合理配置，促進南北方經濟、社會與人口、資源、環境的協調發展。
整個工程分東線、中線、西線三條調水線。東線工程位于東部，因地勢低需抽水北送至華北地區。中線工程從漢水與其最大支流丹江交匯處的丹江口水庫引水，自流供水給黃淮海平原大部分地區，20多座大中城市；西線工程在青藏高原上，由長江上游向黃河上游補水。
現在有N個區域需要建設水資源工程，它們可以自建水庫解決缺水問題，也可以從已有水源的地區建立管道引水過來。當然，這些建設都需要大量投資。
你能不能給出一個優化水資源配置方案，在保證每個區域都能用上水的前提下，使得整個引水工程費用最低。
輸入接下來對每組測試數據：
第1行: N 表示有N個區域（ 1<=N<=300 ）
第2 行： W1 W2 …. WN Wi表示第i個區域自建水庫需要的費用
再有N行： Pi1 Pi2 …. Pin Pij表示建立第i個區域與第j個區域引水管道的費用
AC代碼：
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #define INF 0x3f3f3f3f //只能為0x3f3f3f3f,不能為0xffffff using namespace std; int pos,i,j,ans; int K,N; int map[310][310],low[310],vis[310]; int prim(){ans=0;while(true){pos=0;for(i=1;i<=N;i++){if(!vis[i]&&low[i]<low[pos])pos=i;}if(pos==0)break;vis[pos]=1;ans+=low[pos];for(i=1;i<=N;i++)low[i]=min(low[i],map[pos][i]);}return ans; } int main() {while(cin>>K)while(K--){cin>>N;memset(map,INF,sizeof(map));memset(vis,0,sizeof(vis));memset(low,INF,sizeof(low));for(i=1;i<=N;i++)cin>>low[i];for(i=1;i<=N;i++)for(j=1;j<=N;j++)cin>>map[i][j];prim();cout<<ans<<endl;}return 0; }總結
- 上一篇： Interference Signal
- 下一篇： mysql添加新用户 开放外网访问