MINCOST - Luồng với chi phí nhỏ nhất
Tác giả: skyvn97
Ngôn ngữ: C++
#include<bits/stdc++.h>
#define MAX 111
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi first
#define se second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
void minimize(int &x,const int &y) {
if (x>y) x=y;
}
class MaxFlowMinCost {
public:
struct edge {
int from,to,capa,flow,cost;
edge() {
from=0;to=0;capa=0;flow=0;cost=0;
}
edge(int u,int v,int ca,int co) {
from=u;to=v;capa=ca;flow=0;cost=co;
}
int residual(void) const {
return (capa-flow);
}
};
vector<vector<int> > g;
vector<edge> e;
vector<int> d,tr;
int n;
MaxFlowMinCost() {
n=0;
}
MaxFlowMinCost(int n) {
this->n=n;
g.assign(n+7,vector<int>());
e.clear();
d=vector<int>(n+7);
tr=vector<int>(n+7);
}
void addedge(int u,int v,int ca,int co) {
g[u].push_back(e.size());
e.push_back(edge(u,v,ca,co));
g[v].push_back(e.size());
e.push_back(edge(v,u,0,-co));
}
bool FordBellman(int s,int t) {
FOR(i,1,n) {
d[i]=INF;
tr[i]=-1;
}
vector<bool> inq=vector<bool>(n+7,false);
queue<int> q;
while (!q.empty()) q.pop();
q.push(s);inq[s]=true;d[s]=0;
while (!q.empty()) {
int u=q.front();q.pop();inq[u]=false;
FORE(it,g[u]) if (e[*it].residual()>0) {
int v=e[*it].to;
if (d[v]>d[u]+e[*it].cost) {
d[v]=d[u]+e[*it].cost;
tr[v]=*it;
if (!inq[v]) {
q.push(v);
inq[v]=true;
}
}
}
}
return (d[t]<INF);
}
ii getflow(int s,int t) {
int totflow=0;
int totcost=0;
while (FordBellman(s,t)) {
int delta=INF;
for (int u=t;u!=s;u=e[tr[u]].from) minimize(delta,e[tr[u]].residual());
for (int u=t;u!=s;u=e[tr[u]].from) {
e[tr[u]].flow+=delta;
e[tr[u]^1].flow-=delta;
}
totflow+=delta;
totcost+=delta*d[t];
}
return (ii(totflow,totcost));
}
};
int capa[MAX][MAX],cost[MAX][MAX];
int n,m,k,s,t;
MaxFlowMinCost g;
void loadgraph(void) {
scanf("%d",&n);
scanf("%d",&m);
scanf("%d",&k);
scanf("%d",&s);
scanf("%d",&t);
memset(capa,-1,sizeof capa);
REP(i,m) {
int u,v,c,d;
scanf("%d",&u);
scanf("%d",&v);
scanf("%d",&c);
scanf("%d",&d);
capa[u][v]=d;
cost[u][v]=c;
capa[v][u]=d;
cost[v][u]=c;
}
g=MaxFlowMinCost(n+1);
FOR(u,1,n) FOR(v,1,n) if (capa[u][v]>=0) g.addedge(u,v,capa[u][v],cost[u][v]);
g.addedge(n+1,s,k,0);
}
void process(void) {
ii res=g.getflow(n+1,t);
if (res.fi<k) {
printf("-1");
return;
}
printf("%d\n",res.se);
int totcost=0;
REP(i,g.e.size()) if (i%2==0 && g.e[i].flow>0) {
if (g.e[i].from<=n) printf("%d %d %d\n",g.e[i].from,g.e[i].to,g.e[i].flow);
totcost+=g.e[i].cost*g.e[i].flow;
}
assert(res==ii(k,totcost));
printf("0 0 0");
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("tmp.txt","r",stdin);
printf("START\n");
#endif
loadgraph();
process();
return 0;
}