# Cod sursa(job #2193700)

Utilizator Data 10 aprilie 2018 23:48:27 Cuplaj maxim de cost minim 100 cpp done Arhiva educationala 3.32 kb
``````// 1000x1000 ~ 3s
#include <bits/stdc++.h>
#define SZ(X) ((int) (X).size())
using namespace std;

const int kInf = 0x3f3f3f3f;
const int NIL = -1;

void JonkerVolgenant(const vector<vector<int>> &cost_matrix,
const vector<vector<int>> &edge_index,
ostream &cout) {
// n <= m
const int n = SZ(cost_matrix), m = SZ(*cost_matrix.begin());

vector<int> potential(m), m_distance(m);
vector<int> match_left(n, NIL), match_right(m, NIL);
vector<int> idx(m), from(m);

for (int i = 0; i < m; i += 1) {
idx[i] = m - i - 1;
}

for (int step = n - 1; step >= 0; step -= 1) {
for (int node = 0; node < m; node += 1) {
m_distance[node]=cost_matrix[step][node]-potential[node];
from[node] = step;
}
int potentialDistance, upTo, augmentationNode = NIL;
int frontPos = 0, backPos = 0;
while (augmentationNode == NIL) {
if (frontPos == backPos) {
upTo = frontPos;
potentialDistance = m_distance[idx[backPos++]];
for (int k = backPos; k < m; k += 1) {
if (m_distance[idx[k]] > potentialDistance) {
continue;
}

if (m_distance[idx[k]] < potentialDistance) {
backPos = frontPos;
potentialDistance = m_distance[idx[k]];
}

swap(idx[k], idx[backPos++]);
}
for (int k = frontPos; k < backPos; k += 1) {
if (match_right[idx[k]] == NIL) {
augmentationNode = idx[k];
break;
}
}
}
if (augmentationNode == NIL) {
int right_node = idx[frontPos++];
int left_node = match_right[right_node];
for (int k = backPos; k < m; k += 1) {
const int current_potential =
cost_matrix[left_node][idx[k]] - potential[idx[k]]
- cost_matrix[left_node][right_node]
+ potential[right_node] + potentialDistance;

if (current_potential < m_distance[idx[k]]) {
m_distance[idx[k]] = current_potential;
from[idx[k]] = left_node;
if (current_potential == potentialDistance) {
if (match_right[idx[k]] == NIL) {
augmentationNode = idx[k];
break;
}
swap(idx[k], idx[backPos++]);
}
}
}
}
}
for (int k = 0; k < upTo; k += 1) {
potential[idx[k]] += m_distance[idx[k]] - potentialDistance;
}
int node;
do {
match_right[augmentationNode] = from[augmentationNode];
node = from[augmentationNode];
swap(augmentationNode, match_left[node]);
} while (node != step);
}

// infoarena
int cost = 0, flow = 0;
for (int i = 0; i < n; i += 1) {
if (edge_index[i][match_left[i]] != NIL) {
flow += 1;
cost += cost_matrix[i][match_left[i]];
}
}

cout << flow << ' ' << cost << '\n';
for (int i = 0; i < n; i += 1) {
if (edge_index[i][match_left[i]] != NIL) {
cout << (1 + edge_index[i][match_left[i]]) << ' ';
}
}
cout << '\n';
cout.flush();
}

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

int n, m, e; cin >> n >> m >> e;

bool swapped_dimension = false;
if (n > m) {
swap(n, m);
swapped_dimension = true;
}

vector<vector<int>> cost_matrix(n, vector<int>(m, kInf));
vector<vector<int>> edge(n, vector<int>(m + n, NIL));
for (int i = 0; i < e; i += 1) {
int u, v, cost; cin >> u >> v >> cost;

if (swapped_dimension) {
swap(u, v);
}

cost_matrix[u - 1][v - 1] = cost;
edge[u - 1][v - 1] = i;
}

JonkerVolgenant(cost_matrix, edge, cout);

return 0;
}
``````