Форум DL

Мой профиль

USACO 2006 March Silver: Problem 7: Water Slides

USACO March 2006 Problem 'slides' Analysis
by Bruce Merry
This is a restricted version of the Chinese Postman problem, a fiendishly difficult (but nevertheless polynomial-time) problem. The basic observation is that some platforms have too many incoming slides, while others have too many outgoing slides. If we can connect each of the former to one of the latter (by having Bessie walk from one to the other), then each platform has exactly as many incoming and outgoing routes. We are also guaranteed that the network is weakly connected, and together these facts guarantee the existence of a directed Eulerian cycle, which will take Bessie from platform 1 along each ride and each walking connection exactly once.

The problem is thus to find the minimum cost of connecting the platforms in this fashion. Suppose we have such an arrangement, in which A -> B and C -> D are two of the walking routes. If A < C and B > D (in terms of distance from the entrance), then A -> D, C -> B would achieve the same effect but at lower cost. It follows that the starting-points and ending-points of the walking routes must be ordered the same way in any optimal layout. We can thus construct an optimal layout by sorting both the starting and ending points, and pairing them up in this order.

#include <fstream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

#define MAXN 10000

int main() {
    int N, M;
    int pos[MAXN], deg[MAXN];
    ifstream in("slides.in");
    ofstream out("slides.out");

    in >> N >> M;
    for (int i = 0; i < N; i++) in >> pos[i];
    fill(deg, deg + N, 0);
    for (int i = 0; i < M; i++) {
        int x, y;
        in >> x >> y;
        x--;
        y--;
        deg[x]++;
        deg[y]--;
    }

    vector<int> start, stop;
    for (int i = 0; i < N; i++) {
        while (deg[i] > 0) { start.push_back(pos[i]); deg[i]--; }
        while (deg[i] < 0) { stop.push_back(pos[i]); deg[i]++; }
    }
    sort(start.begin(), start.end());
    sort(stop.begin(), stop.end());

    int ans = 0;
    for (size_t i = 0; i < start.size(); i++)
        ans += abs(start[i] - stop[i]);
    out << ans << "\n";
    return 0;
}