首页 > 代码库 > 洛谷 P2126 Mzc家中的男家丁

洛谷 P2126 Mzc家中的男家丁

题目背景

mzc与djn的…还没有众人皆知,所以我们要来宣传一下。

题目描述

mzc家很有钱(开玩笑),他家有n个男家丁,现在mzc要将她们全都聚集起来(干什么就不知道了)。现在知道mzc与男家丁们互相之间通信的时间,请算出把他们每个人叫到需要的总时间(要重复的哦)。保证能把他们每个人叫到。

输入输出格式

输入格式:

 

第一行有一个数n,表示有n个男家丁。第二行一个数m表示有m条通信路线。之后m行,每行三个数a[i],b[i],c[i],表示第a[i]个男家丁(或mzc)和第b[i]个男家丁(或mzc)通信需要时间(双向)。ai=0表示mzc。

 

输出格式:

 

一行,一个数sum,表示把他们每个人叫到需要的总时间。

 

输入输出样例

输入样例#1:
5120 2 152 3 203 5 131 3 290 1 302 4 210 3 235 1 480 4 170 5 271 2 432 5 41
输出样例#1:
94

说明

n<=2300

m<=2300000

 

技术分享
 1 /* 2 明显的MST 3 但是这个题用kruskal就是WA(百思不得其姐) 4 所以就写了一遍prim 就过了 5 */ 6 #include<cstdio> 7 #include<cstring> 8 #include<iostream> 9 #define MAXN 1000010 using namespace std;11 int n,m,x,y,ans;12 int f[2301][2301],l[MAXN];13 bool used[MAXN];14 inline void read(int&x) {15     x=0;int f=1;char c=getchar();16     while(c>9||c<0) {if(c==-) f=-1;c=getchar();}17     while(c>=0&&c<=9) {x=(x<<1)+(x<<3)+c-48;c=getchar();}18     x=x*f;19 }20 inline void prim() {21     memset(l,127/3,sizeof l);22     memset(used,false,sizeof used);23     l[0]=0;24     int min,k;25     for(int i=0;i<=n;i++) {26         min=1e9;27         for(int j=0;j<=n;j++) {28             if(l[j]<min&&!used[j]) {29                 min=l[j];30                 k=j;31             }32         }33         used[k]=true;34         ans+=l[k];35         for(int j=1;j<=n;j++) {36             if(!used[j]&&f[k][j]<l[j])37               l[j]=f[k][j];38         }39     }40     return;41 }42 int main() {43     read(n);read(m);44     for(int i=0;i<=n;i++)45       for(int j=0;j<=n;j++)46         f[i][j]=1e9;47     for(int i=1;i<=m;i++) {48         read(x);read(y);49         read(f[x][y]);50         f[y][x]=f[x][y];51     }52     prim();53     printf("%d\n",ans);54     return 0;55 }
代码

 

洛谷 P2126 Mzc家中的男家丁