Submission #1148108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148108		rebe__1	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	87 ms	16196 KiB

joi2019_ho_t4

import java.util.*;
import static java.lang.Math.*;

public class joi2019_ho_t4 {
    
    static class Edge {
        int to, cap, cost, rev;
        public Edge(int to, int cap, int cost, int rev) {
            this.to = to;
            this.cap = cap;
            this.cost = cost;
            this.rev = rev;
        }
    }
    
    static int V;
    static ArrayList<Edge>[] graph;
    
    @SuppressWarnings("unchecked")
    static void initGraph(int V) {
        graph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
        }
    }
    
    static void addEdge(int s, int t, int cap, int cost) {
        graph[s].add(new Edge(t, cap, cost, graph[t].size()));
        graph[t].add(new Edge(s, 0, -cost, graph[s].size() - 1));
    }
    
    static long minCostFlow(int s, int t, int f) {
        long res = 0;
        int[] dist = new int[V];
        int[] prevV = new int[V];
        int[] prevE = new int[V];
        final int INF = 1 << 28;
        int[] potential = new int[V];
        
        while (f > 0) {
            Arrays.fill(dist, INF);
            dist[s] = 0;
            PriorityQueue<Pair> pq = new PriorityQueue<>();
            pq.add(new Pair(0, s));
            while (!pq.isEmpty()) {
                Pair p = pq.poll();
                int v = p.v;
                if (dist[v] < p.d) continue;
                for (int i = 0; i < graph[v].size(); i++) {
                    Edge e = graph[v].get(i);
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]) {
                        dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
                        prevV[e.to] = v;
                        prevE[e.to] = i;
                        pq.add(new Pair(dist[e.to], e.to));
                    }
                }
            }
            if (dist[t] == INF) {
                return -1;
            }
            for (int v = 0; v < V; v++) {
                if(dist[v] < INF) potential[v] += dist[v];
            }
            int addFlow = f;
            for (int v = t; v != s; v = prevV[v]) {
                addFlow = min(addFlow, graph[prevV[v]].get(prevE[v]).cap);
            }
            f -= addFlow;
            res += (long) addFlow * potential[t];
            for (int v = t; v != s; v = prevV[v]) {
                Edge e = graph[prevV[v]].get(prevE[v]);
                e.cap -= addFlow;
                graph[v].get(e.rev).cap += addFlow;
            }
        }
        return res;
    }
    
    static class Pair implements Comparable<Pair> {
        int d, v;
        public Pair(int d, int v) {
            this.d = d; this.v = v;
        }
        public int compareTo(Pair other) {
            return Integer.compare(this.d, other.d);
        }
    }
    
    static final int MAXN = 100010;
    static int n;
    static int[][] mat = new int[MAXN][3];
    static long moveCost = 0;
    
    static int moveVal(int value, int min, int max) {
        if (value < min) return min;
        if (value > max) return max;
        return value;
    }
    
    static long adjustmentCost(int x, int y, int n) {
        long cost = 0;
        if (x < 1) cost += (1 - x);
        if (x > n) cost += (x - n);
        if (y < 1) cost += (1 - y);
        if (y > 2) cost += (y - 2);
        return cost;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int totalCoins = 2 * n;
        
        for (int i = 1; i <= n; i++) {
            mat[i][1] = 0;
            mat[i][2] = 0;
        }
        moveCost = 0;
        for (int i = 1; i <= totalCoins; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            moveCost += adjustmentCost(x, y, n);
            int mx = moveVal(x, 1, n);
            int my = moveVal(y, 1, 2);
            mat[mx][my]++;
        }
        
        int V = 2 * n + 2;
        int S = 2 * n;
        int T = 2 * n + 1;
        initGraph(V);
        
        int totalSupply = 0;
        for (int i = 1; i <= n; i++) {
            for (int r = 1; r <= 2; r++) {
                int node = (i - 1) * 2 + (r - 1);
                int supply = mat[i][r] - 1;
                if (supply > 0) {
                    addEdge(S, node, supply, 0);
                    totalSupply += supply;
                } else if (supply < 0) {
                    addEdge(node, T, -supply, 0);
                }
            }
        }
        
        int INF_CAP = 1000000000;
        for (int i = 1; i <= n - 1; i++) {
            for (int r = 1; r <= 2; r++) {
                int u = (i - 1) * 2 + (r - 1);
                int v = (i) * 2 + (r - 1);
                addEdge(u, v, INF_CAP, 1);
            }
        }
        
        for (int i = 1; i <= n; i++) {
            int u = (i - 1) * 2 + 0;
            int v = (i - 1) * 2 + 1;
            addEdge(u, v, INF_CAP, 1);
            addEdge(v, u, INF_CAP, 1);
        }
        
        long flowCost = minCostFlow(S, T, totalSupply);
        if (flowCost < 0) {
            System.out.println("No es posible el flujo");
        } else {
            long answer = moveCost + flowCost;
            System.out.println(answer);
        }
        
        sc.close();
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63