精华内容
下载资源
问答
  • 继续畅通工程

    2017-09-24 16:39:20
    题目网址:继续畅通工程 题目分析:这个比之前的还是畅通工程相比多了一个就是有的路已经修好了,无需在花销,所以我们比之前的做法只是多判断一点,如果已经修过了,那么我们就把这条路的花销修改为0,其他不变。#...

    题目网址:继续畅通工程

    题目分析:这个比之前的还是畅通工程相比多了一个就是有的路已经修好了,无需在花销,所以我们比之前的做法只是多判断一点,如果已经修过了,那么我们就把这条路的花销修改为0,其他不变。

    #include<iostream>
    #include<algorithm>
    using namespace std;
    int parent[102];
    int findroot(int x)
    {
    	if (parent[x] != x)
    		parent[x] = findroot(parent[x]);
    	return parent[x];
    }
    struct edge{
    	int a, b;
    	int cost;
    	bool operator < (const edge&a)const{
    		return cost < a.cost;
    	}
    }e[6000];
    int main()
    {
    	int n;
    	while (cin >> n&&n)
    	{
    		for (int i = 1; i <= n; i++)
    		{
    			parent[i] = i;
    		}
    		for (int i = 0; i < (n - 1)*n / 2; i++)
    		{
    			int state;
    			cin >> e[i].a >> e[i].b >> e[i].cost >> state;
    			if (state == 1)//若是已经修好了,那么直接将cost修改为0
    				e[i].cost = 0;
    		}
    		sort(e, e + (n - 1)*n / 2);
    		int ans = 0;
    		for (int i = 0; i < (n - 1)*n / 2; i++)
    		{
    			int a = findroot(e[i].a);
    			int b = findroot(e[i].b);
    			if (a != b)
    			{
    				parent[a] = b;
    				ans += e[i].cost;
    			}
    		}
    		cout << ans << endl;
    	}
    	return 0;
    }

    展开全文
  • 继续畅通工程 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 29927 Accepted Submission(s): 12581 Problem Description 省政府“畅通工程”的目标是使...

    继续畅通工程
    Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 29927 Accepted Submission(s): 12581

    Problem Description
    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。

    Input
    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

    当N为0时输入结束。

    Output
    每个测试用例的输出占一行,输出全省畅通需要的最低成本。

    Sample Input
    3
    1 2 1 0
    1 3 2 0
    2 3 4 0
    3
    1 2 1 0
    1 3 2 0
    2 3 4 1
    3
    1 2 1 0
    1 3 2 1
    2 3 4 1
    0

    Sample Output
    3
    1
    0


    实现代码如下, 用的克鲁斯卡尔算法,代码运行超时,不知为什么,感觉已经不能再优化了。如果哪位大佬用java AC了,请告知,万分感谢!!


    补:当天晚上解决了,原来一直超时,是因为java的Scanner读取的速度太慢,导致数据量太大时,造成超时,后来找到了一种更快的读取方法,然后AC了。


    
    import java.io.*;
    import java.util.*;
    public class Main{
    	public static int pre[];
    	public static int m,n;
    	public static Edge []edges;
    	static class Edge implements Comparable<Edge>{
    		public int u,v,w;
    		public int compareTo(Edge e){
    			return this.w-e.w;
    		}
    
    	}
    	public static int find(int x){
    		int r = x;
    		while(pre[r]!=r) r=pre[r];
    		int j=x,tmp;
    		while(j!=r)
    		{
    			tmp = pre[j];
    			pre[j] = r;
    			j = tmp;
    		}
    		return r;
    	}
    	public static int kruskal(){
    		int tot=1,sum=0;
    		for(int i=1;i<=m&&tot<=n;i++)   //i代表边,toto代表已经连接的村庄数量
    		{
    
    			int a = find(edges[i].u);
    			int b = find(edges[i].v);
    			if(a!=b){
    				sum+=edges[i].w;
    				pre[a] = b;
    				tot++;
    			}
    		}
    		return sum;
    	}
    	//解决javaIO读取过慢的方法,利用该类读取输入数据,不要用Scanner!!!
    	static class InputReader {
    		public BufferedReader reader;
    		public StringTokenizer tokenizer;
    
    		public InputReader(InputStream stream) {
    			reader = new BufferedReader(new InputStreamReader(stream), 32768);
    			tokenizer = null;
    		}
    
    		public String next() {
    			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
    				try {
    					tokenizer = new StringTokenizer(reader.readLine());
    				} catch (IOException e) {
    					throw new RuntimeException(e);
    				}
    			}
    			return tokenizer.nextToken();
    		}
    
    		public int nextInt() {
    			return Integer.parseInt(next());
    		}
    
    	}
    	public static  void main(String []args) {
    		InputReader sc = new InputReader(System.in);  //用它来代替Scanner。
    		while(true){
    			n = sc.nextInt();
    			m = n*(n-1)/2;
    
    			if(n==0) break;
    			pre = new int[n+1];
    			for(int i=1;i<=n;i++)
    				pre[i] = i;
    
    			edges = new Edge[m+1];
    			for(int i=1;i<=m;i++)
    				edges[i] = new Edge();
    			int c;
    			for(int i=1;i<=m;i++)
    			{
    				edges[i].u = sc.nextInt();
    				edges[i].v = sc.nextInt();
    				edges[i].w = sc.nextInt();
    				c = sc.nextInt();
    				if(c==1) edges[i].w = 0;
    			}
    			Arrays.sort(edges,1,edges.length);
    			System.out.println(kruskal());
    		}
    	}
    }
    
    
    展开全文
  • 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否...
    题目描述
        省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。
    输入描述:
        测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。
    
        当N为0时输入结束。
    输出描述:
        每个测试用例的输出占一行,输出全省畅通需要的最低成本。
    示例1
    输入
    复制
    3
    1 2 1 0
    1 3 2 0
    2 3 4 0
    3
    1 2 1 0
    1 3 2 0
    2 3 4 1
    3
    1 2 1 0
    1 3 2 1
    2 3 4 1
    0
    输出
    复制
    3
    1
    0
    
    import java.util.*;
    import java.io.*;
    import java.text.* ;
    import java.math.*;
    public class Main
    {
    	static int[] father;
    	static ArrayList<Edge> edges;
    	static int n;
        public static void main(String[] args){
        	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	try {
        		String str;
        		while((str = br.readLine()) != null) {
        			n = Integer.parseInt(str);
        			if(n == 0) break;
        			int eNum = n*(n-1)/2;
        			edges = new ArrayList<>();
        			for(int i = 0; i < eNum; i++) {
        				String[] parts = br.readLine().split(" ");
        				int x = Integer.parseInt(parts[0]);
        				int y = Integer.parseInt(parts[1]);
        				int z = Integer.parseInt(parts[2]);
        				if(parts[3].contentEquals("1")) z = 0;
        				edges.add(new Edge(x, y, z));
        			}
        			father = new int[n+1];
        			System.out.println(Kruskal(eNum));
        		}
        	} catch(IOException e) {
        		e.printStackTrace();
        	}
        }
        public static int Kruskal(int eNum) {
    		initial();
    		Collections.sort(edges, new Comparator<Edge>() {
    			public int compare(Edge o1, Edge o2) {
    				return o1.length - o2.length;
    			}
    		});
    		int sum = 0;
    		for(int i = 0; i < eNum; i++) {
    			Edge tmp = edges.get(i);
    			if(find(tmp.from) != find(tmp.to)) {
    				union(tmp.from, tmp.to);
    				sum += tmp.length;
    			}
    		}
    		return sum;
        }
        public static void initial() {
        	for(int i = 1; i <= n; i++) father[i] = i;
        }
        public static int find(int x) {
        	if(x != father[x]) father[x] = find(father[x]);
        	return father[x];
        }
        public static void union(int x, int y) {
        	x = find(x);
        	y = find(y);
        	if(x != y) {
        		father[x] = y;
        	}
        }
    }
    class Edge{
    	int from;
    	int to;
    	int length;
    	Edge(int x, int y, int z){
    		from = x;
    		to = y;
    		length = z;
    	}
    }
    
    
    
    展开全文
  • hdu-继续畅通工程

    2019-09-06 13:15:54
    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经...

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经修通的状态。现请你编写程序,计算出全省畅通需要的最低成本。
    Input
    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1< N < 100 );随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。

    当N为0时输入结束。
    Output
    每个测试用例的输出占一行,输出全省畅通需要的最低成本。
    Sample Input

    3
    1 2 1 0
    1 3 2 0
    2 3 4 0
    3
    1 2 1 0
    1 3 2 0
    2 3 4 1
    3
    1 2 1 0
    1 3 2 1
    2 3 4 1
    0
    

    Sample Output

    3
    1
    0
    

    代码分析:注意输入和输出用C语言那一套,别C++,要不TLE
    AC代码:

    //hdu1879-继续畅通工程 
    #include<bits/stdc++.h>
    using namespace std;
    int ba[101];
    void init(int n){
       for(int i=1;i<=n;i++)
       	ba[i]=i;	
    } 
    int fson(int a){
       while(a!=ba[a])
       	a=ba[a];
       return a;
    } 
    int uson(int a,int b){
       int fa=fson(a);
       int fb=fson(b);
       if(fa!=fb){
       	ba[fa]=fb;
       	return true;
       } 
       return false;
    }
    //边开始
    struct Edge{
       int a,b,c,d;
       bool operator< (const Edge &v)const{
       	return c>v.c;//从小到大进行排序,小的优先权更大 
       }
    }; 
    int main(){
       //freopen("4.txt","r",stdin);
       int n;
       while(~scanf("%d",&n)&&n){
       	init(n);
       	priority_queue<Edge>q;
       	Edge e;
       	for(int i=1;i<=n*(n-1)/2;i++){
       		scanf("%d%d%d%d",&e.a,&e.b,&e.c,&e.d);
       		if(e.d==1) uson(e.a,e.b);//判别此时的状态并联边 
       		else q.push(e);	
       	}
       	int res=0;
       	int is=0;
       	while(!q.empty()){
       		e=q.top();
       		q.pop();
       		if(uson(e.a,e.b)){
       				is++;
       				if(is==n) break;
       				res+=e.c;		
       		}
       	}
       	printf("%d\n",res);
       }
       return 0;
    }
    
    展开全文
  • 问题 D: 继续畅通工程 时间限制:1 Sec内存限制:32 MB 提交:216解决:109 [提交][状态][讨论版][命题人:外部导入] 题目描述 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的...
  • 继续畅通工程Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 26913 Accepted Submission(s): 11362Problem Description 省政府“畅通工程”的目标是使...
  • hdoj1879继续畅通工程

    2015-08-11 11:21:18
    继续畅通工程Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 17816 Accepted Submission(s): 7669Problem Description 省政府“畅通工程”的目标是使...
  • 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经...
  • 题目链接 题目分析 最小生成树问题; 解题思路 ...用Kruskal算法即可,把修通道路(边)的权值(距离)令为0即可;...*@ACM: HDU-1879 继续畅通工程 *@Time: 18/9/13 *@IDE: VSCode + clang++ ********...
  • 1 已经修建了 公路 就是权值 是0
  • 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。现得到城镇道路统计表,表中列出了任意两城镇间修建道路的费用,以及该道路是否已经...
  • hdu--1879继续畅通工程

    2016-07-18 16:06:28
    对于kruskal还不太掌握,,基本上是照着别人模板打的代码,还要继续加强,,prim的话,还好,,下面是两种AC过得方法: kruskal: #include #include #include #include #define N 105 using namespace std; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,204
精华内容 1,281
关键字:

继续畅通工程