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.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.
Code: Select all
if(G[i].wt < weight)
// blah blah blah ......
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 4Code: 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;
}
Solved it with JAVA in 0.892.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());
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());
Your program should output exactly T lines, one for each case.
brianfry713 wrote:You should print a newline at the end of the last line on most problems.
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.
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);
}
}
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.Diaa.Abobaraka wrote:Gives me Time Limit ......any help please ?
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++]; }
}
Code: Select all
$R myReader = new $R(System.in);
// whenever you need to read an integer
int foo = myReader.nextInt();