[编程题]畅通工程
- 热度指数：6275 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。
输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M < =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。
输出描述:
对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。
示例1
输入
3 3 1 2 1 1 3 2 2 3 4 1 3 2 3 2 0 100
输出
3 ?
这道题主要考查最小生成树，可以采用基于并查集的kruskal算法，省事直接把全部边sort了。
注意测例中还会给出自环、相同节点更短边、多连通图的情况，不过在sort之后，只需要对多连通做判断就行了
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 105;
struct node {
int a,b;
int len;
bool operator<(node x) {
return len < x.len;
}
}road[MAXN];
int tab[MAXN]; //并查集表
int father(int x) {
return (x == tab[x]) ? x : father(tab[x]);
}
void Union(int a, int b) {
tab[father(b)] = father(a);
}
bool CheckLink(int m) { //检查是否为多连通图，若有一节点的根与众不同，则为多连通图
int f = father(1);
for (int i = 2; i <= m; i++) {
if (f != father(i))
return false;
}
return true;
}
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
if (!n) break;
for (int i = 1; i <= m; i++) //并查集初始化
tab[i] = i;
int ans = 0;
for (int i = 1; i <= n; i++) { //所有下标从1开始
scanf("%d%d%d", &road[i].a,
&road[i].b, &road[i].len);
}
sort(road + 1, road + 1 + n); //排序后即为kruskal算法的思想，依大小顺序并入有效边
for (int i = 1; i <= n; i++) {
int a = road[i].a, b = road[i].b;
if (father(a) == father(b)) continue;
Union(a, b);
ans += road[i].len;
//cout << "road :" << road[i].a << " " << road[i].b << " " << road[i].len << endl;
}
if (CheckLink(m)) printf("%d\n", ans);
else printf("?\n");
}
return 0;
}
编辑于 2020-03-19 20:34:00
回复(0)
#include<stdio.h>
#include<algorithm>
#define N 101
using namespace std;
int Tree[N];
typedef struct Edge{
int a,b;
int cost;
}Edge;
int FindRoot(int x){
if(Tree[x]==-1) return x;
else{
Tree[x]=FindRoot(Tree[x]);
return Tree[x];
}
}
bool cmp(Edge a,Edge b){
return a.cost<b.cost;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&n!=0){
int i;
Edge e[N];
for(i=1;i<=m;i++)
Tree[i]=-1;
for(i=0;i<n;i++)
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].cost);
sort(e,e+n,cmp);
int a,b;
int ans=0;
for(i=0;i<n;i++){
a=FindRoot(e[i].a);
b=FindRoot(e[i].b);
if(a!=b){
Tree[b]=a;
ans+=e[i].cost;
}
}
int count=0;
for(i=1;i<=m;i++)
if(Tree[i]==-1)
count++;
if(count==1)
printf("%d\n",ans);
else
puts("?");
}
}
发表于 2018-01-21 21:22:07
回复(0)
/*
*kruskal 最小生成树。并查集表征连通分量。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4;
struct edge
{
int u, v, w;
edge(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
};
vector<edge> edges;
int father[maxn+5];
int n, m;
bool cmp(edge a, edge b)
{
return a.w < b.w;
}
void Initial()
{
for(int i = 1;i <= n; i++) father[i] = i;
}
int getFather(int x)
{
int a = x;
while(x != father[x]) x = father[x];
//路径压缩
while(a != father[a])
{
int z = a; a = father[a]; father[z] = x;
}
return x;
}
void Create()
{
int u, v, w, f;
for(int i = 0;i < m; i++)
{
cin >> u >> v >> w;
edges.push_back(edge(u, v, w));
}
}
int Kruskal()
{
Initial();
sort(edges.begin(), edges.end(), cmp);
int ans = 0, num = 0;
for(int i = 0;i < edges.size(); i++)
{
int fu = getFather(edges[i].u);
int fv = getFather(edges[i].v);
if(fu != fv)
{
father[fu] = fv;
ans += edges[i].w; num++;
if(num == n-1) break;
}
}
if(num != n-1) return -1;
else return ans;
}
int main()
{
ios::sync_with_stdio(false);
while(cin >> m >> n && m)
{
Create();
int ans = Kruskal();
if(ans == -1) cout << "?" << '\n';
else cout << ans << '\n';
}
return 0;
}
发表于 2021-01-22 21:00:33
回复(0)
此题考查的是并查集+最小生成树
// runtime: 4mm
// space: 432K
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 101;
struct Road {
int from;
int to;
int price;
bool operator< (const Road& r) const {
return price < r.price;
}
};
int father[MAX];
int height[MAX];
Road road[MAX];
void Initial(int n) { // 初始化
for (int i = 1; i <= n; ++i) {
father[i] = i;
height[i] = 0;
}
}
int Find(int x) { // 查找根结点
if (x != father[x]) { // 路径压缩
father[x] = Find(father[x]);
}
return father[x];
}
void Union(int a, int b) { // 合并
a = Find(a);
b = Find(b);
if (a != b) {
if (height[a] < height[b]) {
father[a] = b;
} else if (height[a] > height[b]) {
father[b] = a;
} else {
father[a] = b;
height[b]++;
}
}
}
int MinPrice(int roadNum, int villageNum) {
int answer = 0, part = 0;
sort(road, road + roadNum);
for (int i = 0; i < roadNum; ++i) {
Road current = road[i];
if (Find(current.from) != Find(current.to)) {
Union(current.from, current.to);
answer += current.price;
}
}
for (int j = 1; j <= villageNum; ++j) {
if (father[j] == j)
part++;
}
if (part != 1)
answer = -1;
return answer;
}
int main() {
int roadNum, villageNum;
while (cin >>roadNum) {
if (roadNum == 0)
break;
cin >> villageNum;
Initial(villageNum);
for (int i = 0; i < roadNum; ++i) {
cin >> road[i].from >> road[i].to >> road[i].price;
}
int answer = MinPrice(roadNum, villageNum);
if (answer == -1)
cout << "?" << endl;
else
cout << answer << endl;
}
return 0;
}
编辑于 2020-03-29 12:16:10
回复(0)
Java
import java.util.Arrays;
import java.util.Scanner;
public class Main {
//并查集+Kruskal算法
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
if (n == 0) break;
int m = scanner.nextInt();
UnionFind unionFind = new UnionFind(m + 1);
Path[] paths = new Path[n];
for (int i = 0; i < n; i++) paths[i] = new Path(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
Arrays.sort(paths);
int sum = 0;
for (Path path : paths) {
if (unionFind.count > 2) {
if (unionFind.find(path.a)!=unionFind.find(path.b)){
unionFind.union(path.a, path.b);
sum += path.cost;
}
} else break;
}
System.out.println(unionFind.count==2?sum:"?");
}
}
public static class UnionFind {
private int[] id;
public int count;
public UnionFind(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
public int find(int p) {
return id[p];
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) return;
for (int i = 0; i < id.length; i++)
if (id[i] == pRoot) id[i] = qRoot;
count--;
}
}
static class Path implements Comparable<Path> {
Integer a;
Integer b;
Integer cost;
public Path(Integer a, Integer b, Integer cost) {
this.a = a;
this.b = b;
this.cost = cost;
}
@Override
public int compareTo(Path o) {
return this.cost.compareTo(o.cost);
}
}
}
发表于 2020-03-20 17:19:16
回复(0)
#include<cstdio>
(802)#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=100;
struct Edge{
int from;
int to;
int len;
};
int father[MAXN];
int height[MAXN];
Edge e[MAXN*MAXN];
bool visit[MAXN]={false};
void initial(int n){
for(int i=0;i<=n;i++){
father[i]=i; //初始每个结点的父亲为自己
height[i]=0; //每个结点的高度初始为 0
}
}
int find(int x){ //查找根结点
if(x!=father[x]){ //根结点不为自己
father[x]=find(father[x]);//则回溯到根结点
}
return father[x];
}
void Union(int x,int y){
x=find(x); //x的根结点
y=find(y); //找到 y 的根结点
if(x!=y){ //x y 的根结点不一致
if(height[x]<height[y]){//矮树为高树的子树
father[x]=y; //将 x树的根结点设为y
}else if(height[x]>height[y]) father[y]=x;
else { //两树一样高
father[y]=x;
height[x]++;
}
}
return ;
}
bool cmp(Edge x,Edge y){
return x.len<y.len;
}
int kruskal(int m,int n){
int sum=0,num=0;
initial(m); //初始化
sort(e,e+n,cmp);
for(int i=0;i<n;i++){
Edge cur=e[i];
if(find(cur.from)!=find(cur.to)&&visit[cur.from]==false&&visit[cur.to]==false){
Union(cur.from,cur.to);//合并集合
visit[cur.from]==true;
visit[cur.to]==true;
sum+=cur.len;
}
}
for(int i=1;i<=m;i++){
if(i==find(i)) num++;
}
if(num==1) return sum;
else return -1;
}
int main(){
int n,m;//m个村庄，n条道路
while(scanf("%d",&n)!=EOF){
if(n==0) break;
scanf("%d",&m);
for(int i=0;i<n;i++){
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].len);
}
int answer=kruskal(m,n);
if(answer!=-1) printf("%d\n",answer);
else printf("?\n");
}
return 0;
} 畅通工程系列我都是用并查集，kruskal算法来做的~代码长，但是套路简单
发表于 2020-03-08 13:32:38
回复(1)
#include<stdio.h>
#include<stdlib.h>
#define N 101
int Tree[N];
typedef struct edge{
int start;
int end;
int edge;
}edge, *Edge;
int findRoot(int x){
if(Tree[x] == -1) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
void Sort(Edge edges, int n){
for(int i = n-1; i>=0; i--){
for(int j = 0; j<i; j++){
if(edges[j].edge > edges[j+1].edge){
edge tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
int main(){
int n, m, a, b;
while(scanf("%d", &n) != EOF && n != 0){
scanf("%d", &m);
for(int i = 0; i<m; i++) Tree[i] = -1;
Edge edges = (Edge)malloc(sizeof(edge)*n);
for(int i = 0; i<n; i++){
scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].edge);
}
Sort(edges, n);
int ans = 0;
for(int i = 0; i<n; i++){
a = findRoot(edges[i].start);
b = findRoot(edges[i].end);
if(a != b){
Tree[a] = b;
ans += edges[i].edge;
}
}
int index = 0;
for(int i = 0; i<m; i++){
if(Tree[i] == -1){
if(index == 1){
printf("?\n");
index = 2;
break;
}
else index++;
}
}
if(index != 2) printf("%d\n", ans);
}
return 0;
}
#include<stdlib.h>
#define N 101
int Tree[N];
typedef struct edge{
int start;
int end;
int edge;
}edge, *Edge;
int findRoot(int x){
if(Tree[x] == -1) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
void Sort(Edge edges, int n){
for(int i = n-1; i>=0; i--){
for(int j = 0; j<i; j++){
if(edges[j].edge > edges[j+1].edge){
edge tmp = edges[j];
edges[j] = edges[j+1];
edges[j+1] = tmp;
}
}
}
}
int main(){
int n, m, a, b;
while(scanf("%d", &n) != EOF && n != 0){
scanf("%d", &m);
for(int i = 0; i<m; i++) Tree[i] = -1;
Edge edges = (Edge)malloc(sizeof(edge)*n);
for(int i = 0; i<n; i++){
scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].edge);
}
Sort(edges, n);
int ans = 0;
for(int i = 0; i<n; i++){
a = findRoot(edges[i].start);
b = findRoot(edges[i].end);
if(a != b){
Tree[a] = b;
ans += edges[i].edge;
}
}
int index = 0;
for(int i = 0; i<m; i++){
if(Tree[i] == -1){
if(index == 1){
printf("?\n");
index = 2;
break;
}
else index++;
}
}
if(index != 2) printf("%d\n", ans);
}
return 0;
}
发表于 2019-08-07 14:31:40
回复(0)
/*畅通工程*/只想问一下各位大佬，为什么我想着用DFS来遍历全部节点，得出每次的成本总和，
#include<stdio.h>
#define INF 99999
#define MAX 100
int vis[MAX];
int icount;//总代价
int a[MAX][MAX];
int N,M;//N条道路，M座村庄
int dist[MAX];
//DFS遍历全部村庄
/*void DFS(int i){
int j;
vis[i]=1;
for(j=1;j<=M;j++){
if(a[i][j]!=-1&&!vis[j]){//i和j之间有通道且j未被访问过
icount+=a[i][j];
DFS(j);
}
}
}*/
/*void init(int v[],int M){
int i;
for(i=1;i<=M;i++)
v[i]=0;
}*/
int main(){
int i,j;
while(scanf("%d%d",&N,&M)!=EOF){
if(N==0){
continue;
}else{
for(i=0;i<MAX;i++){
for(j=1;j<MAX;j++){
if(i==j){
a[i][j]=0;
}else{
a[i][j]=INF;//一开始不同村庄都不可达
}
}
}
int b,c,d;
for(i=0;i<N;i++){
scanf("%d%d%d",&b,&c,&d);
if(a[b][c]>d)
a[b][c]=a[c][b]=d;//初赋值成本
}
/*接下来判断是否可连通
(遍历整个二维数组，记录-1的个数，只要有一个村庄除了到自己的距离为0,
其余都是-1,那么就是不连通)
*/
int flag=1;
int count;
for(i=1;i<=M;i++){
count=0;
for(j=1;j<=M;j++){
if(a[i][j]==INF)
count++;
}
if(count==M-1){//只需要检测到有一个村庄不连通
flag=0;
}
}
if(flag==0){
printf("?\n");
}else{//如果连通的话,遍历所有点，DFS(实在不知道哪里出问题了)
/* int minlen=999;
for(i=1;i<=M;i++){
icount=0;
init(vis,M);
DFS(i);
if(icount<minlen)
minlen=icount;
}
printf("%d\n",minlen);*/
//只能改用prim算法了
int sum=0,count=1,min_dist,t;
for(i=1;i<=M;i++){
dist[i]=a[1][i];//dist先保存着从节点1到其他节点的成本
}
while(count<M){
min_dist=INF;
for(i=1;i<=M;i++){
//这个if是找到距离i最近的一条路
if(dist[i]<min_dist&&dist[i]!=0){
//0是到自己本身
min_dist=dist[i];
t=i;
}
}
dist[t]=0;
sum+=min_dist;
for(i=1;i<=M;i++){
if(a[t][i]<dist[i]){
dist[i]=a[t][i];
}
}
++count;
}
printf("%d\n",sum);
}
}
}
return 0;
}
编辑于 2019-03-19 17:45:53
回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//自己回忆了下prim算法按感觉写的
//这道题实在想爆粗口，开始写觉得正确死活过不了，仔细查看样例，发现居然有 3 4 6，3 4 5 这样的毒数据，我真是***了，小改了一下过了
//望大家注意
int dis[105][105];
int Visited[105][105];
int visited[105];
int main(void){
int n,m,i,j,point,res,k,minDis,start,end,cnt,temp;
while(scanf("%d %d",&n,&m) != EOF){
if(n == 0) return 0;
memset(dis,0,sizeof(dis));
memset(visited,0,sizeof(visited));
memset(Visited,0,sizeof(Visited));
for(i = 0;i < n;i++){
scanf("%d %d",&j,&k);
if(Visited[j][k] == 0 ){ //两个节点之间的距离取最小的那一个
Visited[j][k] = Visited[k][j] = 1;
scanf("%d",&dis[j][k]);
dis[k][j] = dis[j][k];
}
else {
scanf("%d",&temp);
if(temp < dis[j][k]){
dis[j][k] = temp;
dis[k][j] = temp;
}
}
}
visited[1] = 1;
point = m - 1;
res = 0;
while(point){
minDis = 9999999;
for(i = 1; i <= m;i++){
if(visited[i] == 1){
for(j = 1;j <= m;j++){
if(visited[j] == 0 && dis[i][j] != 0){
if(dis[i][j] < minDis){
minDis = dis[i][j];
end = j;
}
}
}
}
}
visited[end] = 1;
res += minDis;
point--;
}
cnt = 0;
for(i = 1 ;i <= m ;i++){
if(visited[i] == 1) cnt++;
}
if(cnt == m) printf("%d\n",res);
else {
printf("?\n");
}
}
return 0;
}
发表于 2019-03-11 02:19:37
回复(0)
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int matrix[101][101];
int dist[101];
int main(){
int i,j,n,m,x,y,cost;
while(cin>>n>>m){
if(n==0){break;}
else{
for(i=0;i<101;++i){
for(j=0;j<101;++j){
if(i==j){matrix[i][j]=0;}
else{matrix[i][j]=INT_MAX;}
}
}
for(i=0;i<n;++i){
cin>>x>>y>>cost;
if(matrix[x][y]>cost){matrix[x][y]=matrix[y][x]=cost;}//初始化
}
bool is_connect=true;
int count=0;
for(i=1;i<=m;++i){//判断是否连通
count=0;
for(j=1;j<=m;++j){
if(matrix[i][j]==INT_MAX){++count;}
}
if(count==m-1){is_connect=false;}//如果一个村除了到自己的距离都是INT_MAX,说明图不连通
}
if(is_connect==false){cout<<"?"<<endl;}
else{//prim方法构造最小生成树
int sum=0,count=1,min_dist,t;
for(i=1;i<=m;++i){dist[i]=matrix[1][i];}
while(count<m){
min_dist=INT_MAX;
for(i=1;i<=m;++i){
if(dist[i]<min_dist&&dist[i]!=0){min_dist=dist[i];t=i;}
}
dist[t]=0;
sum+=min_dist;
for(i=1;i<=m;++i){
if(matrix[t][i]<dist[i]){dist[i]=matrix[t][i];}
}
++count;
}
cout<<sum<<endl;
}
}
}
return 0;
}
发表于 2019-03-09 14:01:49
回复(0)
#include<stdio.h>
#include<algorithm>
using namespace std;
int tree[110];
struct Edge{
int a,b;
int cost;
}buf[110];
bool cmp(Edge a,Edge b){
return a.cost<b.cost;
}
int sum[110];
int findroot(int x){
if(tree[x]==-1){
return x;
}
else {
int tmp=findroot(tree[x]);
tree[x]=tmp;
return tmp;
}
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
if(n==0){
break;
}
for(int i=1;i<=n;i++){
scanf("%d%d%d",&buf[i].a,&buf[i].b,&buf[i].cost);
}
sort(buf+1,buf+1+n,cmp);
for(int i=1;i<=m;i++){
tree[i]=-1;
sum[i]=1;
}
int ans=0;
for(int i=1;i<=n;i++){
int a=findroot(buf[i].a);
int b=findroot(buf[i].b);
if(a!=b){
tree[a]=b;
sum[b]=sum[a]+sum[b];
ans=ans+buf[i].cost;
}
}
int flag=0;
for(int i=1;i<=m;i++){
if(sum[i]==m){
flag=1;
break;
}
}
if(flag!=0){
printf("%d\n",ans);
}
else printf("?\n");
}
return 0;
}
发表于 2019-02-04 13:46:44
回复(0)
def findRoot(village):
global villages
if villages[village] == -1:
return village
else:
temp = findRoot(villages[village])
villages[village] = temp
return temp
while True:
try:
n,m = list(map(int,input().split()))
if n == 0:
break
roads = []
for i in range(n):
roads.append(list(map(int,input().split())))
values = 0
villages = [-1 for i in range(m+1)]
nodeNum = 1
roads.sort(key=lambda x:x[2])
for i in range(n):
a = findRoot(roads[i][0])
b = findRoot(roads[i][1])
if a != b:
villages[a] = b
values += roads[i][2]
nodeNum += 1
if nodeNum == m:
break
if nodeNum == m:
print(values)
else:
print('?')
except Exception:
break
编辑于 2018-09-28 15:38:50
回复(0)
最小生成树
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
class Edge implements Comparable{
int begin;
int end;
int cost;
Edge next;
public Edge(int begin, int end, int cost){
this.begin = begin;
this.end = end;
this.cost = cost;
this.next = null;
}
@Override
public int compareTo(Object o){
Edge edge = (Edge) o;
return this.cost - edge.cost;
}
}
public class Main{
static int[] root;
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
while(scan.hasNext()){
int N = scan.nextInt();
int M = scan.nextInt();
root = new int[M+1];
for(int i=0;i<=M;i++)
root[i] = -1;
ArrayList<Edge> arr = new ArrayList<Edge>();
for(int i=0;i<N;i++){
Edge edge = new Edge(scan.nextInt(), scan.nextInt(), scan.nextInt());
arr.add(edge);
}
Collections.sort(arr);
int sum=0;
while(!arr.isEmpty()){
Edge tmp = arr.get(0);
int a = findRoot(tmp.begin);
int b = findRoot(tmp.end);
if(a==b) arr.remove(0);
else{
root[a] = b;
sum += tmp.cost;
}
}
int cnt=0;
for(int i=1;i<=M;i++)
if(root[i]==-1) cnt++;
if(cnt==1) System.out.println(sum);
else System.out.println("?");
}
}
public static int findRoot(int x){
if(root[x]==-1) return x;
int tmp = findRoot(root[x]);
root[x] = tmp;
return tmp;
}
}
发表于 2018-03-04 14:02:33
回复(0)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 100
int tree[N];
int findroot(int x){
if(tree[x]==-1)return x;
else{
int tmp=findroot(tree[x]);
tree[x]=tmp;
return tmp;
}
}
struct edge{
int a,b;
int cost;
bool operator <(const edge &a)const{
return cost<a.cost;
}
}edge[120];
int main(){
int m,n;
while(scanf("%d%d",&n,&m)!=EOF&&n!=0){
for(int i=1;i<=n;++i)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
sort(edge+1,edge+1+n);
for(int i=1;i<=m;++i)tree[i]=-1;
int ans=0;
for(int i=1;i<=n;++i){
int a=findroot(edge[i].a);
int b=findroot(edge[i].b);
if(a!=b){
tree[a]=b;
ans+=edge[i].cost;
}
}
int cnt=0;
for(int i=1;i<=m;i++)
if(tree[i]==-1)cnt++;
(cnt==1)?printf("%d\n",ans):printf("?\n");
}
return 0;
}
#include <algorithm>
using namespace std;
#define N 100
int tree[N];
int findroot(int x){
if(tree[x]==-1)return x;
else{
int tmp=findroot(tree[x]);
tree[x]=tmp;
return tmp;
}
}
struct edge{
int a,b;
int cost;
bool operator <(const edge &a)const{
return cost<a.cost;
}
}edge[120];
int main(){
int m,n;
while(scanf("%d%d",&n,&m)!=EOF&&n!=0){
for(int i=1;i<=n;++i)
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
sort(edge+1,edge+1+n);
for(int i=1;i<=m;++i)tree[i]=-1;
int ans=0;
for(int i=1;i<=n;++i){
int a=findroot(edge[i].a);
int b=findroot(edge[i].b);
if(a!=b){
tree[a]=b;
ans+=edge[i].cost;
}
}
int cnt=0;
for(int i=1;i<=m;i++)
if(tree[i]==-1)cnt++;
(cnt==1)?printf("%d\n",ans):printf("?\n");
}
return 0;
}
发表于 2018-01-21 23:32:04
回复(0)
不知道其他正确的答案怎么个想法，说说我自己做过的过程。
熟悉并查集的同学看到这题，第一想法就是最小生成树，没错，你想对了。
然后按照最小生成树的方法完成之后，提交，发现为成功所有实例，为什么？
对比数据发现，重复数据输入会影响之前的输入，举例，已经读入了1 5 10，代表村庄1到村庄5的建设成本是10。然后又输入了1 5 4，问题就出现在了这里，按以往算法，我们会略过这条数据，因为1与5已经连通了，但在此题里，我们还要更新数据4，说明村庄到村庄5的建设成本是4，其次类推，其他结点相同。
注意到这个地方，即可AC，代码如下，凑合看。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
class road {
int begin;
int end;
int weight;
public road(int begin, int end, int weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
@Override
public boolean equals(Object obj) {
road o = (road) obj;
return this.begin == o.begin && this.end == o.end;
}
}
public class Main {
static int[] tree;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
if (n == 0)
break;
int minWeight = 0;
int m = scanner.nextInt();
tree = new int[m + 1];
List<road> list = new ArrayList<>();
for (int i = 0; i < tree.length; i++)
tree[i] = -1;
for (int i = 0; i < n; i++) {
int begin = scanner.nextInt();
int end = scanner.nextInt();
int weight = scanner.nextInt();
road r = new road(begin, end, weight);
if (!list.contains(r))
list.add(r);
else {
int index = list.indexOf(r);
if (weight < list.get(index).weight)
list.get(index).weight = weight;
}
}
list.sort(new Comparator<road>() {
@Override
public int compare(road o1, road o2) {
return o1.weight <= o2.weight ? -1 : 1;
}
});
for (road r : list) {
int beginRoot = findRoot(r.begin);
int endRoot = findRoot(r.end);
if (beginRoot != endRoot) {
tree[beginRoot] = endRoot;
minWeight += r.weight;
}
}
int connect = 0;
for (int i = 1; i <= m; i++)
if (tree[i] == -1)
connect++;
if (connect > 1)
System.out.println("?");
else
System.out.println(minWeight);
}
scanner.close();
}
static int findRoot(int x) {
if (tree[x] == -1)
return x;
int root = findRoot(tree[x]);
tree[x] = root;
return root;
}
}
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
class road {
int begin;
int end;
int weight;
public road(int begin, int end, int weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
@Override
public boolean equals(Object obj) {
road o = (road) obj;
return this.begin == o.begin && this.end == o.end;
}
}
public class Main {
static int[] tree;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
if (n == 0)
break;
int minWeight = 0;
int m = scanner.nextInt();
tree = new int[m + 1];
List<road> list = new ArrayList<>();
for (int i = 0; i < tree.length; i++)
tree[i] = -1;
for (int i = 0; i < n; i++) {
int begin = scanner.nextInt();
int end = scanner.nextInt();
int weight = scanner.nextInt();
road r = new road(begin, end, weight);
if (!list.contains(r))
list.add(r);
else {
int index = list.indexOf(r);
if (weight < list.get(index).weight)
list.get(index).weight = weight;
}
}
list.sort(new Comparator<road>() {
@Override
public int compare(road o1, road o2) {
return o1.weight <= o2.weight ? -1 : 1;
}
});
for (road r : list) {
int beginRoot = findRoot(r.begin);
int endRoot = findRoot(r.end);
if (beginRoot != endRoot) {
tree[beginRoot] = endRoot;
minWeight += r.weight;
}
}
int connect = 0;
for (int i = 1; i <= m; i++)
if (tree[i] == -1)
connect++;
if (connect > 1)
System.out.println("?");
else
System.out.println(minWeight);
}
scanner.close();
}
static int findRoot(int x) {
if (tree[x] == -1)
return x;
int root = findRoot(tree[x]);
tree[x] = root;
return root;
}
}
发表于 2018-01-20 21:21:23
回复(2)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 101;
struct Edge {
int from; //边的起点
int to; //边的终点
int length; //边的长度
bool operator<(const Edge& e) {
return length < e.length;
}
};
vector<Edge>edge(MAXN); //边集
vector<int>father(MAXN); //父亲结点
vector<int>height(MAXN); //结点高度
void Initial(int n) { //初始化
for (int i = 0; i <= n; i++) {
father[i] = i; //结点的父亲为自己
height[i] = 0; //结点的高度为0
}
}
int Find(int x) { //查找根结点
if (x != father[x]) { //路径压缩
father[x] = Find(father[x]);
}
return father[x];
}
void Union(int x, int y) { //查找根结点
x = Find(x);
y = Find(y);
if (x != y) { //矮树作为高树的子树
if (height[x] < height[y]) {
father[x] = y;
} else if (height[y] < height[x]) {
father[y] = x;
} else {
father[y] = x;
height[x]++;
}
}
}
int Kruskal(int m, int n) { //克鲁斯卡尔算法求最小生成树
Initial(m);
sort(edge.begin(), edge.begin() + n); //边按权值排序
int sum = 0, //边权和（总长度）
count = 0; //边数
for (int i = 0; i < n; i++) {
Edge current = edge[i];
if (Find(current.from) != Find(current.to)) {
Union(current.from, current.to);
sum += current.length; //边权累加
count++; //统计边数
}
}
//若边数太少不足以构成连通树（原图也一定不是连通图），则返回错误信息（-1）；
//否则返回最小总长度（sum）
return count == m - 1 ? sum : -1;
}
int main() {
int n, m;
while (cin >> n >> m && n) {
for (int i = 0; i < n; i++) {
cin >> edge[i].from >> edge[i].to >> edge[i].length;
}
int result = Kruskal(m, n);
result == -1 ? cout << '?' << endl : cout << result << endl;
}
return 0;
}
编辑于 2024-03-02 14:51:04
回复(0)
//这道题算是比较常规的题了，采用kruskal算法并利用并查集思想求最小生成树
#include "stdio.h"
#include "queue"
using namespace std;
struct Edge{
int villageS;//源端的村庄编号
int villageT;//目的端的村庄编号
int weight;
};
int N,M;//N为道路数目，M为村庄数目
priority_queue<Edge> myPQueue;
int Father[101];//并查集得根存储
bool operator < (Edge lhs,Edge rhs){
return lhs.weight > rhs.weight;
}
void Init(){
for (int i = 1; i <= M; ++i) {
Father[i] = i;
}
while (!myPQueue.empty())
myPQueue.pop();
}
int find(int x){
if (Father[x] != x){
Father[x] = find(Father[x]);
}
return Father[x];
}
int kruskal(){
int sum = 0;//存储路径总长
while (!myPQueue.empty()){
Edge edge = myPQueue.top();
myPQueue.pop();
int villageS = edge.villageS,villageT = edge.villageT;
if (find(villageS) != find(villageT)){
Father[find(villageT)] = find(villageS);//Union操作
sum += edge.weight;
}
}
int count = 0;
for (int i = 1; i <= M; ++i) {
if (Father[i] == i)
++count;
}
if (count != 1)//有多个连通分支，无法形成最小生成树
return -1;
else
return sum;
}
int main(){
while (scanf("%d",&N)!=EOF){
if (N == 0)
break;
scanf("%d",&M);
Init();//对邻接矩阵和并查集进行初始化
int villageS,villageT,weight;
for (int i = 1; i <= N; ++i) {//道路入优先队列
scanf("%d%d%d",&villageS,&villageT,&weight);
Edge edge;edge.villageS = villageS;
edge.villageT = villageT;edge.weight = weight;
myPQueue.push(edge);
}
int sum = kruskal();
if (sum != -1)
printf("%d\n",sum);
else
printf("?\n");
}
}
发表于 2023-03-26 19:13:52
回复(0)
Kruskal + 堆优化
使用并查集和小顶堆（优先队列）
'''
#include <bits/stdc++.h>
using namespace std;
int fa[101] = {0};
int findFa(int x) {
return x == fa[x] ? x : fa[x] = findFa(fa[x]);
}
void unite(int x, int y) {
int r1 = findFa(x);
int r2 = findFa(y);
fa[r1] = r2;
}
struct Edge {
int u;
int v;
int w;
bool friend operator <(const Edge& e1,const Edge& e2) {
return e1.w > e2.w;
}
};
int main() {
int N, M;
while (cin >> N) {
if (N == 0) break;
cin >> M;
for (int i = 1; i <= M; i++) {
fa[i] = i;
}
priority_queue<Edge, vector<Edge> > pq;
int i = 0;
while (i++ < N) {
Edge e;
cin >> e.u >> e.v >> e.w;
pq.push(e);
}
i = 0;
int ans = 0;
while (!pq.empty()) {
auto e1 = pq.top();
pq.pop();
if (findFa(e1.u) != findFa(e1.v)) {
unite(e1.u, e1.v);
ans += e1.w;
}
}
//判断图是否连通
int f = findFa(1);
bool flag = true;
for (int i = 2; i <= M; i++) {
if (findFa(i) != f) {
flag = false;
}
}
if (flag) {
cout << ans << endl;
} else cout << "?" << endl;
}
}
// 64 位输出请用 printf("%lld")
'''
发表于 2023-02-19 21:51:41
回复(0)
问题信息
难度：
60条回答
51收藏
7174浏览
通过挑战的用户
查看代码-
2023-03-10 18:42:54
-
2023-03-10 17:04:42
-
2023-03-09 10:08:40 -
2023-03-08 11:50:45 -
2023-02-05 01:52:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
