【题目描述】
Tyvj已经一岁了,网站也由最初的几个用户增加到了上万个用户,随着Tyvj网站的逐步壮大,管理员的数目也越来越多,现在你身为Tyvj管理层的联络员,希望你找到一些通信渠道,使得管理员两两都可以联络(直接或者是间接都可以)。Tyvj是一个公益性的网站,没有过多的利润,所以你要尽可能的使费用少才可以。
目前你已经知道,Tyvj的通信渠道分为两大类,一类是必选通信渠道,无论价格多少,你都需要把所有的都选择上;还有一类是选择性的通信渠道,你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。
【输入】
第一行n,m表示Tyvj一共有n个管理员,有m个通信渠道;
第二行到m+1行,每行四个非负整数,p,u,v,w 当p=1时,表示这个通信渠道为必选通信渠道;当p=2时,表示这个通信渠道为选择性通信渠道;u,v,w表示本条信息描述的是u,v管理员之间的通信渠道,u可以收到v的信息,v也可以收到u的信息,w表示费用。
【输出】
最小的通信费用。
【输入样例】
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5【输出样例】
9
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 10001
#define MOD 123
#define E 1e-6
using namespace std;
int father[N];
struct Node{
int p;
int u;
int v;
int w;
}g[N*N];
int cmp(Node a,Node b)
{
if(a.p==2&&b.p==2)
return a.w<b.w;
return a.p<b.p;
}
int Find(int x)
{
if(father[x]==x)
return x;
return father[x]=Find(father[x]);
}
int Union(int x,int y)
{
x=Find(x);
y=Find(y);
if(x!=y)
{
father[y]=x;
return 1;
}
return 0;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++)
cin>>g[i].p>>g[i].u>>g[i].v>>g[i].w;
sort(g+1,g+1+m,cmp);
int sum=0;
for(int i=1;i<=m;i++)
{
if(g[i].p==1)
{
sum+=g[i].w;
Union(g[i].u,g[i].v);
}
else if(g[i].p==2)
{
if(Union(g[i].u,g[i].v))
sum+=g[i].w;
}
}
cout<<sum<<endl;
return 0;
}
信息学奥赛一本通T1393:最小生成树 联络员 归属于 最小生成树,更多同类题解源程序见:最小生成树 和 联络员
0 篇文章
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!