SRM465

追記(3/27):600解いてSystemTest通した

250の問題を勘違いしていたせいで時間かかりまくり。全ての(x,y)に四角形を置くと思ってた…。2つかよ…。死にたい。誰か俺を殺せ。

ということでスコアは 1452->1423 と減少。600の方は最小カットという噂を聞いた。あとでリベンジするかな。

• > リベンジした。以下コード。

最大流で、エドモンズ・カープ。Dinic実装したことないですごめんなさい…。
それはそうとコード無駄に長い気がするので、あとで他人のを参考にするべきですね...。
…あとちゃんとtypedefしろよ > 俺

class GreenWarfare {
public:
    int calc_energy(int x1, int y1, int x2, int y2) {
        return (int)(pow(x1-x2, 2.0)+pow(y1-y2, 2.0));
    }

    int max_flow(vector<vector<int> >& edges, vector<vector<int> >& caps, int s, int t) {
        int f = 0, n = edges.size();
        vector<vector<int> > flow(n, vector<int>(n, 0));
        while (1) {
            // BFS
            queue<int> Q; Q.push(s);
            vector<int> prev(n, -1); prev[s] = s;
            while (!Q.empty() && prev[t] < 0) {
                int u = Q.front(); Q.pop();
                for (int i=0; i<static_cast<int>(edges[u].size()); ++i) {
                    int dst = edges[u][i];
                    if (prev[dst] < 0 && caps[u][dst]-flow[u][dst] > 0) {
                        prev[dst] = u;
                        Q.push(dst);
                    }
                }
            }
            if (prev[t] < 0) return f;
            int inc = INT_MAX;
            for (int i=t; prev[i] != i; i = prev[i]) {
                inc = min(inc, caps[prev[i]][i]-flow[prev[i]][i]);
            }
            for (int i=t; prev[i] != i; i = prev[i]) {
                flow[prev[i]][i] += inc; flow[i][prev[i]] -= inc;
            }
            f += inc;
        }
        return f;
    }

    void add(vector<vector<int> >& edges, vector<vector<int> >& costs, int s, int t, int c) {
        edges[s].push_back(t);
        costs[s][t] = c;
        edges[t].push_back(s);
        costs[t][s] = 0;
    }

    int minimumEnergyCost(vector <int> canonX, vector <int> canonY, vector <int> baseX, vector <int> baseY, vector <int> plantX, vector <int> plantY, int energySupplyRadius) {
        int s = 0, t = baseX.size()+plantX.size()+1;
        int base_offset = 1, plant_offset = 1+baseX.size();
        int R2 = energySupplyRadius*energySupplyRadius;

        vector<vector<int> > edges(t+1);
        vector<vector<int> > costs(t+1, vector<int>(t+1, 0));

        for (int i=0; i<static_cast<int>(baseX.size()); ++i) {
            // s -> base
            int e = INT_MAX;
            for (int j=0; j<static_cast<int>(canonX.size()); ++j) {
                e = min(e, calc_energy(baseX[i], baseY[i], canonX[j], canonY[j]));
            }
            add(edges, costs, s, base_offset+i, e);

            // base -> plant|t
            bool added = false;
            for (int j=0; j<static_cast<int>(plantX.size()); ++j) {
                if (calc_energy(baseX[i], baseY[i], plantX[j], plantY[j]) <= R2) {
                    added = true;
                    add(edges, costs, base_offset+i, plant_offset+j, INT_MAX);
                }
            }
            if (!added) {
                add(edges, costs, base_offset+i, t, INT_MAX);
            }
        }

        for (int i=0; i<static_cast<int>(plantX.size()); ++i) {
            // plant -> t
            int e = INT_MAX;
            for (int j=0; j<static_cast<int>(canonX.size()); ++j) {
                e = min(e, calc_energy(plantX[i], plantY[i], canonX[j], canonY[j]));
            }
            add(edges, costs, plant_offset+i, t, e);
        }

        return max_flow(edges, costs, s, t);
    }
};