Page 1 of 1
11631 - Dark roads. WA!!!
Posted: Tue Dec 25, 2012 8:42 pm
by sith
Hi,
I believe I chose right approach, but I got WA,
Could anybody help with advice or provide some input
Code: Select all
import java.io.*;
import java.util.Arrays;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
try {
Scanner scanner = new Scanner(reader);
while (scanner.hasNextInt()) {
int m = scanner.nextInt();
int n = scanner.nextInt();
Distance[] distances = new Distance[n];
int sum = 0;
for (int i = 0; i < n; i++) {
int from = scanner.nextInt();
int to = scanner.nextInt();
int distance = scanner.nextInt();
distances[i] = new Distance(from, to, distance);
sum += distance;
}
WeightedQuickUnion quickUnion = new WeightedQuickUnion(m + 1);
Arrays.sort(distances);
int totalDistance = 0;
for (Distance distance : distances) {
if (quickUnion.find(distance.from, distance.to)) {
continue;
}
totalDistance += distance.distance;
quickUnion.union(distance.from, distance.to);
}
writer.write((sum-totalDistance) + "\n");
}
writer.flush();
} catch (IOException e) {
e.printStackTrace();
}
}
static class Distance implements Comparable<Distance> {
int from, to, distance;
Distance(int from, int to, int distance) {
this.from = from;
this.to = to;
this.distance = distance;
}
@Override
public int compareTo(Distance o) {
int distanceDiff = distance - o.distance;
if (distanceDiff != 0) {
return distanceDiff;
}
int fromDiff = from - o.from;
if (fromDiff != 0) {
return fromDiff;
}
return to - o.to;
}
}
static class QuickUnion extends FindUnion {
public QuickUnion(int n) {
super(n);
}
@Override
public void union(int p, int q) {
int i = getRoot(p);
int j = getRoot(q);
array[i] = j;
groups--;
}
@Override
public boolean find(int a, int b) {
return getRoot(a) == getRoot(b);
}
protected int getRoot(int a) {
if (a == array[a]) {
return a;
}
return getRoot(array[a]);
}
}
static abstract class FindUnion {
protected final int[] array;
protected int groups;
protected FindUnion(int n) {
this.array = new int[n];
for (int i = 1; i < array.length; i++) {
array[i] = i;
}
groups = n;
}
public abstract void union(int p, int q);
public abstract boolean find(int p, int q);
public int getGroups() {
return groups;
}
}
static class WeightedQuickUnion extends QuickUnion {
final int[] size;
public WeightedQuickUnion(int n) {
super(n);
size = new int[n];
for (int i = 0; i < size.length; i++) {
size[i] = 1;
}
}
@Override
public void union(int p, int q) {
int i = getRoot(p);
int j = getRoot(q);
if (size[i] < size[j]) {
array[i] = j;
size[j] += size[i];
} else {
array[j] = i;
size[i] += size[j];
}
groups--;
}
}
}
Re: 11631 - Dark roads. WA!!!
Posted: Wed Dec 26, 2012 11:29 am
by brianfry713
Doesn't match the sample I/O.
11631 - Dark roads
Posted: Sat Dec 29, 2012 12:45 pm
by laituanksa245
I kept getting TLE on this problem.
Any suggestion to speed up my program ?
I used Kruskal algorithm.
Re: 11631 - Dark roads TLE
Posted: Sun Dec 30, 2012 9:09 am
by brianfry713
Add union find to Kruskal's algorithm.
Re: 11631 - Dark roads TLE
Posted: Sun Jan 06, 2013 6:12 am
by laituanksa245
Thanks very much. Got AC
Re: 11631 - Dark roads TLE
Posted: Tue Dec 10, 2013 12:39 pm
by Saminur Islam
I think this is a simple mst problem I use prim algorithm but getting submission error ..... plz help me to find out the problem in my code
Code: Select all
#include<iostream>
#include<vector>
#include<map>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<list>
#include<utility>
#include<fstream>
#include<cmath>
using namespace std;
int M,N;
vector<pair<int,int> >node[200001];
bool visited[200001];
int dist[200001];
int parent[200001];
int minkey()
{
int i,min;
for(i=0;i<M;i++)
{
if(visited[i]==false)
{
min=i;
break;
}
}
for(i=0;i<M;i++)
{
if(dist[min]>dist[i] && visited[i]==false) min=i;
}
return min;
}
void prim()
{
int i,j;
int k,distance;
int value;
memset(visited,false,sizeof visited);
memset(parent,-1,sizeof parent);
for(int i=0;i<M;i++)dist[i]=1000000;
dist[0]=0;
i=0;
for(i=0;i<M;i++)
{
int min= minkey();
visited[min]=true;
//cout<<min<<" "<<dist[min]<<endl;
for(j=0;j<node[min].size();j++)
{
pair<int,int>p;
p=node[min][j];
value=p.first;
distance=p.second;
if(visited[value]==false && distance<dist[value])
{
dist[value]=distance;
parent[value]=min;
}
}
}
}
int main()
{
//freopen("i.txt","r",stdin);
int i,j,k;
int totalcost2;
int value1,value2,weight;
while(scanf("%d %d",&M,&N)==2)
{
if(M==0&&N==0) break;
totalcost2=0;
for(i=0;i<N;i++)
{
scanf("%d %d %d",&value1,&value2,&weight);
totalcost2=totalcost2+weight;
node[value1].push_back(make_pair(value2,weight));
node[value2].push_back(make_pair(value1,weight));
}
//cout<<totalcost2<<endl;
prim();
int totalCost=0;
for(i=M-1;i>0;i--)
{
//cout<<dist[i]<<"\n";
totalCost+=dist[i];
}
//cout<<totalCost<<endl;
cout<<totalcost2-totalCost<<endl;
}
return 0;
}
Re: 11631 - Dark roads TLE
Posted: Tue Dec 10, 2013 10:06 pm
by brianfry713
Your code is now getting wrong answer.
Try input:
Output should be 0
Re: 11631 - Dark roads
Posted: Sat Nov 15, 2014 7:34 pm
by Karkat_Vantas
My code returns a compiler error. In my IDE though, it shows no errors, and no warnings except "Unchecked cast from Bag[] to Bag<Main.Edge>[]". The code runs fine on my machine. What are some reasons why the judge would find a different compiling error?
My code also contains different classes (I'm guessing that this is the reason for the error.)
Is
Code: Select all
public class Main{
public static void main(String[] args)
{}
public static class A
{}
public static class B
{}
}
the way to arrange multiple classes in the same file?
Re: 11631 - Dark roads
Posted: Mon Nov 17, 2014 11:06 pm
by brianfry713
Check My Submissions for your CE.
Re: 11631 - Dark roads
Posted: Mon Jun 08, 2015 11:20 am
by dreamd_hacker
Hi, I got TLE three times. Here is my code.
Code: Select all
#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#define DEBUG 0
using namespace std;
struct edge {
int f, t, w;
bool operator <(const edge &other) const {
return this-> w < other.w;
}
};
int find_set(int *s, int v){
if(s[v] == v)
return v;
else
return find_set(s, s[v]);
}
int main() {
if (DEBUG)
freopen("in.txt", "r", stdin);
int n, m, f, t, w, par1, par2, total, min_sum, select;
int arr_set[200010];
while (1) {
scanf("%d%d", &n, &m);
if (n == 0 && m == 0)
break;
total = 0;
vector<edge> q;
for(int i = 0; i < m; ++i){
scanf("%d%d%d", &f, &t, &w);
edge e = {f, t, w};
q.push_back(e);
total += w;
arr_set[i] = i;
}
arr_set[n] = n;
if(n == m + 1){
printf("0\n");
continue;
}
min_sum = 0;
select = n - 1;
sort(q.begin(), q.end());
for(int i = 0; (i < m) && select; ++i){
edge t = q[i];
par1 = find_set(arr_set, t.f);
par2 = find_set(arr_set, t.t);
if(par1 != par2){
min_sum += t.w;
arr_set[par1] = par2;
select--;
}
}
printf("%d\n", total - min_sum);
}
return 0;
}
Re: 11631 - Dark roads
Posted: Fri Nov 13, 2015 8:26 pm
by martijnn2008
I get a Run Error, can't find out why. Please help.
Code: Select all
import java.util.*;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
while(n != 0 && m != 0) {
solve(n, m, sc);
n = sc.nextInt();
m = sc.nextInt();
}
}
static class Edge implements Comparable<Edge> {
int a, b, w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
public int compareTo(Edge e) {
return this.w - e.w;
}
public String toString() {
return "[(" + a + ", " + b + ") : " + w + "]";
}
}
static void solve(int n, int m, Scanner sc) {
Edge[] edges = new Edge[m];
Edge[] tree = new Edge[n - 1];
int total = 0;
for (int i = 0; i < m; i++) {
edges[i] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
total += edges[i].w;
}
parent = new int[n];
rank = new int[n];
int s = 0;
Arrays.sort(edges);
for (int i = 0; i < n; i++) { parent[i] = i; }
for (Edge e : edges) { if (join(e.a, e.b)) { tree[s++] = e; }
if (s >= n -1) break;}
int output = 0;
for (Edge e : tree) {
output += e.w;
}
System.out.println(total - output);
}
static int[] parent;
static int[] rank;
static boolean join(int x, int y) {
/*
int fx = find(x);
int fy = find(y);
if(rank[x] < rank[y])
parent[x] = fy;
else {
parent[y] = fx;
if (rank[x] != rank[y]) {
rank[x]++;
}
}
return fx != fy;
*/
int xrt = find(x);
int yrt = find(y);
if (rank[xrt] > rank[yrt]) {
parent[yrt] = xrt;
} else {
parent[xrt] = yrt;
if (xrt != yrt) {
rank[xrt]++;
}
}
return xrt != yrt;
}
static int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
}
Re: 11631 - Dark roads
Posted: Wed Nov 25, 2015 2:51 am
by brianfry713
use class Main