## Solución al problema número 10594 de UVA - 10594.

Cualquier duda no dudes en contactar.

``````#include <bits/stdc++.h>
#define INF LLONG_MAX
#define MAX_V 1+2*100
#define MAX_E 2*10001
using namespace std;

typedef long long edge_type;
int V,E,previ[MAX_V],last[MAX_V];
edge_type flowVal,flowCost,cap[MAX_E],cost[MAX_E],to[MAX_E],nexti[MAX_E],dist[MAX_V],pot[MAX_V];

void init(){
memset(last,-1,sizeof(last));
E = 0;
}
void add_edge(int u, int v, edge_type capacity, edge_type cst){
to[E] = v, cap[E] = capacity;
cost[E] = cst, nexti[E] = last[u];
last[u] = E++;
to[E] = u, cap[E] = 0;
cost[E] = -cst, nexti[E] = last[v];
last[v] = E++;
}

void mincostmaxflow(int s, int t){
flowVal = flowCost = 0;
memset(pot,0,sizeof(pot));

while(true){
memset(previ,-1,sizeof(previ));
for(int i = 0;i<V;++i) dist[i] = INF;
set< pair<edge_type, int> > Q;
Q.insert(make_pair(0,s));
dist[s] = previ[s] = 0;
while(!Q.empty()){
int aux = Q.begin()->second; Q.erase(Q.begin());
for(int e = last[aux];e!=-1;e = nexti[e]){
if(cap[e]<=0) continue;
edge_type new_dist = dist[aux]+cost[e]+pot[aux]-pot[to[e]];
if(new_dist<dist[to[e]]){
Q.erase(make_pair(dist[to[e]],to[e]));
dist[to[e]] = new_dist;
previ[to[e]] = e;
Q.insert(make_pair(new_dist,to[e]));
}
}
}
if (previ[t]==-1) break;
edge_type f = INF;
for(int i = t;i!=s;i = to[previ[i]^1]) f = min(f,cap[previ[i]]);
for(int i = t;i!=s;i = to[previ[i]^1]){
cap[previ[i]] -= f;
cap[previ[i]^1] += f;
}
flowVal += f;
flowCost += f*(dist[t]-pot[s]+pot[t]);

for(int i = 0;i<V;++i) if (previ[i]!=-1) pot[i] += dist[i];
}
}

int main(){
int N,M,u[5000],v[5000];
long long cst[5000],D,K;

while(scanf("%d %d",&N,&M)==2){
V = 2*N+1;

for(int i = 0;i<M;++i){
scanf("%d %d %lld",&u[i],&v[i],&cst[i]);
--u[i]; --v[i];
}
scanf("%lld %lld",&D,&K);

init();

for(int i = 0;i<M;++i){
}

mincostmaxflow(0,2*N-1);

if(flowVal!=D) printf("Impossible.\n");
else printf("%lld\n",flowCost);
}
return 0;
}
``````