# Cod sursa(job #2279108)

Utilizator Data 8 noiembrie 2018 22:14:04 Cuplaj maxim de cost minim 100 cpp-64 done Arhiva educationala 4 kb
``````/// inspired from another source code https://www.infoarena.ro/job_detail/1781469

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("cmcm.in");
ofstream fout("cmcm.out");
#define MAX 305
#define NIL -1
#define inf 3000000
#define cout fout
int potential[MAX], idx[MAX], l[MAX], r[MAX], m_distance[MAX];
int cost[MAX][MAX], from[MAX], edge[MAX][MAX];
int n, m;

void solve() {
int frontPos, backPos, newNode, potentialValue, rightNode, leftNode;
int leftNodePotential, potentialDistance = 0;
int i, k, step;
for(i = 0 ; i < m ; i++) {
idx[i] = i;
l[i] = NIL;
}
for(i = 0 ; i < n ; i++) {
r[i] = NIL;
}
for(step = 0; step < n ; step++) {
//cout << step << endl;
for(i = 0 ; i < m ; i++) {
m_distance[i] = cost[step][i] - potential[i];
from[i] = step;
}
frontPos = backPos = 0;
newNode = NIL;
while(newNode == NIL) {
if(frontPos == backPos) {
potentialValue = m_distance[idx[backPos++]];
for(i = backPos ; i < m ; i++) {
if(potentialValue < m_distance[idx[i]])
continue;
if(potentialValue > m_distance[idx[i]]){
potentialValue = m_distance[idx[i]];
backPos = frontPos;
}
swap(idx[i], idx[backPos++]);
}
for(i = frontPos ; i < backPos ; i++) {
if(l[idx[i]] == NIL) {
newNode = idx[i];
break;
}
}
}
if(newNode == NIL) {
rightNode = idx[frontPos++];
leftNode = l[rightNode];
leftNodePotential = cost[leftNode][rightNode] - potential[rightNode];
for(k = backPos ; k < m ; k++) {
/// here we will update the local minimums (m_distance)
int current_potential = potentialValue + (cost[leftNode][idx[k]] - potential[idx[k]] - leftNodePotential);
if(m_distance[idx[k]] > current_potential) {
m_distance[idx[k]] = current_potential;
from[idx[k]] = leftNode;
if(current_potential == potentialDistance) {
if(l[idx[k]] == NIL) {
newNode = idx[k];
break;
}
swap(idx[k], idx[backPos++]);
}
}
}
}
}
for(i = 0 ; i < frontPos ; i++) {
potential[idx[i]] += m_distance[idx[i]] - potentialValue;
}
do {
//cout << newNode << endl;
leftNode = from[newNode];
rightNode = r[leftNode];
l[newNode] = leftNode;
r[leftNode] = newNode;
newNode = rightNode;
//cout << newNode << endl;

} while(leftNode != step);
}
vector<int> result;
int c = 0;
for(i = 0 ; i < n ; i++) {
if(cost[i][r[i]] == inf)
continue;
c += cost[i][r[i]];
result.push_back(edge[i][r[i]]);
}
cout << result.size() << " " << c << endl;
for(i = 0 ; i < (int)result.size() ; i++) {
cout << result[i] << " ";
}
}

int main()
{
int e, i, j, x, y, c;
bool swapped = false;
fin >> n >> m >> e;
if(n > m) {
swapped = true;
swap(n, m);
}
for(i = 0 ; i < n ; i++) {
for(j = 0 ; j < m ; j++) {
cost[i][j] = inf;
}
}
for(int ki = 1 ; ki <= e ; ki++) {
fin >> x >> y >> c;
x--; y--;
if(swapped)
swap(x, y);
cost[x][y] = c;
edge[x][y] = ki;
}
solve();
}
``````