codeforces/240e

240e.cpp

#include <fstream>
#include <iostream>
#include <list>
#include <vector>

using namespace std;

class Edge {
  public:
    int from;
    int to;
    int cost;
    int id;

    Edge(int from = 0, int to = 0, int cost = 0, int id = 0) :
        from(from), to(to), cost(cost), id(id) {
      // nothing
    }
};

class Node {
  public:
    list<Edge> edges;
    list<Edge>::const_iterator entry;

    Node() { }

    void addEdge(const Edge& e) {
      if (e.cost) {
        edges.push_back(e);
      } else {
        edges.push_front(e);
      }
    }

    void done() {
      entry = edges.begin();
    }

    list<Edge>::const_iterator getBegin() const {
      return edges.begin();
    }

    list<Edge>::const_iterator getEntry() const {
      return entry;
    }

    list<Edge>::const_iterator getEnd() const {
      return edges.end();
    }

    void setEntry(list<Edge>::const_iterator it) {
      entry = it;
    }
};

int getParent(vector<int>& parent, int v) {
  int u = v;
  list<int> x;
  while (parent[u] != u) {
    x.push_back(u);
    u = parent[u];
  }

  for (list<int>::iterator it = x.begin(); it != x.end(); ++ it) {
    parent[*it] = u;
  }
  return u;
}

int main(int argc , char * argv[]) {
  int n, m;

//#define fin cin
//#define fout cout

  ifstream fin("input.txt");
  ofstream fout("output.txt");
  fin >> n >> m;

  if (m < n - 1) {
    // a quick return
    fout << -1 << endl;
    return 0;
  }

  vector<Node> nodes(n);

  for (int i = 0; i < m; ++ i) {
    int a, b, c;
    fin >> a >> b >> c;
    -- b;
    if (b == 0) { // we don't need this edge.
      continue;
    }
    -- a;
    nodes[b].addEdge(Edge(a, b, c, i + 1));
  }

  for (int i = 0; i < n; ++ i) {
    nodes[i].done();
  }

  vector<int> parent(n);
  for (int v = 0; v < n; ++ v) {
    parent[v] = v;
  }

  for (int v = 1; v < n; ++ v) {
    list<Edge>::const_iterator vit = nodes[v].getEntry();
    if (vit == nodes[v].getEnd()) {
      fout << -1 << endl;
      return 0;
    }
    int entry = vit->from;
    int px = getParent(parent, entry);
    if (px != v) {
      parent[v] = px;
    }
  }

  for (int v = 1; v < n; ++ v) {
    list<Edge>::const_iterator vit = nodes[v].getEntry();
    if (vit == nodes[v].getEnd()) {
      fout << -1 << endl;
      return 0;
    }

    int entry = vit->from;
    int px = getParent(parent, entry);
    while (px == v) { // while the incoming edge still makes a
      int u = -1; // node to change
      list<Edge>::const_iterator newEntry;  // new Entry of u// have minimum modified cost
      int min = 100000000;
      for (int x = entry; x != v; x = nodes[x].getEntry()->from) {
        for (list<Edge>::const_iterator it = nodes[x].getBegin();
            it != nodes[x].getEnd(); ++ it) {
          if (getParent(parent, it->from) == v) {
            continue;
          }
          int w = it->cost - nodes[x].getEntry()->cost;
          if (w < min) {
            min = w;
            u = x;
            newEntry = it;
          }
        }
      }

      if (u == -1) {
        // we can't break this circle
        fout << -1 << endl;
        return 0;
      }
      // break this circle, change parents of internal nodes
      px = getParent(parent, newEntry->from);
      for (int x = entry; x != v; x = nodes[x].getEntry()->from) {
        parent[x] = px;
      }
      nodes[u].setEntry(newEntry);
    }
    parent[v] = px;
  }

  int cost = 0;
  list<int> repairs;
  for (int v = 1; v < n; ++ v) {
    if (nodes[v].getEntry()->cost) {
      cost += 1;
      repairs.push_back(nodes[v].getEntry()->id);
    }
  }

  fout << cost << endl;
  if (cost) {
    for (list<int>::const_iterator it = repairs.begin(); it != repairs.end();
        ++ it) {
      if (--cost) {
        fout << *it << ' ';
      } else {
        fout << *it << endl;
      }
    }
  }

  return 0;
}