Cod sursa(job #2474684)

Utilizator PetyAlexandru Peticaru Pety Data 15 octombrie 2019 18:36:30
Problema Critice Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")


using namespace std;

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



const int N = 205;
int n, m, level[1002], start[1002], nr;

struct edge{
  int v;
  int flow, c;
  int rev;
  int index;
};
vector<edge>g[N];

void addEdge (int x, int y, int flow) {
  g[x].push_back({y, 0, flow, g[y].size(), ++nr});
  g[y].push_back({x, 0, flow, g[x].size() - 1, nr});
}

bool bfs () {
  for (int i = 1; i <= n ; i++)
    level[i] = -1;
  level[1] = 0;
  queue<int>q;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (auto it : g[x]) {
      if (level[it.v] < 0 && it.flow < it.c) {
        level[it.v] = level[x] + 1;
        q.push(it.v);
      }
    }
  }
  if (level[n] < 0)
    return 0;
  else
    return 1;
}

int dinica (int u, int t, int sum) {
  if (u == t)
    return sum;
  for (;start[u] < g[u].size(); start[u]++) {
     //if (u == 1)
      //  cout << start[u] << " ";
    edge e = g[u][start[u]];

    if (level[e.v] == level[u] + 1 && e.flow < e.c) {

      int aux = min(sum, e.c - e.flow);
      int aux2 = dinica(e.v, t, aux);
      if (aux2 > 0) {
        g[u][start[u]].flow += aux2;
        g[e.v][e.rev].flow -= aux2;
        return aux2;
      }
    }
  }
  return 0;
}

int viz1[1002], viz2[1002];

void dfs1 (int x) {
  viz1[x] = 1;
  for (int i = 0; i < g[x].size(); i++) {
    edge e = g[x][i];
    if (!viz1[e.v] && e.c - e.flow > 0)
      dfs1(e.v);
  }
}
void dfs2 (int x) {
  viz2[x] = 1;
  for (int i = 0; i < g[x].size(); i++) {
    edge e = g[x][i];
    edge e1 = g[e.v][e.rev];
    if (!viz2[e.v] && e1.c - e1.flow > 0)
      dfs2(e.v);
  }
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y;
    int cost;
    fin >> x >> y >> cost;
    addEdge(x, y, cost);
  }
  int ans = 0;
  while (bfs()) {
    int k;
    memset(start, 0, sizeof(start));
    while ((k = dinica(1, n , INT_MAX)))
      ans += k;
  }
  dfs1(1);
  dfs2(n);
  vector<int>sol;
  for (int i = 1; i <= n; i++)
    for (edge it : g[i]) {
      if (viz1[i] && viz2[it.v] && it.c - it.flow== 0) {
        sol.push_back(it.index);
      }
    }
  sort(sol.begin(), sol.end());
  fout << sol.size() << "\n";
  for (int i = 0; i < sol.size(); i++)
    fout << sol[i] << "\n";
  return 0;
}