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;
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

How to Build A Debuggable Styled Component

Server-Side GraphQL with Apollo & NextJS — Part 1: Setup

Banner image for Server-Side GraphQL Tutorial with Apollo & NextJS

Open-source Tools to Make the Lives of Developers Easier

Let’s take a look at some improvements in Javascript

JavaScript: How to implement a queue

Implementing SDF text rendering in PIXI.js

React Native + Firebase: How to Send Push Notifications on iOS & Android Part 1

React developer roadmap 2022

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
dume0011

dume0011

More from Medium

Leetcode 1514. Path with Maximum Probability

LeetCode 53. Maximum Subarray

Introduction To Merge Sort

What is a Stack?