[UVA][二分maxflow] 10983 - Buy one, get the rest free＠Morris' Blog

2013-10-02 08:27:51| 人氣1,220| 回應0 | 上一篇 | 下一篇

[UVA][二分maxflow] 10983 - Buy one, get the rest free

推薦 0 收藏 0 轉貼0 訂閱站台

Problem B
Buy one, get the rest free.
Time Limit: 3 seconds

"Whoa! It feels like I'm flying!"

Lrrr

It's year 2258, and the age of airplanes is coming to an end. Everyone is using teleporters now. In an effort to stay competitive, the last remaining air travel company, GetsJo, is offering the following deal to its customers. Instead of buying one plane ticket, you can rent a whole flight from A to B. Each flight can carry a certain number of people and costs a certain amount of money. If you do that, then you can rent all of the other flights of equal or lesser cost for free!

For example, if there are 4 flights with costs $10000, $25000, $30000 and $40000, and you rent the $30000 flight, then you get the $10000 and $25000 flights for free. The total cost to rent these 3 flights is $30000.

You want to organize a large programming competition and would like to invite all of the participants to city n, where the competition will be held. Being a nice person, you decide to pay for everyone's airplane tickets. Given the locations of the participants and the list of available flights between now and the day of the competition, what is the cost of renting enough flights to get all of the participants to city n in the next d days?

Input
The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the number of cities (1<=n<=30), the number of days (1<=d<=10) until the competition and the number of flights (0<=m<=1000). m lines follow, each one containing 5 integers: u, v, c, p and e (1<=u,v<=n, 1<=c<=100, 0<=e<d). This means that a flight that can carry c passengers and costs p dollars leaves city u on day e in the evening and arrives next day in the morning to city v. Day 0 is today, and all of the participants need to be in city n in the evening of day e. Finally, n integers (z₁, z₂, ..., z_n) follow, meaning that there are z_i participants in city i on day 0 (0<=z_i<=100). The maximum cost of a flight is 100000. There will never be two flights with the same u, v and e values.

Output
For each test case, output one line containing "Case #x:" followed by the minimum required cost of flying all of the participants to city n before the end of day d. If no amount of money is enough, print "Impossible" instead.

Sample Input	Sample Output
2 5 4 5 1 5 100 30000 0 2 4 10 10000 0 2 4 10 10000 1 4 5 25 25000 2 2 5 100 40000 3 1 20 0 5 100 2 1 1 1 2 99 10400 0 100 0	Case #1: 30000 Case #2: Impossible

Problemsetter: Igor Naverniouk
Alternate solution: Yury Kholondyrev

題目描述：

訂機票的年代過去了，現在都是直接租飛機。

主辦單位要邀請各地參賽選手來到他們的比賽會場參賽，租用飛機的規則為：

花一筆錢後，小於等於這筆花費的飛機皆可以使用。

現在比賽辦在 d 天後，問能不能在此之前，把所有人帶過來。

飛機航線資訊為起站 u, 到站 v, 載客 c, 花費 p, 哪一天會飛 e

每個地點的參賽選手可能有很多位。

題目解法：

二分花費，每次二分建圖做最大流檢查。

根據每一地與天數，得到狀態 (days, place)。

1. source 連接 (0, place_i) 容量為 place_i 的參賽選手個數
2. (e, place_i) -> (e+1, place_i) 容量為 infinite，當天可能沒有飛機，要多等一天。
3. 飛機航線不用多說 (e, place_u) -> (e+1, place_v) 容量為 c。
4. (x, place_n) 全部連到 sink，容量為 infinite。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[50005];
int e, head[505], dis[505], prev[505], record[505];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
int maxflow(int s, int t) {
    int flow = 0;
    int i, j, x, y;
    while(1) {
        memset(dis, 0, sizeof(dis));
        dis[s] = 0xffff; // oo
        queue<int> Q;
        Q.push(s);
        while(!Q.empty()) {
            x = Q.front();
            Q.pop();
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(dis[y] == 0 && edge[i].v > 0) {
                    prev[y] = x, record[y] = i;
                    dis[y] = min(dis[x], edge[i].v);
                    Q.push(y);
                }
            }
            if(dis[t]) break;
        }
        if(dis[t] == 0) break;
        flow += dis[t];
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].v -= dis[t];
            edge[ri^1].v += dis[t];
        }
    }
    return flow;
}
int n, d, m;
int u[1005], v[1005], c[1005], p[1005], days[1005];
int z[1005];
int check(int cc) {//cost limit,
//each node(i, j) as i-days at j-citys, 0<=i<=d, 0<=j<n
    e = 0;
    memset(head, -1, sizeof(head));
    int i, j, k;
    int st = (d+1)*n, ed = st+1, tot = 0;
    for(i = 0; i < m; i++) {
        if(p[i] <= cc)
            addEdge(days[i]*n+u[i], (days[i]+1)*n+v[i], c[i]);
    }
    for(i = 0; i < n; i++) {
        for(j = 0; j < d; j++) {
            addEdge(j*n+i, (j+1)*n+i, 0xfffffff);//infinite = 0xfffffff
        }
    }
    for(j = 0; j <= d; j++)
        addEdge(j*n+n-1, ed, 0xfffffff);
    for(i = 0; i < n; i++) {
        addEdge(st, 0*n+i, z[i]);
        tot += z[i];
    }
    int mxflow = maxflow(st, ed);
    return tot == mxflow;
}
int main() {
    int testcase, cases = 0;
    int i, j, k;
    int binary_used[1005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d %d", &n, &d, &m);
        for(i = 0; i < m; i++) {
            scanf("%d %d %d %d %d", &u[i], &v[i], &c[i], &p[i], &days[i]);
            u[i]--, v[i]--;
            binary_used[i] = p[i];
        }
        for(i = 0; i < n; i++)
            scanf("%d", &z[i]);
        // process start.
        sort(binary_used, binary_used+m);
        for(i = 1, j = 0; i < m; i++)
            if(binary_used[i] != binary_used[j])
                binary_used[++j] = binary_used[i];
        int l = 0, r = j, mid;
        int ret = 0xfffffff;
        printf("Case #%d: ", ++cases);
        if(check(ret) == 0) {
            puts("Impossible");
            continue;
        }
        while(l <= r) {
            mid = (l+r)/2;
            if(check(binary_used[mid])) {
                ret = binary_used[mid];
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        printf("%d\n", ret);
    }
    return 0;
}

我要檢舉

#10983#Buy one#get the rest free#maxflow#二分

台長： Morris

您可能對以下文章有興趣

[UVA][math] 12517 - Digit Sum

d729. 10593 - Kites

[UVA][LinkedList] 540 - Team Queue

[UVA] 469 - Wetlands of Florida

人氣(1,220) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][二分貪婪] 12255 - Underwater Snipers
此分類上一篇:[UVA][二分匈牙利] 1221 - Against Mammoths

回應(0)