KimJennie's blog

By KimJennie, history, 7 weeks ago, In English

Hello, Codeforces!

I have to find MST with this algorithm, but got WA. Can you please help me? I would really appreciate that.

My submission: https://pastebin.com/P4nGmhRM Problem: https://codeforces.com/gym/100088/attachments It's in russian, but the idea is:

There are n cities. The mayor of city wants to build a roads, so you were able to visit one city from any another. And there are given n (x; y) coordinates, and you have to find minimum spanning tree. Obviously, in graph i and j (1 <= i,j <= n) are vertices, and the weight of edge is (x[i]-x[j])^2 + (y[i]-y[j])^2.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Edit the blog with the problem link and, if possible, your submission.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sure, sorry about that!

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ok, are you sure that you are solving the right problem? I don't see you using the formula (x[i]-x[j])^2 + (y[i]-y[j])^2 anywhere...

      Have you ever solved any minimum spanning tree problem before? If not, I recommend that you try this problem first: https://cses.fi/problemset/task/1675

      For your problem, you only need to:

      1. Create a graph G with N nodes.

      2. Read X[U] and Y[U] for each node U from 0 to N — 1.

      3. For each node U, for each other node V create an edge between U and V in G with a weight of square root of (X[U]-X[V])^2 + (Y[U]-Y[V])^2

      4. Run Prim's algorithm

      Furthermore, you need to do input/output from files. One (ugly) way to do it is to add this lines:

      void solve(){
      	ifstream cin("unionday.in");
      	ofstream cout("unionday.out");	
      	
      	// your solution 
      	
      	cin.close();
      	cout.close();
      }
      
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by KimJennie (previous revision, new revision, compare).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by KimJennie (previous revision, new revision, compare).