MINCOST - Luồng với chi phí nhỏ nhất
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include "stdio.h"
#include "string.h"
int n, flow, start, finish, m;
int cap[111][111], cost[111][111], f[111][111];
int fx[111], dt;
bool visited[111], daxong;
bool dfs(int i) {
if(daxong) return false;
visited[i] = true;
if(i==finish) { --flow; return daxong = true; }
for(int j=1;j<=n;++j) {
if(f[i][j]<cap[i][j] && !visited[j]) {
if(fx[i]+cost[i][j]-fx[j]==0) {
if(dfs(j)) { ++f[i][j]; return true; }
}
else dt <?= fx[i]+cost[i][j]-fx[j];
}
if(f[j][i]>0 && !visited[j]) {
if(fx[j]+cost[j][i]-fx[i]==0) {
if(dfs(j)) { --f[j][i]; return true; }
}
else dt <?= -(fx[j]+cost[j][i]-fx[i]);
}
}
return false;
}
int main() {
int u, v, c, d;
scanf("%d%d%d%d%d",&n,&m,&flow,&start,&finish);
for(int i=0;i<m;++i) {
scanf("%d%d%d%d",&u,&v,&c,&d);
cap[u][v] = cap[v][u] = d;
cost[u][v] = cost[v][u] = c;
}
for(int i=0;i<50000 && flow>0;++i) {
memset( visited, false, sizeof(visited));
daxong = false;
dt = 1000000000;
if(!dfs(start))
for(int i=1;i<=n;++i) if(!visited[i]) fx[i] += dt;
}
if(flow>0) printf("-1");
else {
int res = 0;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) res += f[i][j] * cost[i][j];
printf("%d\n",res);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
if(f[i][j]>0) printf("%d %d %d\n",i, j, f[i][j]);
printf("0 0 0");
}
return 0;
}