Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class F {
- FastScanner in;
- PrintWriter out;
- class Edge {
- int to;
- double flow, cap;
- public Edge(int to, double cap) {
- super();
- this.to = to;
- this.cap = cap;
- }
- Edge rev;
- @Override
- public String toString() {
- return "Edge [to=" + to + ", flow=" + flow + ", cap=" + cap + "]";
- }
- }
- class Flow {
- ArrayList<Edge>[] g;
- int[] h;
- int[] cur;
- int[] q;
- int n;
- Flow(int n) {
- this.n = n;
- g = new ArrayList[n];
- for (int i = 0; i < n; i++) {
- g[i] = new ArrayList<>();
- }
- h = new int[n];
- q = new int[n];
- cur = new int[n];
- }
- void clean() {
- for (int i = 0; i < n; i++) {
- for (Edge e : g[i]) {
- e.flow = 0;
- }
- }
- }
- Edge addEdge(int fr, int to, double cap) {
- Edge e1 = new Edge(to, cap);
- Edge e2 = new Edge(fr, 0);
- e1.rev = e2;
- e2.rev = e1;
- g[fr].add(e1);
- g[to].add(e2);
- return e1;
- }
- boolean bfs() {
- int qIt = 0, qSz = 1;
- Arrays.fill(h, -1);
- q[0] = 0;
- h[0] = 0;
- while (qIt < qSz) {
- int v = q[qIt++];
- for (Edge e : g[v]) {
- if (e.flow < e.cap) {
- if (h[e.to] == -1) {
- h[e.to] = h[v] + 1;
- q[qSz++] = e.to;
- }
- }
- }
- }
- return h[n - 1] != -1;
- }
- double dfs(int v, double fl) {
- if (v == n - 1 || fl == 0) {
- return fl;
- }
- for (; cur[v] < g[v].size(); cur[v]++) {
- Edge e = g[v].get(cur[v]);
- if (h[e.to] == h[v] + 1) {
- double add = dfs(e.to, Math.min(e.cap - e.flow, fl));
- if (add == 0) {
- continue;
- }
- e.flow += add;
- e.rev.flow -= add;
- return add;
- }
- }
- return 0;
- }
- double getFlow() {
- double res = 0;
- while (bfs()) {
- Arrays.fill(cur, 0);
- while (true) {
- double xx = dfs(0, Double.MAX_VALUE);
- if (xx == 0) {
- break;
- }
- res += xx;
- }
- }
- return res;
- }
- }
- void solve() {
- int n = in.nextInt();
- int m = in.nextInt();
- int w = in.nextInt();
- int h = in.nextInt();
- double[] maxColor = new double[m];
- for (int i = 0; i < m; i++) {
- maxColor[i] = in.nextDouble();
- }
- double last = 0;
- double[] ww = new double[n];
- for (int i = 0; i < n - 1; i++) {
- double cur = in.nextDouble();
- ww[i] = cur - last;
- last = cur;
- }
- ww[n - 1] = w - last;
- double[][] min = new double[n][m];
- double[][] max = new double[n][m];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- min[i][j] = in.nextDouble();
- }
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- max[i][j] = in.nextDouble();
- }
- }
- Flow f = new Flow(2 + n + m);
- Edge[] toSections = new Edge[n];
- for (int i = 0; i < n; i++) {
- toSections[i] = f.addEdge(0, 1 + i, 0);
- }
- for (int i = 0; i < m; i++) {
- double sumColor = 0;
- for (int j = 0; j < n; j++) {
- sumColor += min[j][i];
- }
- f.addEdge(1 + n + i, 1 + n + m, maxColor[i] - sumColor);
- }
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- f.addEdge(1 + i, 1 + n + j, max[i][j] - min[i][j]);
- }
- }
- double left = 0, right = h;
- double maxH = 0;
- double[] minH = new double[n];
- for (int i = 0; i < n; i++) {
- double sum = 0;
- for (int j = 0; j < m; j++) {
- sum += min[i][j];
- }
- minH[i] = sum / ww[i];
- maxH = Math.max(maxH, sum / ww[i]);
- }
- for (int it = 0; it < 66; it++) {
- double mid = (left + right) / 2;
- f.clean();
- for (int i = 0; i < n; i++) {
- double curH = Math.max(minH[i], maxH - mid) - minH[i];
- toSections[i].cap = curH * ww[i];
- }
- f.getFlow();
- boolean ok = true;
- for (int i = 0; i < n; i++) {
- if (toSections[i].flow != toSections[i].cap) {
- ok = false;
- break;
- }
- }
- if (ok) {
- right = mid;
- } else {
- left = mid;
- }
- }
- out.printf(Locale.US, "%.3f\n", (left + right) / 2);
- }
- void run() {
- try {
- in = new FastScanner(new File("F.in"));
- out = new PrintWriter(new File("F.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- double nextDouble() {
- return Double.parseDouble(next());
- }
- }
- public static void main(String[] args) {
- new F().runIO();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement