11733 - Airports

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

11733 - Airports

Post by MRH » Sun Jan 10, 2010 7:15 am

I can not find my wrong in simple MST problem

Please give me some I/O

Thanks in advance

robot
New poster
Posts: 29
Joined: Sun May 24, 2009 8:39 pm

Re: 11733 - Airports

Post by robot » Fri Jan 15, 2010 5:06 pm

Hi try this input checking.. its help u i think..
4
3 2 120
1 2 20
2 3 120
5 2 100
1 3 20
3 5 100
5 2 120
1 3 20
3 5 100
4 3 10
1 2 5
2 3 15
3 4 0
Case #1: 260 2
Case #2: 420 4
Case #3: 480 3
Case #4: 25 2
ASU(SUST)
"Teme jabo bole to Shopno deki ni"

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Help in understanding 11733 - Airports

Post by anis_cuet016 » Fri Jul 16, 2010 3:58 pm

Hi,

i m having difficulty in understanding the theme of this problem, at first i thought it can b solved by using kruskal and union find... but the sample i/o given below is not fitting to my logic...

5 2 100
1 3 20
3 5 100

here there are link between 1 -> 3 -> 5 so i consider it whole as 1, there are two more locations 2 and 4 so all together it became 1 + 1 + 1 = 3 airports...... but how the correct number of airports became 4 ??? please clarify me ....

sory 4 my bad English .....

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11733 - Airports

Post by zobayer » Wed Jul 28, 2010 12:17 pm

Well, indeed this can be solved by kruskal, but you have misunderstood the problem. Problem clearly said
The government now needs your help to decide on the cheapest way of ensuring that every location has access to an airport. The aim is to make airport access as easy as possible, so if there are several ways of getting the minimal cost, choose the one that has the most airports.
So, it you look closely, when you build the MST, you have larger edges at the end. Say, the last edge cost is A and airport building cost is B where A > B, so clearly, you would like not to build this road, rather, you will build an airport more. As you are putting just one airport in each tree of the minimum spanning forest, it is clear from the tree property that, if you remove an edge from it, it will be split into two trees.... So, previously you built one airport for the tree, and if the above property holds, you would cut this road, and then you have to build one more airport.

I think now you understand the problem.
You should not always say what you know, but you should always know what you say.

anis_cuet016
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

Re: 11733 - Airports

Post by anis_cuet016 » Thu Jul 29, 2010 10:33 pm

Thankz a lot zobayer ......... what kind of shit i m, didnt give proper concentration in that para, i think i should b more carefull....... nwayz just added this line in my code and got accepted nthing else changed :D

Code: Select all

if(G[i].wt < weight)
// blah blah blah ......
Hey buddy thankz again, was stuck in this problem for more then two week ..........
Khodahafiz
Anis

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11733 - Airports

Post by Shafaet_du » Wed Aug 17, 2011 2:18 pm

try this:

Code: Select all

1
8 7 10
1 3 5
1 2 8
2 4 6
3 4 10
4 5 30
5 6 6
5 7 15

Code: Select all

Case #1: 65 4

spewer
New poster
Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

Re: 11733 - Airports

Post by spewer » Tue Dec 20, 2011 4:14 pm

Hi help me pls i cannot find the WA
tell pls if i misunderstood the problem or gimme a critical Input pls

Code: Select all

#include "stdafx.h"
#include<string>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<utility>
#include<queue>

using namespace std;

vector<int> pset(100000);
int findSet(int i) {
   return (pset[i] == i) ? i :   
   (pset[i] = findSet(pset[i]));
}
void initSet(int _size) {
   pset.clear();   
   pset.resize(_size);
   for (int i=0; i<_size;i++) 
      pset[i]=i;
}
void unionSet(int i, int j) 
{
   pset[findSet(i)]=findSet(j);
}
bool isSameSet(int i, int j) {
   return findSet(i)==findSet(j);
}

typedef pair<int,pair<int,int> > iii;
priority_queue < iii , vector < iii > , greater < iii > > edgeList;
int kruskal(int n) { // n = #vertices, m= #aristas, retorna valor MST.
   int cont = 0; double mst_cost =  0;   initSet(n);
   while(!edgeList.empty() && cont < n-1)    {
      iii front = edgeList.top(); edgeList.pop();
      if ( !isSameSet(front.second.first,front.second.second) ) // nodo a y b
      {
         cont++; 
		 mst_cost += front.first; 
         unionSet(front.second.first,front.second.second);
      }
   }
   return mst_cost;
}


int casos,vertices,aristas,aero;
int ori,des,pes;
int main()
{
	freopen("in.txt","rt",stdin);
	freopen("out.txt","wt",stdout);
	scanf("%d",&casos);
	for(int c=0;c<casos;c++)
	{
		while(!edgeList.empty())
			edgeList.pop();
		scanf("%d %d %d",&vertices,&aristas,&aero);// aero= costo por creaeaeropuerto
		for(int a=0;a<aristas;a++)
		{
			iii coso;
			scanf("%d %d %d",&ori,&des,&pes);
			if(pes<aero)
			{
				coso.first=pes;coso.second.first=ori-1;coso.second.second=des-1;//ORIgen DEStino PESo
				edgeList.push(coso);
			}
		}
		int rpta=kruskal(vertices);
		for(int i=0;i<vertices;i++)
			findSet(i);
		int buliano=0;
		for(int i=0;i<vertices;i++)
		for(int j=0;j<i;j++)
		{
			if(pset[i]==pset[j])
			{
				buliano++;
				break;
			}
		}
		rpta+=(aero*(vertices-buliano));//vertices - buliano = cantidad de aeropuertos
		printf("Case #%d: %d %d\n",c+1,rpta,vertices-buliano);
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11733 - Airports

Post by brianfry713 » Sat Jan 14, 2012 12:28 am

remove the lines:
#include "stdafx.h"
freopen("in.txt","rt",stdin);
freopen("out.txt","wt",stdout);
Check input and AC output for thousands of problems on uDebug!

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 11733 - Airports

Post by SyFy » Fri Jun 29, 2012 4:50 pm

OMG! :lol: Solved it with JAVA in 0.892.

But its really frustrating... had this code first:

Code: Select all

if(i != t - 1) 
out.printf("Case #%d: %d %d\n", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());
else out.printf("Case #%d: %d %d", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());
Got WAs...

changed to:

Code: Select all

//if(i != t - 1) 
out.printf("Case #%d: %d %d\n", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());
//else out.printf("Case #%d: %d %d", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());
Got AC...

but problem statement clearly says:
Your program should output exactly T lines, one for each case.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11733 - Airports

Post by brianfry713 » Sat Jun 30, 2012 12:13 am

You should print a newline at the end of the last line on most problems.
Check input and AC output for thousands of problems on uDebug!

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 11733 - Airports

Post by SyFy » Sat Jun 30, 2012 12:51 am

does it matter for instance if I will print 2 newlines ? and how can I know that when I am getting WAs in JAVA its not PE ? :roll:
brianfry713 wrote:You should print a newline at the end of the last line on most problems.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11733 - Airports

Post by brianfry713 » Mon Jul 02, 2012 10:30 pm

Yes it matters how many newlines you print. Don't count on ever getting PE. On a lot of problems extra or missing whitespace will give you WA.
Check input and AC output for thousands of problems on uDebug!

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir
Contact:

Re: 11733 - Airports

Post by SyFy » Mon Jul 02, 2012 11:42 pm

yep. but its very sad when you get WA and dont know whats wrong: algo or output.
brianfry713 wrote:Yes it matters how many newlines you print. Don't count on ever getting PE. On a lot of problems extra or missing whitespace will give you WA.

Diaa.Abobaraka
New poster
Posts: 3
Joined: Mon Feb 11, 2013 5:44 pm

Re: 11733 - Airports

Post by Diaa.Abobaraka » Sat May 24, 2014 6:43 pm

Gives me Time Limit ......any help please ?

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Airports {
	static class Edge implements Comparable<Edge> {
		int firstNode, secondNode;
		int weight;

		public Edge(int firstNode1, int secondNode1, int d) {
			firstNode = firstNode1;
			secondNode = secondNode1;
			weight = d;
		}

		@Override
		public int compareTo(Edge edgeObject) {
			if (edgeObject.weight < weight) {
				return 1;
			} else if (edgeObject.weight == weight) {
				return 0;
			} else {
				return -1;
			}

		}
	}

	static int[] parentList;
	static ArrayList<Edge> edgeList;

	static int findParent(int i) {
		if (i == parentList[i])
			return i;
		return parentList[i] = findParent(parentList[i]);
	}

	static void connect(int i, int j) {
		parentList[findParent(i)] = parentList[findParent(j)];
	}

	static boolean isConnected(int i, int j) {
		if (findParent(i) == findParent(j))
			return true;
		return false;
	}

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		StringBuilder sb = new StringBuilder();
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n, m, airportCost;
		int first, second, len;
		int sum, cnt;
		int tc = Integer.parseInt(bf.readLine());
		for (int t = 1; t <= tc; t++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			airportCost = Integer.parseInt(st.nextToken());
			parentList = new int[n];
			for (int i = 0; i < n; i++)
				parentList[i] = i;
			edgeList = new ArrayList<>();
			int xx = m;
			for (int i = 0; i < xx; i++) {
				StringTokenizer st1 = new StringTokenizer(bf.readLine());
				first = Integer.parseInt(st1.nextToken());
				second = Integer.parseInt(st1.nextToken());
				len = Integer.parseInt(st1.nextToken());
				if (len < airportCost) {
					edgeList.add(new Edge(first - 1, second - 1, len));
				} else {
					m--;
				}

			}
			Collections.sort(edgeList);
			cnt = n;
			sum = 0;
			for (int i = 0; i < m && cnt > 1; i++) {
				first = edgeList.get(i).firstNode;
				second = edgeList.get(i).secondNode;
				len = edgeList.get(i).weight;
				if (!isConnected(first, second)) {
					cnt--;
					sum += len;
					connect(first, second);
				}
			}
			sum += cnt * airportCost;
			sb.append("Case #" + t + ": " + sum + " " + cnt + "\n");

		}
		System.out.println(sb);

	}

}

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 11733 - Airports

Post by lbv » Sun May 25, 2014 12:03 am

Diaa.Abobaraka wrote:Gives me Time Limit ......any help please ?
This problem has a very tight time limit and a large amount of input, so a really efficient method to read data is needed. I'm not sure if StringTokenizer cuts it.

I used to write in Java for competitions a few years ago, so I went back and looked at the old I/O routines that I used, adapted them to your code, and got AC in 0.809s.

For reference, here's the relevant reader class:

Code: Select all

    class $R {
        InputStream in; byte b; byte[] buf; int bi, bz;
        $R(InputStream I) { in=I; buf=new byte[65536]; bi=bz=0; read(); }
        boolean hasNext() { skip(); return b >= 0; }
        void skip() { while (b >= 0 && b <= 32) read(); }
        String next() {
            StringBuilder sb = new StringBuilder();
            for (skip(); b > 32; read()) sb.append((char)b);
            return sb.length() == 0 ? null : sb.toString(); }
        String nextLine() {
            StringBuilder sb = new StringBuilder();
            for (; b != 10 && b != 13; read()) sb.append((char)b);
            while (b == 10 || b == 13) read();
            return sb.toString(); }
        int nextInt() {
            int ival = 0; boolean isgn = false;
            skip(); if (b == '-') { isgn = true; read(); }
            for (; b > 32; read()) ival = ival*10 + b-48;
            return isgn ? -ival : ival; }
        void read() {
            if (bi==bz) {
                bi=0; try { bz=in.read(buf); } catch(Exception e) { bz=-1; } }
            b = bz == -1 ? -1 : buf[bi++];  }
    }
Using this class goes something like this:

Code: Select all

$R myReader = new $R(System.in);

// whenever you need to read an integer
int foo = myReader.nextInt();
Also, notice that you should not print an extra blank line at the end of the output.

Post Reply

Return to “Volume 117 (11700-11799)”