本文主要是介绍Air Portshttp://www.lightoj.com/volume_showproblem.php?problem=1059，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最小生成树变形，这一题，真他妈的恶心，由于没看清最后一句话，导致一直wa，，在修建机场和修路方面，如果修路的费用和修飞机场的相同，则优先考虑修飞机场，，
法一：
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#define pf printf
#include<cstdio>
#define N 100005
#define M 10005
using namespace std;
typedef struct node
{int x;int y;int len;bool operator<(node a)const{return len<a.len;}
}Node;
Node s[N];
int Father[M];
int n,m,cost;
int Find(int x)
{if(x==Father[x]) return x;return Father[x]=Find(Father[x]);
}
void in(int &a)
{char ch;while((ch=getchar())<'0'||ch>'9');for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
int main()
{int T;in(T);for(int k=1;k<=T;++k){in(n),in(m),in(cost);for(int i=0;i<=n;++i) Father[i]=i;for(int i=0;i!=m;++i) in(s[i].x),in(s[i].y),in(s[i].len);sort(s,s+m);int num=0;bool flag=false;long long ans=0;for(int i=0;i<m;++i){if(s[i].len>=cost) continue;if(num==n-1) {flag=1;break;}int x=Find(s[i].x);int y=Find(s[i].y);if(x!=y){num++;Father[x]=y;ans+=s[i].len;}}if(flag) pf("Case %d: %lld 1\n",k,ans+cost);else{int res=0;for(int i=1;i<=n;++i)if(i==Find(i)) res++;pf("Case %d: %lld %d\n",k,ans+res*cost,res);}}return 0;
}
#include<iostream>
#include<string.h>
#include<string>
#include<algorithm>
#define pf printf
#include<cstdio>
#define N 100005
#define M 10005
using namespace std;
typedef struct node
{int x;int y;int len;bool operator<(node a)const{return len<a.len;}
}Node;
Node s[N];
int Father[M];
int n,m,cost;
int Find(int x)
{if(x==Father[x]) return x;return Father[x]=Find(Father[x]);
}
void in(int &a)
{char ch;while((ch=getchar())<'0'||ch>'9');for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';
}
int main()
{int T;in(T);for(int k=1;k<=T;++k){in(n),in(m),in(cost);for(int i=0;i<=n;++i) Father[i]=i;for(int i=0;i!=m;++i) in(s[i].x),in(s[i].y),in(s[i].len);sort(s,s+m);int num=0;long long ans=0;for(int j=0;j<m;j++){if(num==n-1) break;if(s[j].len>=cost) continue;int xx=Find(s[j].x),yy=Find(s[j].y);if(xx!=yy){num++;Father[xx]=yy;ans+=s[j].len;}}printf("Case %d: %lld %d\n",k,(ans+(n-num)*cost),n-num);}return 0;
}
这篇关于Air Portshttp://www.lightoj.com/volume_showproblem.php?problem=1059的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
