修路

時(shí)限：?2000MS	?	內(nèi)存限制：?65536K
提交總數(shù)：?31810	?	接受：?14215

描述

有N個(gè)村莊，編號(hào)從1到N，您應(yīng)該修建一些道路，使每?jī)蓚€(gè)村莊可以相互連接。我們說(shuō)兩個(gè)村莊A和B是連通的，當(dāng)且僅當(dāng)A和B之間有一條道路，或者存在一個(gè)村莊C使得A和C之間有一條道路，并且C和B連通時(shí)。

我們知道，一些村莊之間已經(jīng)存在一些道路，您的工作是建造一些道路，以使所有村莊都連接起來(lái)，并且所有道路的長(zhǎng)度都應(yīng)最小。

輸入

第一行是整數(shù)N（3 <= N <= 100），它是村莊的數(shù)量。然后是N行，其中第i個(gè)包含N個(gè)整數(shù)，而這N個(gè)整數(shù)中的第j個(gè)是村莊i與村莊j之間的距離（該距離應(yīng)為[1，1000]之內(nèi)的整數(shù)）。

然后有一個(gè)整數(shù)Q（0 <= Q <= N *（N +1）/ 2）。然后出現(xiàn)Q條線，每條線包含兩個(gè)整數(shù)a和b（1 <= a <b <= N），這意味著已經(jīng)建立了村莊a和村莊b之間的道路。

產(chǎn)量

您應(yīng)該輸出包含整數(shù)的線，該整數(shù)是要連接所有村莊的所有道路的長(zhǎng)度，并且該值是最小值。

樣本輸入

3 0 990 692 990 0 179 692 179 0 1 1 2

樣本輸出

179

資源

北京大學(xué)月刊，KICC

就是給了N個(gè)村莊，然后給你權(quán)值什么的 ，后面又給了一個(gè)數(shù)M，告訴你哪些路已經(jīng)修好了，你就不用修了，最后問(wèn)最小生成樹，問(wèn)需要修的最短的路。

思路：把已經(jīng)修建好的路的權(quán)值設(shè)置為0，這樣求和就不用重復(fù)計(jì)算，而且能保證這些之前的路優(yōu)先選擇！

#include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> //---------------------------------Sexy operation--------------------------//#define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define debug(n) printf("%d_________________________________\n",n); #define speed ios_base::sync_with_stdio(0) #define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout) //-------------------------------Actual option------------------------------// #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Swap(a,b) a^=b^=a^=b #define Max(a,b) (a>b?a:b) #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define mp(a,b) make_pair(a,b) #define pb(n) push_back(n) #define dis(a,b,c,d) ((double)sqrt((a-c)*(a-c)+(b-d)*(b-d))) //--------------------------------constant----------------------------------//#define INF 0x3f3f3f3f #define esp 1e-9 #define PI acos(-1) using namespace std; #define maxn 1020 #define INF 0x3f3f3f3fusing namespace std;int dis[maxn][maxn]; int d[maxn]; bool vis[maxn]; int n,q; void prim() {for(int i = 1; i <= n; i ++){d[i] = dis[1][i];vis[i] = 0;}for(int i = 1; i <= n; i ++){int minx = INF;int now;for(int j = 1; j <= n; j ++){if(!vis[j] && minx > d[j]){now = j;minx = d[j];}}vis[now] = 1;for(int k = 1; k <= n; k ++){if(!vis[k] && d[k] > dis[now][k])d[k] = dis[now][k];}}int sum = 0;for(int i = 1; i <= n; i ++)sum += d[i];printf("%d\n",sum); } int main() {scanf("%d",&n);for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++){scanf("%d",&dis[i][j]);}scanf("%d",&q);int x,y;while(q --){scanf("%d%d",&x,&y);dis[x][y] = dis[y][x] = 0;}prim();return 0; }

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的POJ2421 Constructing Roads 最小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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