NYOJ38布线问题 prim 最小生成树MST

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 01 月 23 日

#include<iostream>  
#include<cstring>  
using namespace std;  
#define typec int                 
#define V 502  
const typec inf = 0x0f3f3f3f;  
int vis[V]; typec lowc[V];   
typec cost[V][V];  
typec prim(int n)  
{   
    int i, j, p;   
    typec minc, res = 0;   
    memset(vis, 0, sizeof(vis));   
    vis[1] = 1;   
    for (i=2; i<=n; i++) lowc[i] = cost[1][i];   
    for (i=2; i<=n; i++) {   
        minc = inf; p = -1;   
        for (j=1; j<=n; j++)   
            if (1 != vis[j] && minc > lowc[j]) {   
                minc = lowc[j]; p = j;   
            }   
        if (inf == minc) return -1;  
        res += minc; vis[p] = 1;   
        for (j=1; j<=n; j++)   
            if (0 == vis[j] && lowc[j] > cost[p][j])   
                lowc[j] = cost[p][j];   
    }   
    return res;   
}   
int main()  
{  
    int n;  
    cin>>n;  
    while(n--)  
    {  
        int v,e;  
        cin>>v>>e;  
        int x,y;  
        for (int i=0;i<e;i++)  
        {  
            cin>>x>>y;  
            cin>>cost[x][y];  
            cost[y][x]=cost[x][y];  
        }  
        int least=999;  
        int vcost;  
        for (int i=0;i<v;i++)  
        {  
            cin>>vcost;  
            if(least>vcost)   
                least=vcost;  
        }  
        least +=prim(v);  
        cout<<least<<endl;  
    }  
    return 0;  
} 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期六, 2017 年 10 月 21 日