Cod sursa(job #22424)

Utilizator vlad_popaVlad Popa vlad_popa Data 26 februarie 2007 15:10:26
Problema Critice Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
using namespace std;

#include <cstdio>
#include <cassert>
#include <vector>

#define FIN "critice.in"
#define FOUT "critice.out"
#define NMAX 1001
#define INF 0x3f3f3f3f

int c[NMAX][NMAX], N, M, f[NMAX][NMAX], iter, pred[NMAX], d[NMAX], rez[NMAX];
vector<int> cd;
bool vizs[NMAX], vizt[NMAX];
struct retine {int n1, n2;};
retine ret[10*NMAX];

void bf ()
{
  int v;
  d[1] = iter;
  cd.push_back(1);
  while (cd.size())
   {
     v = *(cd.end() - 1);
     assert (v >= 1 && v <= N);
     cd.pop_back();
     for (int i = 1; i <= N; ++ i)
       if (c[v][i] - f[v][i] > 0 && d[i] != iter)
        {
          d[i] = iter;
          pred[i] = v;
          cd.push_back (i);
          if (i == N)
           {
             cd.clear();
             return;
           }
        }
   }
  cd.clear();
}

void ford_fulk ()
{
  int i;
  ++ iter;
  while (d[N] != iter)
   {
     int min = INF;
     bf ();
     if (d[N] != iter)
       break;
     i = N;
     while (pred[i])
      {
        if (min > c[pred[i]][i] - f[pred[i]][i])
          min = c[pred[i]][i] - f[pred[i]][i];
        i = pred[i];
      }
     i = N;
     while (pred[i])
      {
        f[pred[i]][i] += min;
        f[i][pred[i]] -= min;
        i = pred[i];
      }
     ++ iter;
   }
}

void bfs ()
{
  ++ iter;
  int v;
  d[1] = iter;
  vizs[1] = true;
  cd.push_back(1);
  while (cd.size())
   {
     v = *(cd.end() - 1);
     //fprintf (stderr, "%d ", v);
     assert (v >= 1 && v <= N);
     cd.pop_back();
     for (int i = 1; i <= N; ++ i)
       if (c[v][i] - f[v][i] > 0 && d[i] != iter && -f[v][i] != c[v][i])
        {
          d[i] = iter;
          vizs[i] = true;
          cd.push_back (i);
        }
   }
  cd.clear();
}

void bft ()
{
  ++ iter;
  int v;
  d[N] = iter;
  vizt[N] = true;
  cd.push_back(N);
  while (cd.size())
   {
     v = *(cd.end() - 1);
     //fprintf (stderr, "%d ", v);
     assert (v >= 1 && v <= N);
     cd.pop_back();
     for (int i = 1; i <= N; ++ i)
       if (c[v][i] - f[v][i] > 0 && d[i] != iter && -f[v][i] != c[v][i])
        {
          d[i] = iter;
          vizt[i] = true;
          cd.push_back (i);
        }
   }
  cd.clear();
}

int
 main ()
{
  int x, y, cap;
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d%d", &N, &M);
  for (int i = 1; i <= M; ++ i)
   {
     scanf ("%d%d%d", &x, &y, &cap);
     c[x][y] = c[y][x] = cap;
     ret[i].n1 = x;
     ret[i].n2 = y;
   }
  ford_fulk ();
  /*for (int i = 1; i <= N; ++ i)
    for (int j = 1; j <= N; ++ j)
      if (f[i][j])
        fprintf (stderr, "%d %d   flux : %d", i, j, f[i][j]);*/
  bfs ();
  bft ();
  int ct = 0;
  /*fprintf (stderr, "\n");
  for (int i = 1; i <= M; ++ i)
    fprintf (stderr, "%d ", vizs[i]);
  fprintf (stderr, "\n");
  for (int i = 1; i <= M; ++ i)
    fprintf (stderr, "%d ", vizt[i]);*/
  for (int i = 1; i <= M; ++ i)
    if ((vizs[ret[i].n1] && vizt[ret[i].n2]) ||
         vizs[ret[i].n2] && vizt[ret[i].n1])
           rez[++ct] = i;
  printf ("%d\n", ct);
  for (int i = 1; i <= ct; ++ i)
    printf ("%d\n", rez[i]);
  return 0;
}