c++编程一道难题
题目描述
N个点，M条边，其中K条边必选，求所有点点之间都有可达的最小代价。数据保证有解。
输入第一行两个整数n，m。第二行到m+1行，每行四个非负整数，p,u,v,w当p=1时，表示必选边；当p=2时，表示可选边；u,v,w一条无向边端点为u和v，权值为w。
输出最小费用。
样例输入561121123113411411225102255
样例输出9
提示数据范围：对于30%的数据，n<=10m<=100对于50%的数据,n<=200m<=1000对于100%的数据，n<=2000m<=10000
最佳答案
这个参考网上的:
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
const int M = 10005;
int f[N];
struct Edge
{
int p, u, v, w;
} a[M];
int cmp(Edge x, Edge y)
{
if(x.p == y.p) return x.w < y.w;
else return x.p < y.p;
}
int get(int x)
{
if(f[x] == x) return x;
f[x] = get(f[x]);
return f[x];
}
int main()
{
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++)
cin >> a[i].p >> a[i].u >> a[i].v >> a[i].w;
sort(a + 1, a + 1 + m, cmp);
int ans = 0;
for(int i = 1; i <= m; i++) ans += a[i].w;
for(int i = 1; i <= n; i++) f[i] = i;
for(int i = 1; i <= m; i++)
{
int root1 = get(a[i].u), root2 = get(a[i].v);
if(a[i].p == 1)
{
f[root1] = root2; //直接添加
continue;
}
if(root1 == root2) ans -= a[i].w;
else f[root1] = root2;
}
printf("%d\n", ans);
}
追问：
能不能简单一点。。。我看不懂 追答：
这些都是C++基本语法及普通算法,你哪部分没明白?
追问：
struct Edge{ int p, u, v, w;} a[M]; 追答：
这个是定义一个结构对C++来说,结构就是一个特殊的类(若学习C++没有学习类,等于没有学过C++,这点是公认的)它与一般类的区别是,它的成员都是公有的C语言也有结构的,这个你可以先在教材上看下相关的部分
且a[M]中的a是结构数组,对初学者来说是有点难(本来这道题目就不是针对初学者的)因为有二个概念,一个是结构,一个是数组不过任何C/C++教材上肯定全都有的
其他回答
暂无其它回答!
