解題區/解題區 - UVa

UVa 1006 - Fixed Partition Memory Management

contents

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

Problem

每個程式會有在不同的空間限制下會有不同的運行時間，現在給定 N 個內存池，M 個程式，每個程式只能在一個內存池下運行，並且同一個時間內存池內最多有一個程式。

最平均運行時間最少為何。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Case 1
Average turnaround time = 7.75
Program 1 runs in region 1 from 0 to 4
Program 2 runs in region 2 from 0 to 3
Program 3 runs in region 1 from 4 to 14
Program 4 runs in region 2 from 3 to 10
Case 2
Average turnaround time = 35.40
Program 1 runs in region 2 from 25 to 55
Program 2 runs in region 2 from 0 to 25
Program 3 runs in region 3 from 0 to 19
Program 4 runs in region 3 from 19 to 60
Program 5 runs in region 1 from 0 to 18

Solution

平均最少時間的計算，就是拿每個程式的運行結束時間加總取平均。

但是必須累計到前一個在內存池運行的程式時間，這一點必須轉換成最少費用流模型。

事實上，換個角度想，假使排定程式 A 運行，而後會有 B, C 程式，那麼 A 的運行時間會累計到三次，而 B 會被累計到兩次。也就是說，內存池每一個程式的時間加總會分配到 1 ~ N 個程式重複計數。

因此模型為 source - program - [memory_pool, count] - sink。

輸出的時候，在內存池被累計越多次的程式應該越早執行。

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
#include <stdio.h>
#include <string.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
struct Node {
    int x, y, cap, cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], dis[600], prev[600], record[600], inq[600];
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++;
}
int mincost(int s, int t) {
    int mncost = 0, flow, totflow = 0;
    int i, x, y;
    while(1) {
        memset(dis, 63, sizeof(dis));
        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;
                    prev[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 = oo;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[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 mncost;
}
int main() {
    int n, m, cases = 0;
    int x, y, d, a;
    int mem[128], needmem[128][128], runtime[128][128], ch[128];
    
    while(scanf("%d %d", &n, &m) == 2 && n+m) {
    	for (int i = 0; i < n; i++)
    		scanf("%d", &mem[i]);
    	for (int i = 0; i < m; i++) {
    		scanf("%d", &ch[i]);
    		for (int j = 0; j < ch[i]; j++)
    			scanf("%d %d", &needmem[i][j], &runtime[i][j]);
    		needmem[i][ch[i]] = 0x3f3f3f3f;
    	}
    	
        e = 0;
        memset(head, -1, sizeof(head));
        int source = n*m + m + 1, sink = n*m + m + 2;
        for (int i = 0; i < m; i++) {
        	addEdge(source, i, 1, 0);
        	for (int j = 0; j < ch[i]; j++) {
        		for (int k = 0; k < n; k++) {
        			if (needmem[i][j] <= mem[k] && mem[k] <= needmem[i][j+1]) {
        				for (int p = 0; p < m; p++)
        					addEdge(i, m + k * m + p, 1, runtime[i][j] * (p + 1));
        			}
        		}
        	}
        }
        for (int i = 0; i < n; i++)
        	for (int j = 0; j < m; j++)
        		addEdge(m + i * m + j, sink, 1, 0);
        
        double cost = mincost(source, sink);
        int prog[128], from[128] = {}, run[128];
        vector< pair<int, int> > runtable[128];
        for (int i = 0; i < m; i++) {
        	for (int j = head[i]; j != -1; j = edge[j].next) {
        		if (edge[j].cap == 0 && edge[j].y >= m && edge[j].y < m + n*m) {
        			prog[i] = (edge[j].y - m) / m;
        			run[i] = edge[j].cost / ((edge[j].y - m) % m + 1);
        			runtable[prog[i]].push_back(make_pair((edge[j].y - m) % m, i));
        			break;
        		}
        	}
        }
        for (int i = 0; i < n; i++) {
        	sort(runtable[i].begin(), runtable[i].end(), greater< pair<int, int> >());
        	for (int j = 1; j < runtable[i].size(); j++)
        		from[runtable[i][j].second] = from[runtable[i][j-1].second] + run[runtable[i][j-1].second];
        }
        printf("Case %d\n", ++cases);
        printf("Average turnaround time = %.2lf\n", (double) cost / m);
        for (int i = 0; i < m; i++) {
        	printf("Program %d runs in region %d from %d to %d\n", i+1, prog[i]+1, from[i], from[i] + run[i]);
        }
        puts("");
    }
    return 0;
}
/*
2 4
40 60
1 35 4
1 20 3
1 40 10
1 60 7
3 5
10 20 30
2 10 50 12 30
2 10 100 20 25
1 25 19
1 19 41
2 10 18 30 42
0 0
*/