解題區/解題區 - UVa

UVa 1049 - Remember the A La Mode

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

販售冰淇淋。

已知每一種口味的冰淇淋、不同種的冰淇淋脆皮的庫存量，也已知冰淇淋口味與脆皮之間搭配獲得的利益。

求出在兜售完畢的情況下，最大獲益、最小獲益分別為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
2 3 
40 50 
27 30 33 
1.11 1.27 0.70 
-1 2 0.34 
4 4 
10 10 10 10 
10 10 10 10 
1.01 -1 -1 -1 
-1 1.01 -1 -1 
-1 -1 1.01 -1 
-1 -1 -1 1.01 
0 0

Sample Output

1
2
Problem 1: 91.70 to 105.87 
Problem 2: 40.40 to 40.40

Solution

保證在兜售完畢的情況下，相當於 maxflow 流滿，那麼可以套用最少費用流來找到最少利益。為了解決最大獲益，取個補數來套用最少費用流模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define MAXN 2048
#define MAXM 1048576
struct Node {
    int x, y, cap;
    double cost;// x->y, v
    int next;
} edge[MAXM];
class MinCost {
public:
    int e, head[MAXN], pre[MAXN], record[MAXN], inq[MAXN];
    int dis[MAXN];
    int n;
    const int INF = 0x3f3f3f3f;
    void Addedge(int x, int y, int cap, int cost) {
        edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
        edge[e].next = head[x], head[x] = e++;
        edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
        edge[e].next = head[y], head[y] = e++;
    }
    pair<int, int> mincost(int s, int t) {
        int mncost = 0;
        int flow, totflow = 0;
        int i, x, y;
        while(1) {
        	for (int i = 0; i < n; i++)
        		dis[i] = INF;
            int oo = dis[0];
            dis[s] = 0;
            deque<int> Q;
            Q.push_front(s);
            while(!Q.empty()) {
                x = Q.front(), Q.pop_front();
                inq[x] = 0;
                for(i = head[x]; i != -1; i = edge[i].next) {
                    y = edge[i].y;
                    if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                        dis[y] = dis[x] + edge[i].cost;
                        pre[y] = x, record[y] = i;
                        if(inq[y] == 0) {
                            inq[y] = 1;
                            if(Q.size() && dis[Q.front()] > dis[y])
                                Q.push_front(y);
                            else
                                Q.push_back(y);
                        }
                    }
                }
            }
            if(dis[t] == oo)
                break;
            flow = 0x3f3f3f3f;
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                flow = min(flow, edge[ri].cap);
            }
            for(x = t; x != s; x = pre[x]) {
                int ri = record[x];
                edge[ri].cap -= flow;
                edge[ri^1].cap += flow;
                edge[ri^1].cost = -edge[ri].cost;
            }
            totflow += flow;
            mncost += dis[t] * flow;
        }
        return make_pair(mncost, totflow);
    }
    void init(int n) {
    	this->n = n;
        e = 0;
        for (int i = 0; i <= n; i++)
            head[i] = -1;
    }
} g;
int readDouble() {
    static char s[16];
    scanf("%s", s);
    if (s[0] == '-')	return -1;
    int i, x = 0;
    for (i = 0; s[i] && s[i] != '.'; i++)
        x = x * 10 + s[i] - '0';
    if (!s[i])	return x * 100;
    i++;
    x = x * 10 + s[i] - '0';
    if(!s[i+1]) return x * 10;
    i++;
    x = x * 10 + s[i] - '0';
    return x;
}
int main() {
    int N, M, Nsz[64], Msz[64], cases = 0;
    int NMp[64][64];
    while (scanf("%d %d", &N, &M) == 2 && N) {
    	
  		for (int i = 0; i < N; i++)
            scanf("%d", &Nsz[i]);
        for (int i = 0; i < M; i++)
        	scanf("%d", &Msz[i]);
        for (int i = 0; i < N; i++)
        	for (int j = 0; j < M; j++)
        		NMp[i][j] = readDouble();
        	
        int source = N + M, sink = N + M + 1;
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, NMp[i][j]);
        	}
        }
        pair<int, int> ret1 = g.mincost(source, sink);
        
        g.init(N + M + 2);
        for (int i = 0; i < N; i++) 
        	g.Addedge(source, i, Nsz[i], 0);
        for (int i = 0; i < M; i++) 
        	g.Addedge(i + N, sink, Msz[i], 0);
        	
        const int ADD = 50 * 100 * 2000;
        for (int i = 0; i < N; i++) {
        	for (int j = 0; j < M; j++) {
        		if (NMp[i][j] < 0) 	continue;
        		g.Addedge(i, j + N, 0x3f3f3f3f, ADD - NMp[i][j]);
        	}
        }
        pair<int, int> ret2 = g.mincost(source, sink);
        double r1, r2;
        r1 = ret1.first / 100.0;
        r2 = (ret2.second * ADD - ret2.first) / 100.0;
        printf("Problem %d: ", ++cases);
 		printf("%.2lf to %.2lf\n", r1, r2);
    }
    return 0;
}