?
?
題意：
給出圖的邊和點數，要求最小生成樹的代價，注：有些點之間是不可達的，也就是可能有多個連通圖。比如4個點，2條邊:1-2，3-4。
?
思路：
如果不能連通所有的點，就輸出‘?’。之前以為每個點只要有邊連著就一定能生成樹，其實還可以是每個點雖然有邊可達，但是給的其實是兩個圖，比如上例。其他按照常規Prim。
?
?
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=105; 4 const int mod=0x7f7f7f7f; 5 int v[N][N]; //權 6 int vis[N]; 7 int low[N]; //到每個點的最小權 8 9 10 int prim(int n) 11 { 12 int pos=vis[1]=1; //從點1開始 13 for(int i=2; i<=n; i++) low[i]=v[1][i]; //目前到每個點的最小權 14 int ans=0; 15 for(int i=1; i<n; i++) //搞定另外n-1個點 16 { 17 int big=mod; 18 for(int j=2; j<=n; j++) //找權最小的邊 19 { 20 if(!vis[j] && low[j]<big ) //未瀏覽過，目前可達，權小 21 { 22 pos=j; 23 big=low[j]; 24 } 25 } 26 if(big==mod) return 0; //無法到達。 27 ans+=big; 28 vis[pos]++; //瀏覽過 29 for( int j=2; j<=n; j++ ) //更新到每個點的權值 30 if(!vis[j] && v[pos][j]<mod && low[j]>v[pos][j] ) low[j]=v[pos][j]; //未瀏覽過，有路可達,更短 31 } 32 return ans; 33 } 34 35 36 37 38 int main() 39 { 40 freopen("input.txt", "r", stdin); 41 int n, m, a, b, t; 42 while(scanf("%d%d", &n, &m), n) 43 { 44 45 memset(cnt,0,sizeof(cnt)); 46 memset(vis,0,sizeof(vis)); 47 memset(v,0x7f,sizeof(v)); //置為不可達 48 49 for(int i=0; i<n; i++) 50 { 51 scanf("%d%d%d",&a,&b,&t); 52 v[a][b]=v[b][a]=t; 53 } 54 int ans=prim(m); 55 if(ans) printf("%d\n",ans); 56 else printf("?\n"); 57 } 58 return 0; 59 }
?
)
