## Algoritmo de MinCostMaxFlow.

Cualquier duda no dudes en contactar.

``````/**
* Author: Isaac
* Date:
* Description: - Pair of (maximum flow value, minimum cost value). Look at positive values only. Use adjacency matrix. For a regular max flow, set all edge costs to 0.
* Time:  O(V^4 * MAX_EDGE_COST)
* Status:
*/
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long L;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

const L INF = numeric_limits<L>::max() / 4;

struct MinCostMaxFlow {
int N;
VVL cap, flow, cost;
VI found;
VL dist, pi, width;

MinCostMaxFlow(int N) :
N(N), cap(N, VL(N)), flow(N, VL(N)), cost(N, VL(N)),
found(N), dist(N), pi(N), width(N), dad(N) {}

void AddEdge(int from, int to, L cap, L cost) {
this->cap[from][to] = cap;
this->cost[from][to] = cost;
}

void Relax(int s, int k, L cap, L cost, int dir) {
L val = dist[s] + pi[s] - pi[k] + cost;
if (cap && val < dist[k]) {
dist[k] = val;
width[k] = min(cap, width[s]);
}
}

L Dijkstra(int s, int t) {
fill(found.begin(), found.end(), false);
fill(dist.begin(), dist.end(), INF);
fill(width.begin(), width.end(), 0);
dist[s] = 0;
width[s] = INF;

while (s != -1) {
int best = -1;
found[s] = true;
for (int k = 0; k < N; k++) {
if (found[k]) continue;
Relax(s, k, cap[s][k] - flow[s][k], cost[s][k], 1);
Relax(s, k, flow[k][s], -cost[k][s], -1);
if (best == -1 || dist[k] < dist[best]) best = k;
}
s = best;
}

for (int k = 0; k < N; k++)
pi[k] = min(pi[k] + dist[k], INF);
return width[t];
}

pair<L, L> GetMaxFlow(int s, int t) {
L totflow = 0, totcost = 0;
while (L amt = Dijkstra(s, t)) {
totflow += amt;
for (int x = t; x != s; x = dad[x].first) {
} else {
}
}
}
return make_pair(totflow, totcost);
}
};

int main() { //Data Flow
int N, M;

while (scanf("%d%d", &N, &M) == 2) {
VVL v(M, VL(3));
for (int i = 0; i < M; i++)
scanf("%Ld%Ld%Ld", &v[i][0], &v[i][1], &v[i][2]);
L D, K;
scanf("%Ld%Ld", &D, &K);

MinCostMaxFlow mcmf(N+1);
for (int i = 0; i < M; i++) {
}

pair<L, L> res = mcmf.GetMaxFlow(0, N);

if (res.first == D) {
printf("%Ld\n", res.second);
} else {
printf("Impossible.\n");
}
}
return 0;
}
``````