Uva 908 Re-connecting Computer Site

Uva 908 Re-connecting Computer Site
Question：

標準 MST 問題：使用 Kruskal's Algorithm

Code：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
typedef pair<int,int> ii;
#define MAXN 1000005
int g[MAXN];
void ini(int n)
{
    for(int i=1; i<=n; i++)
    {
        g[i]=i;
    }
}
int Find(int a)
{
    if(a!=g[a]) g[a]=Find(g[a]);
    return g[a];
}
void Union(int a,int b)
{
    if(Find(a)!=Find(b))
    {
        g[g[a]]=g[b];
    }
}
int Kruskal(priority_queue<pair<int,ii> > &ppq)
{
    int cost=0;
    while(!ppq.empty())
    {
        pair<int,ii> tmp=ppq.top();
        ppq.pop();
        if(Find(g[tmp.second.first])!=Find(g[tmp.second.second]))
        {
            cost+=(0-tmp.first);
            Union(tmp.second.first,tmp.second.second);
        }
    }
    return cost;
}
int main()
{
    int n=0,flag=0;
    while(cin>>n)
    {
        int k,m;
        int a,b,c,ans1=0,ans2=0;
        memset(g,-1,sizeof(g));
        ini(n);
        for(int i=0; i<n-1; i++)
        {
            cin>>a>>b>>c;
            ans1+=c;
        }
        priority_queue<pair<int,ii> > pq;
        cin>>k;
        for(int i=0; i<k; i++)
        {
            cin>>a>>b>>c;
            pq.push(make_pair(0-c,make_pair(a,b)));
        }
        cin>>m;
        for(int i=0; i<m; i++)
        {
            cin>>a>>b>>c;
            pq.push(make_pair(0-c,make_pair(a,b)));
        }
        if(flag==1) cout<<endl;
        flag=1;
        ans2=Kruskal(pq);
        cout<<ans1<<endl<<ans2<<endl;
    }
    return 0;

}

重點程式碼(Kruskal)：

typedef pair<int,int> ii;
#define MAXN 1000005
int g[MAXN];
void ini(int n) 
{
    for(int i=1; i<=n; i++)
    {
        g[i]=i;
    }
}
int Find(int a)
{
    if(a!=g[a]) g[a]=Find(g[a]);
    return g[a];
}
void Union(int a,int b)
{
    if(Find(a)!=Find(b))
    {
        g[g[a]]=g[b];
    }
}
int Kruskal(priority_queue<pair<int,ii> > &ppq)
{
   //主程式用pq存邊的權重<(negative) weight(i,j),<i,j> > 
   //存負權重用Priority_Queue才會由小排到大(記得加回來時多個負號)
    int cost=0;
    while(!ppq.empty())
    {
        pair<int,ii> tmp=ppq.top();
        ppq.pop();
        if(Find(g[tmp.second.first])!=Find(g[tmp.second.second]))
        {
            cost+=(0-tmp.first);
            Union(tmp.second.first,tmp.second.second);
        }
    }
    return cost;
}

留言

張貼留言

這個網誌中的熱門文章

Things a Little Bird Told Me: Confessions of the Creative Mind

圖片
瘋狂改變世界：我就是這樣創立Twitter的！心得分享 評價：★ ★ ★ ★ ★ 看完這本書評價絕對是5星啦!!! 都快變成Biz Stone的粉絲了~ 原本以為又是一本教人如何創業、如何成功的一本書。 但，裡面完全沒有! 這本書完完全全就是 Biz Stone的人生觀，敘述他的經歷以及他對世界的看法。 人生本來就是這樣嘛~應該超級精彩~ 一輩子一份工作，每天做同一件事情，多乏味~ 世界上有多少人只想找一份安安穩穩的生活，這樣並不是不好 這樣的生活的確適合某些人， 但，如果正值青春歲月，又不愁吃穿，又有顆聰明的腦袋， 為何不闖闖看這世界，反正是人總會跌倒，再爬起來就是了 現在是科技的時代，能教我們東西的不在只是學校老師，教我們更多的反而是Google大神。 我總覺得沒甚麼是做不到的!只要有心有熱情，還有冒險精神，加上一點堅持，這就是書中教會我的。 我是人，賴利·佩吉、謝爾蓋·布林、比爾蓋茲、賈伯斯、畢茲．史東 他們也是人，為何他們做得到我卻做不到!我欣賞他們，但更想成為像他們一樣能改變世界創造科技進步的人。 我想冒險挑戰!熱愛自己的工作!思考改變世界的創意! 我不想只是當一個如同有計算機腦袋的工程師，而是一個有人性，懂人心的工程師! 好希望未來能有機會和作者談話XDDD
閱讀完整內容

UVa 12970 Alcoholic Pilots

 1  #include <stdio.h>  2  #include <stdlib.h>  3  #include <iostream>  4  #include <algorithm>  5  using namespace std ;  6  long long int gcd ( long long int a , long long int b )  7  {  8      return b ? gcd ( b , a % b ): a ;  9  } 10  int main () 11  { 12      long long int v1 , d1 , v2 , d2 , cas = 1 ; 13      while ( cin >> v1 >> d1 >> v2 >> d2 && ( v1 != 0 || v2 != 0 || d1 != 0 || d2 != 0 )) 14      { 15          long long int a = d1 * v2 , b = d2 * v1 ; 16          if ( a < b ) printf ( "Case #%lld: You owe me a beer!\n" , cas ++); 17          else if ( a > b )...
閱讀完整內容

UVa 483 Word Scramble

 1  #include <stdio.h>  2  #include <string>  3  #include <iostream>  4  #include <algorithm>  5  #include <sstream>  6  using namespace std ;  7  int main ()  8  {  9      string line ; 10      while ( getline ( cin , line )) 11      { 12          string str [ 1000 ]; 13          stringstream ss ( line ); 14          int x = 0 ; 15          while ( ss >> str [ x ]) x ++; 16          for ( int i = 0 ; i < x ; i ++) 17          { 18          ...
閱讀完整內容