Cod sursa(job #1565829)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 11 ianuarie 2016 14:58:24
Problema Lazy Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#define nmax 200009
using namespace std;

ifstream fin ("lazy.in");
ofstream fout ("lazy.out");

struct lista{
    int x, y, c1, c2, i;
};

lista a[nmax];
int n, m, t[nmax], c[nmax];

inline bool cmp(const lista nr1, const lista nr2)
{
   if (nr1.c1 ==  nr2.c1)
       return (nr1.c2 > nr1.c2);
   return (nr1.c1 < nr2.c1);
}

int Find(int x)
{
   int y, z;
   y = x;

   while (t[x]!=0)
      x = t[x];

   while (t[y]!=0)
   {
      z = t[y];
      t[y] = x;
      y = z;
   }
   return x;
}

void Union(int x, int y)
{
   if (c[x] > c[y])
   {
       t[y] = x;
       c[y] = 0;
       c[x] += c[y];
   }
   else
   {
       t[x] = y;
       c[x] = 0;
       c[y] += c[x];
   }
}

void Citire()
{
  int c1, c2, x, y;
  lista q;
  fin >> n >> m;
  for (int i=1; i<=m; i++)
  {
    fin >> x >> y >> c1 >> c2;
    q.x = x;
    q.y = y;
    q.c1 = c1;
    q.c2 = c2;
    q.i  = i;
    a[i] = q;
  }
}

void Rezolva()
{
   int i, j, x, y;
   sort (a+1, a+m+1, cmp);
   for (i=1; i<=n; i++)
      { t[i] = 0; c[i] = 1; }

   for (i=1; i<=m; i++)
   {
      x = a[i].x; y = a[i].y;
      if (Find(x) != Find(y))
      {
          Union(x,y);
          a[i].c1 = -2; a[i].c2 = -2;
      }
   }
}

void Afisare()
{
   int i;
   for (i=1; i<n; i++)
    {
        if (a[i].c1 == -2)
        {
            fout << a[i].i << "\n";
        }
    }
}

int main ()
{
  Citire();
  Rezolva();
  Afisare();
  fin.close();
  fout.close();
  return 0;
}