一定有人问我我死哪里去了……

这题挺简单的，但是对于zzs这种图论渣来讲，是巨大的困难……

这题可以造一个虚拟结点，所有点和它连该点点权长的边，其他边的正常造，然后剩下MST的就很简单了……

然而第一次写Prim……哎

代码：

/**************************************************************
    Problem: 1601
    User: danihao123
    Language: C++
    Result: Accepted
    Time:180 ms
    Memory:3936 kb
****************************************************************/
 
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=301;
int n;
struct Node{
    int u,v,d;
    bool operator < (const Node& x) const{
        return d>x.d;
    }
};
int G[maxn][maxn];
bool vis[maxn];
priority_queue<Node> h;
void expand(int x){
    register int i;
    for(i=0;i<=n;i++)
        if(G[x][i])
            h.push((Node){x,i,G[x][i]});
}
int prim(int x){
    register int e=0,ans=0;
    memset(vis,0,sizeof(vis));
    vis[x]=true;
    expand(x);
    while(e<n){
        Node it=h.top();
        h.pop();
        if(!vis[it.v]){
            vis[it.v]=true;
            ans+=it.d;
            e++;
            expand(it.v);
        }
    }
    return ans;
}
int main(){
    register int i,j;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>G[0][i];
        G[i][0]=G[0][i];
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            cin>>G[i][j];
        }
    cout<<prim(0)<<endl;
    return 0;
}

• 相关文章
• 全局相关文章