mst

So I was checking if the 2 vertices of the graph already connected, but didn't consider the test below and wasted a lot of time looking for a mistake and rewriting the code

4 3
1 2 1
3 4 2
2 3 3

Correct output:
3
3
1 2
3 4
2 3

My output:
2
2
1 2
3 4

For me this test was usefull:

7 11
1 2 7
1 4 5
2 4 9
2 3 8
2 5 7
3 5 5
4 5 15
4 6 6
5 6 8
5 7 9
6 7 11

It can be done with only 3 cables with max value of 1.  Got AC

you should output edges in input order

The first test is something like this
4 4
1 2 1
2 3 1
3 4 2
4 1 1

I hope this helps you

You can just sort edges in non-increasing order and add them sequentially until there are two or more connectivity components...

i try to solve it with kruskal and it gives me wa6 can anyone help me?

need help. i used Kruskal's algorithm

Just minimize the max length of a single cable,then output all the edges that shorter then max or equal.
GL

4 6
1 2 1
1 3 1
1 4 2
2 3 1
3 4 1
2 4 1

1
3
1 2
1 3
3 4

well, i like prim better

After wa1 many times i submit programms that should got CE (i print some strings,not numbers) but got wa1. Also i print nothing - again wa1,but not CE. It's very strange. May be checker to this problem is incorrect?

I submit prim's realization that got AC at olympiads.ru. Also i submitted kruskal's realization that got AC at some past contest. Why both AC programms can't pass test #1? can somebody give me tricky test cases?

I wrote two idental programs in C++ and Pascal. First works for 0.565 sec, another for 0.062. I means, that tests for C++ and Pascal are different?!

Why I got MLE#3? I'm using 1 int[M][3] matrix to store the edges, 3 short[N+1] arrays for Union-find, and an additional short[N] to store the resulting spanning tree.

Bug in qsort.

Edited by author 18.02.2010 15:19

I think, that 1160 is MST problem. Is my idea correct?
And explain me, please, is my output for sample input correct :
1
3
1 2
2 3
3 4

program ural1160;
const
  maxn=1000;
  maxm=15000;
type
  edge=record v1,v2:word;l:longint;end;
var
  root:array[1..maxn]of word;
  e:array[1..maxm]of edge;
  n,m,i:word;
procedure qsort(s,t:word);
  var
    p,i,j:word;
    te:edge;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    te:=e[p];e[p]:=e[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (e[j].l>=te.l) do dec(j);
      if i=j then break;e[i]:=e[j];inc(i);
      while (i<j) and (e[i].l<=te.l) do inc(i);
      if i=j then break;e[j]:=e[i];dec(j);
    until i=j;
    e[i]:=te;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
procedure pathcomp(x:word);
  var
    r,t:word;
  begin
    r:=x;
    while root[r]<>r do r:=root[r];
    while root[x]<>r do begin
      t:=root[x];root[x]:=r;x:=t;
    end;
  end;
begin
  read(n,m);
  for i:=1 to m do
    read(e[i].v1,e[i].v2,e[i].l);
  qsort(1,m);

  for i:=1 to n do
    root[i]:=i;
  for i:=1 to m do begin
    pathcomp(e[i].v1);pathcomp(e[i].v2);
    if root[e[i].v1]<>root[e[i].v2] then begin
      root[root[e[i].v1]]:=root[e[i].v2];
      dec(n);
    end;
    if n=1 then break;
  end;

  writeln(e[i].l);
  writeln(i);
  for n:=1 to i do
    writeln(e[n].v1,' ',e[n].v2);
end.

Help me please.
I can't find error
this is my code:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int i;
    vector<pair<int,pair<int,int> > >a(m);
    vector<int>c(n);
    for(i=0;i<m;i++)
        cin>>a[i].second.first>>a[i].second.second>>a[i].first;
    for(i=0;i<n;i++)
        c[i]=i;

    sort(a.begin(),a.end());
    int kil=n;
    int pot=0;
    while(kil>1){
        if(c[a[pot].second.first]!=c[a[pot].second.second]){
            int c2=c[a[pot].second.second];
            int c1=c[a[pot].second.first];
            for(i=0;i<n;i++)
                if(c[i]==c2)
                    c[i]=c1;
            kil--;
        }
        pot++;
    }
    cout<<a[pot-1].first<<endl;
    cout<<pot<<endl;
    for(i=0;i<pot;i++)
        cout<<a[i].second.first<<' '<<a[i].second.second<<endl;
    return 0;
}

Edited by author 22.07.2008 16:20