POJ: Farm Tour

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
6
#include <cstdio>
#include <vector>
using namespace std;struct SEdge {
int to;
int cap;
int cost;
int rev;
SEdge(int t, int c, int co, int r): to(t), cap(c), cost(co), rev(r) {}
};
#define MAX_N 1000
#define MAX_M 10000
#define INF 0x3f3f3f3f
int n, m;
vector<SEdge> G[MAX_N];
int dist[MAX_N];
int prevv[MAX_N];
int preve[MAX_N];
void add_edge(int from, int to, int cap, int cost) {
SEdge fromEdge(to, cap, cost, (int)G[to].size());
G[from].push_back(fromEdge);
SEdge toEdge(from, 0, -cost, (int)G[from].size() - 1);
G[to].push_back(toEdge);
}
int min_cost_flow(int s, int t, int f) {
int res = 0;
while (f > 0) {
fill(dist, dist+n, INF);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v < n; ++v) {
if (dist[v] == INF) continue;
for (int i = 0; i < G[v].size(); ++i) {
SEdge& e = G[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
if (dist[t] == INF) return -1; int d = f;
for (int v = t; v != s; v = prevv[v])
d = min(d, G[prevv[v]][preve[v]].cap);
f -= d;
res += d * dist[t];
for (int v = t; v != s; v = prevv[v]) {
SEdge& e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
int main(int argc, char *argv[]) {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++i) {
getchar();
int from, to, cost;
scanf("%d%d%d", &from, &to, &cost);
add_edge(from - 1, to - 1, 1, cost);
add_edge(to - 1, from - 1, 1, cost);
}
printf("%d\n", min_cost_flow(0, n-1, 2)); return 0;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store