[51nod]1443 路径和树【最短路+MST】

1443 路径和树

【题目描述】

传送门

【题解】

我们要同时满足两个条件,那么就需要先求出这个最短路,然后取出最短路径上的边刷MST就可以了。

代码如下

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define MAXN 300005
using namespace std;
int n,m,e,S,fa[MAXN];
LL dst[MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN<<1],W[MAXN<<1],son[MAXN<<1];
    void Add(int x,int y,int z){son[++tot]=y;W[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
struct xcw{
    int x,y,w;
    bool operator <(const xcw b)const{return w<b.w;}
}a[MAXN];
queue<int>que;
bool vis[MAXN];
void SPFA(int x){
    memset(dst,63,sizeof(dst));
    que.push(x);vis[x]=1;dst[x]=0;
    while(!que.empty()){
        x=que.front();que.pop();vis[x]=0;
        for(int j=E.lnk[x];j;j=E.nxt[j])
        if(dst[E.son[j]]>dst[x]+E.W[j]){
            dst[E.son[j]]=dst[x]+E.W[j];
            if(!vis[E.son[j]]) vis[E.son[j]]=1,que.push(E.son[j]);
        }
    }
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
LL Kruscal(){
    memset(vis,0,sizeof(vis));
    LL Ans=0,Num=0;
    sort(a+1,a+1+e);
    for(int i=1;i<=e;i++){
        int fx=get(a[i].x),fy=get(a[i].y);
        if(vis[a[i].y]||fx==fy) continue;
        vis[a[i].y]=1;fa[fy]=fx;Ans+=a[i].w;
    }
    return Ans;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1443.in","r",stdin);
    freopen("1443.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,w;scanf("%d%d%d",&x,&y,&w);
        E.Add(x,y,w);E.Add(y,x,w);
    }
    scanf("%d",&S);
    for(int i=1;i<=n;i++) fa[i]=i;
    SPFA(S);
    for(int i=1;i<=n;i++)
    for(int j=E.lnk[i];j;j=E.nxt[j])
    if(dst[i]+E.W[j]==dst[E.son[j]]) a[++e]=(xcw){i,E.son[j],E.W[j]};
    printf("%lld\n",Kruscal());
    return 0;
}

发表评论

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

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部