首页 > 代码库 > Problem I: 俊爷的局域网
Problem I: 俊爷的局域网
分析：这道题就是要求求出俊爷能赚我多少钱！
然后这道题中，俊爷建设的所有路径都是最短的，然后还要求求出在这些最短路径中路径最大的一个--maxcost！
由于是最短路径了，所以我需要的支付的钱为：maxcost*(n-1)；实际所花的钱其实就是将每条路径所花的钱的总和！
然后怎么求出每条路径的花费呢？那么就是使用最小生成树来解决了！在建立最小生成树的时候便可求出最大值maxcost了！
然后剩下的就好办了，直接就是一个减法就ok了！
代码如下：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5201314;
int p[maxn],cnt,mas;
struct qiu
{
int f,t,mon;
bool operator<(const qiu &a)const
{
return mon<a.mon;
}
}road[maxn];
int find(int x)
{
return p[x]==-1?x:p[x]=find(p[x]);
}
int ans()
{
int sum=0;
for(int i=0;i<cnt;i++)
{
int x=find(road[i].f);
int y=find(road[i].t);
if(x!=y)
{
sum+=road[i].mon;
p[x]=y;
if(mas<road[i].mon)
mas=road[i].mon;//求出最小生成树里的最大节点的值！
}
}
return sum;
}
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
memset(p,-1,sizeof(p));//根节点初始化！
cnt=mas=0;//初始化节点数和最大价钱数！
while(m--)
{
int f,t,c;
scanf("%d%d%d",&f,&t,&c);
road[cnt].f=f;
road[cnt].t=t;
road[cnt++].mon=c;
}
sort(road,road+cnt);
int sum=ans();//求出最小花费！
//cout<<"本应该花费钱："<<sum<<" ;"<<"最大花费："<<mas<<endl;
cout<<mas*(n-1)-sum<<endl;//俊爷能赚我多少钱呢？？0.0
}
return 0;
}
Description
俊爷最近投资创办了一家局域网公司，这家公司的业务不仅有地球上的业务，也有外太空的业务。由于DB星球除了钱什么都没有，作为首领的DBZ请俊爷帮他们星球建成局域网。俊爷当然想拿下这笔生意，我们知道A与B联通并且B与C联通，那么A与C也是联通的，现在DBZ要求将DB星球上的所有城市都联通。
俊爷最近有点伤感，他本想趁这个机会多赚一笔，哪知精明的DBZ已经学会如何架设线路费用才是最小的。但DBZ给了俊爷一个机会，他对每条路径支付的费用为俊爷建设的所有路径中的最大值。那么现在俊爷想知道他到底可以赚到DBZ多少钱？（当然如果俊爷欺骗DBZ，那么后果很严重，DBZ将会寻找其他公司架设）。
俊爷架设一个单位长度的线路需要1DBB（DBB星球的货币)
Input
测试数据包含多组。
每组测试数据包含若干行，第一行包含n ( 1 < = n < = 100000 ) , m ( 1 < = m < = 1000000 ) 。代表DB星球有n个城市，m条路径。
接下来的m行每行包含3个整数，u,v ( 1< = u,v < = n ) , c ( 1 < = c < = 1000 000 000 ) 代表从城市u到城市v有一条距离为c的路径。
Output
输出仅包含一个数，为俊爷能赚多少钱。
Sample Input
Sample Output
Problem I: 俊爷的局域网