2016年10月20日 星期四

TIOJ 1211 - 圖論 之 最小生成樹

http://tioj.infor.org/problems/1211

校隊培訓裡面的某題
因為一開始做kruskal
然後大家都在寫prim覺得也來寫寫看 
然後覺得好慢又用priority_queue優化

 所以這次code有三種寫法喔OwO

 跑這題的時間大概分別是 640ms, 7000ms, 500ms

 kruskal : 

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
using namespace std;

struct edge{
    int l,r,c;
    friend bool operator > (const edge &l,const edge &r){
        return l.c>r.c;
    }
};

int m,n,i,j,c,lo,s[10005],ans,sz[10005],apped[10005],appcnt;
priority_queue<edge,vector<edge>,greater<edge> > pq;
void C();
void Init();

int F(int a){
    if(a==s[a])return a;
    return s[a] = F(s[a]);
}
inline bool U(int a,int b){
    a=F(a),b=F(b);
    if(a==b)return 0;
    if(sz[b]<sz[a])swap(a,b);
    s[a]=b;
    sz[b]+=sz[a];
    return 1;
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>n>>m && m && n){
        C();

        for(lo=0;lo<m;lo++){
            cin>>i>>j>>c;
            pq.push({i,j,c});
        }

        Init();

        while(pq.size()){
            edge e=pq.top();
            pq.pop();
            if(U(e.l,e.r)){
                ans+=e.c;
            }
        }
        if(sz[F(1)]!=n){
            cout<<"-1\n";
        }
        else{
            cout<<ans<<endl;
        }
    }
}

inline void C(){
    memset(s,0,sizeof(s));
    memset(sz,0,sizeof(sz));
    ans=0;
    while(pq.size())pq.pop();
}
inline void Init(){
    for(lo=0;lo<=n;lo++){
        s[lo]=lo;
        sz[lo]=1;
    }
}

prim : 

 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define pii pair<int,int>
#define X first
#define Y second
using namespace std;
int n,m;
vector<pii> G[10003];
bitset<10003> ined;
int dist[10003];
int ans;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m && n){
        for(int i=0;i<10003;i++)G[i].clear();
        ined.reset();
        memset(dist,0,sizeof(dist));
        ans=0;
        for(int i=0;i<m;i++){
            int z,x,c;
            cin>>z>>x>>c;
            G[z].push_back({x,c});
            G[x].push_back({z,c});
        }
        memset(dist,0x7f,sizeof(dist));
        dist[1]=0;
        for(int ppp=0;ppp<n;ppp++){
            int nowc=-1,noww=0x7f7f7f7f;
            for(int i=1;i<=n;i++){
                if(!ined[i] && dist[i]<noww){
                    nowc=i;
                    noww=dist[i];
                }
            }
            if(nowc==-1){
                break;
            }
            // cout<<"join:nowc:"<<nowc<<endl;
            ined[nowc]=1;
            ans+=noww;
            for(int i=0;i<(int)G[nowc].size();i++){
                if(!ined[G[nowc][i].X] && G[nowc][i].Y < dist[G[nowc][i].X]){
                    dist[G[nowc][i].X]=G[nowc][i].Y;
                }
            }
        }
        for(int i=1;i<=n;i++){
            if(!ined[i]){
                cout<<"-1\n";
                goto jizz;
            }
        }
        cout<<ans<<endl;
        jizz:;
    }
}

prim + priority_queue : 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m;
struct node{int pt,val;};
vector<node> G[10003];
bitset<10003> ined;
int dist[10003];
int ans;
int ppp,i;
priority_queue<node,vector<node>,greater<node>> pq;
bool operator>(const node &a,const node &b){
    return a.val>b.val;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while(cin>>n>>m && n){
        for(i=1;i<=n;i++)G[i].clear();
        ined.reset();
        memset(dist,0,sizeof(dist));
        ans=0;
        while(pq.size())pq.pop();
        for(int i=0;i<m;i++){
            int z,x,c;
            cin>>z>>x>>c;
            G[z].push_back({x,c});
            G[x].push_back({z,c});
        }
        memset(dist,0x7f,sizeof(dist));
        dist[1]=0;
        pq.push({1,0});
        for(ppp=0;ppp<n;ppp++){
            int nowc=-1;
            while(pq.size() && ined[pq.top().pt]){
                pq.pop();
            }
            if(!pq.size()){
                break;
            }
            nowc=pq.top().pt;
            ined[nowc]=1;
            // cout<<"join:nowc:"<<nowc<<endl;
            ans+=pq.top().val;
            for(i=0;i<(int)G[nowc].size();i++){
                if(!ined[G[nowc][i].pt] && G[nowc][i].val < dist[G[nowc][i].pt]){
                    dist[G[nowc][i].pt]=G[nowc][i].val;
                    pq.push({G[nowc][i].pt,dist[G[nowc][i].pt]});
                }
            }
        }
        for(i=1;i<=n;i++){
            if(!ined[i]){
                cout<<"-1\n";
                goto jizz;
            }
        }
        cout<<ans<<"\n";
        jizz:;
    }
}
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)