POJ: The Windy’s

33 4
100 100 100 1
99 99 99 1
98 98 98 1
3 4
1 100 100 100
99 1 99 99
98 98 1 98
3 4
1 100 100 100
1 99 99 99
98 1 98 98
2.000000
1.000000
1.333333
#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 50
#define MAX_M 50
#define MAX_V ((MAX_N) * (MAX_M) + (MAX_N) + 2)
#define INF 0x3f3f3f3f
int Z[MAX_N][MAX_M];
int n, m;
int V;
vector<SEdge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V];
int preve[MAX_V];
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+V, INF);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v < V; ++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[]) {
int times;
scanf("%d", &times);
while (times--) {
getchar();
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
getchar();
for (int j = 0; j < m; ++j) scanf("%d", &Z[i][j]);
}
int s = n + n * m;
int t = s + 1;
V = t + 1;

for (int i = 0; i < V; ++i) G[i].clear();
for (int i = 0; i < n; ++i) add_edge(s, i, 1, 0);
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
add_edge(n + j * n + k, t, 1, 0);
for (int i = 0; i < n; ++i)
add_edge(i, n + j * n + k, 1, (k+1) * Z[i][j]);
}
}
printf("%0.6f\n", (double)min_cost_flow(s, t, n) / n);
}
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