Cod sursa(job #2052133)

Utilizator neth------ neth Data 30 octombrie 2017 01:41:01
Problema Cuplaj maxim de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <bits/stdc++.h>
using namespace std;

#define ROW 0
#define COL 1

template <typename T, int S, T INF>
void kuhn_augment(
    int const n, T const g[S][S], int rig[S], int lef[S],
    T v[2][S], int c[2][S], int x[S]) {
  T t = INF;
  for (int i = 1; i <= n; i++) if (!c[ROW][i])
    for (int j = 1; j <= n; j++) if (!c[COL][j])
      t = min(t, g[i][j] - v[ROW][i] - v[COL][j]);

  for (int i = 1; i <= n; i++)
    v[ROW][i] -= t * c[ROW][i],
    v[COL][i] += t * !c[COL][i];

  for (int i = 1; i <= n; i++) if (!c[ROW][i])
    for (int j = 1; j <= n; j++) if (!c[COL][j])
      if (g[i][j] - v[ROW][i] - v[COL][j] == 0)
        if (rig[i]) {
          x[i] = j; c[COL][rig[i]] = !(c[ROW][i] = 1);
          break;
        } else {
          while (i) rig[i] = j, lef[j] = lef[j] + i - (i = lef[j]), j = x[i];
          return;
        }

  kuhn_augment<T, S, INF>(n, g, rig, lef, v, c, x);
}

template <typename T, int S, T INF>
void kuhn(int const n, T const g[S][S], int rig[S], int lef[S]) {
  memset(rig, 0, S * sizeof(T));
  memset(lef, 0, S * sizeof(T));

  T t, v[2][S];
  for (int i = 1; i <= n; i++) {
    t = INF; for (int j = 1; j <= n; j++) t = min(t, g[i][j]); v[ROW][i] = t;
    t = INF; for (int j = 1; j <= n; j++) t = min(t, g[j][i]); v[COL][i] = t;
  }

  int c[2][S]; int x[S];
  for (int step = 1; step <= n; step++) {
    memset(c, 0, sizeof c);
    memset(x, 0, sizeof(x));
    memcpy(c[COL], lef, sizeof c[COL]);
    kuhn_augment<T, S, INF>(n, g, rig, lef, v, c, x);
  }

  for (int i = 1; i <= n; i++)
    if (g[i][rig[i]] == INF) rig[i] = lef[rig[i]] = 0;
}

#define MAX 301
#define INF 20001
int g[MAX][MAX], t[MAX][MAX], rig[MAX], lef[MAX];

int main() {
  ifstream cin("cmcm.in"); ofstream cout("cmcm.out");
  ios_base::sync_with_stdio(0); cin.tie(0);

  int n, m, e; cin >> n >> m >> e; n = max(n, m);

  for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g[i][j] = INF;

  for (int i = 1; i <= e; i++) {
    int x, y, c; cin >> x >> y >> c;
    g[x][y] = c;
    t[x][y] = i;
  }

  kuhn<int, MAX, INF>(n, g, rig, lef);

  int num = 0, sum = 0;
  for (int i = 1; i <= n; i++) if (rig[i]) num++, sum += g[i][rig[i]];

  cout << num << ' ' << sum << '\n';
  for (int i = 1; i <= n; i++) if (rig[i]) cout << t[i][rig[i]] << ' '; cout << '\n';
}