首页 > 代码库 > POJ 2112 Optimal Milking
POJ 2112 Optimal Milking
Optimal Milking
Time Limit: 2000ms
Memory Limit: 30000KB
This problem will be judged on PKU. Original ID: 211264-bit integer IO format: %lld Java class name: Main
FJ has moved his K (1 <= K <= 30) milking machines out into the cow pastures among the C (1 <= C <= 200) cows. A set of paths of various lengths runs among the cows and the milking machines. The milking machine locations are named by ID numbers 1..K; the cow locations are named by ID numbers K+1..K+C.
Each milking point can "process" at most M (1 <= M <= 15) cows each day.
Write a program to find an assignment for each cow to some milking machine so that the distance the furthest-walking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine.
Each milking point can "process" at most M (1 <= M <= 15) cows each day.
Write a program to find an assignment for each cow to some milking machine so that the distance the furthest-walking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine.
Input
* Line 1: A single line with three space-separated integers: K, C, and M.
* Lines 2.. ...: Each of these K+C lines of K+C space-separated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.
* Lines 2.. ...: Each of these K+C lines of K+C space-separated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line.
Output
A single line with a single integer that is the minimum possible total distance for the furthest walking cow.
Sample Input
2 3 20 3 2 1 13 0 3 2 02 3 0 1 01 2 1 0 21 0 0 2 0
Sample Output
2
Source
USACO 2003 U S Open
解题：建图是关键啊。有K台挤奶器，C头奶牛，使得奶牛到最远的挤奶器最近。二分距离。如何建图？Floyd求出奶牛到最近的挤奶器的距离。还是建图吧。源点连每头奶牛，流量为1，二分距离，选择距离不大于所二分的距离的奶牛连接挤奶器，流量无限，然后挤奶器连汇点，流量为m。因为每台挤奶器每天最多为m头奶牛服务。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 500; 18 struct arc { 19 int to,flow,next; 20 arc(int x = 0,int y = 0,int z = 0) { 21 to = x; 22 flow = y; 23 next = z; 24 } 25 }; 26 int K,C,M,S,T,tot,mp[maxn][maxn],head[maxn],d[maxn]; 27 arc e[200000]; 28 void add(int u,int v,int flow) { 29 e[tot] = arc(v,flow,head[u]); 30 head[u] = tot++; 31 e[tot] = arc(u,0,head[v]); 32 head[v] = tot++; 33 } 34 void Floyd() { 35 for(int k = 1; k <= K+C; k++) { 36 for(int i = 1; i <= K+C; i++) { 37 for(int j = 1; mp[i][k] < INF && j <= K+C; j++) 38 if(mp[k][j] < INF && mp[i][j] > mp[i][k]+mp[k][j]) 39 mp[i][j] = mp[i][k] + mp[k][j]; 40 } 41 } 42 } 43 queue<int>q; 44 bool bfs() { 45 memset(d,0,sizeof(d)); 46 while(!q.empty()) q.pop(); 47 d[S] = 1; 48 q.push(S); 49 while(!q.empty()) { 50 int u = q.front(); 51 q.pop(); 52 for(int i = head[u]; ~i; i = e[i].next) { 53 if(e[i].flow > 0 && !d[e[i].to]) { 54 d[e[i].to] = d[u] + 1; 55 q.push(e[i].to); 56 } 57 } 58 } 59 return d[T] > 0; 60 } 61 int dfs(int u,int low) { 62 if(u == T) return low; 63 int tmp = 0,a; 64 for(int i = head[u]; ~i; i = e[i].next) { 65 if(d[e[i].to] == d[u] + 1 && (a = dfs(e[i].to,min(low,e[i].flow)))) { 66 tmp += a; 67 e[i].flow -= a; 68 e[i^1].flow += a; 69 low -= a; 70 if(!low) break; 71 } 72 } 73 return tmp; 74 } 75 int Dinic() { 76 int tmp = 0; 77 while(bfs()) tmp += dfs(S,INF); 78 return tmp; 79 } 80 int main() { 81 int low,high,mid; 82 while(~scanf("%d %d %d",&K,&C,&M)) { 83 low = INF; 84 high = 0; 85 for(int i = 1; i <= K+C; i++) { 86 for(int j = 1; j <= K+C; j++) { 87 scanf("%d",mp[i]+j); 88 if(!mp[i][j]) mp[i][j] = INF; 89 } 90 } 91 Floyd(); 92 S = 0; 93 T = K + C + 1; 94 for(int i = 1; i <= K+C; i++) 95 for(int j = i+1; j <= K+C; j++) 96 if(mp[i][j] < INF) { 97 low = min(low,mp[i][j]); 98 high = max(high,mp[i][j]); 99 }100 while(low < high) {101 mid = (low+high)>>1;102 memset(head,-1,sizeof(head));103 for(int i = K+1; i <= K+C; i++) {104 add(S,i,1);105 for(int j = 1; j <= K; j++) {106 if(mp[i][j] <= mid) {add(i,j,INF);}107 }108 }109 for(int i = 1; i <= K; i++) add(i,T,M);110 int Flow = Dinic();111 if(Flow < C) low = mid+1;112 else high = mid;113 }114 printf("%d\n",low);115 }116 return 0;117 }
加速版
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 250; 18 struct arc { 19 int to,flow,next; 20 arc(int x = 0,int y = 0,int z = 0) { 21 to = x; 22 flow = y; 23 next = z; 24 } 25 }; 26 int K,C,M,S,T,tot,mp[maxn][maxn],head[maxn],d[maxn],cur[maxn]; 27 arc e[20000]; 28 void add(int u,int v,int flow) { 29 e[tot] = arc(v,flow,head[u]); 30 head[u] = tot++; 31 e[tot] = arc(u,0,head[v]); 32 head[v] = tot++; 33 } 34 void Floyd() { 35 for(int k = 1; k <= K+C; k++) { 36 for(int i = 1; i <= K+C; i++) { 37 for(int j = 1; mp[i][k] < INF && j <= K+C; j++) 38 if(mp[k][j] < INF && mp[i][j] > mp[i][k]+mp[k][j]) 39 mp[i][j] = mp[i][k] + mp[k][j]; 40 } 41 } 42 } 43 queue<int>q; 44 bool bfs() { 45 memset(d,-1,sizeof(d)); 46 while(!q.empty()) q.pop(); 47 d[S] = 0; 48 q.push(S); 49 while(!q.empty()) { 50 int u = q.front(); 51 q.pop(); 52 for(int i = head[u]; ~i; i = e[i].next) { 53 if(e[i].flow > 0 && d[e[i].to] < 0) { 54 d[e[i].to] = d[u] + 1; 55 q.push(e[i].to); 56 } 57 } 58 } 59 return d[T] > -1; 60 } 61 int dfs(int u,int low) { 62 if(u == T) return low; 63 int tmp = 0,a; 64 for(int &i = cur[u]; ~i; i = e[i].next) { 65 if(e[i].flow && d[e[i].to] == d[u] + 1 && (a = dfs(e[i].to,min(low,e[i].flow)))) { 66 tmp += a; 67 e[i].flow -= a; 68 e[i^1].flow += a; 69 low -= a; 70 if(!low) break; 71 } 72 } 73 if(tmp == 0) d[u] = -1; 74 return tmp; 75 } 76 int Dinic() { 77 int tmp = 0; 78 while(bfs()) { 79 for(int i = 0; i <= T; i++) 80 cur[i] = head[i]; 81 tmp += dfs(S,INF); 82 } 83 return tmp; 84 } 85 int main() { 86 int low,high,mid; 87 while(~scanf("%d %d %d",&K,&C,&M)) { 88 low = INF; 89 high = 0; 90 for(int i = 1; i <= K+C; i++) { 91 for(int j = 1; j <= K+C; j++) { 92 scanf("%d",mp[i]+j); 93 if(!mp[i][j]) mp[i][j] = INF; 94 } 95 } 96 Floyd(); 97 S = 0; 98 T = K + C + 1; 99 for(int i = 1; i <= K+C; i++)100 for(int j = i+1; j <= K+C; j++)101 if(mp[i][j] < INF) {102 low = min(low,mp[i][j]);103 high = max(high,mp[i][j]);104 }105 while(low < high) {106 mid = (low+high)>>1;107 memset(head,-1,sizeof(head));108 tot = 0;109 for(int i = K+1; i <= K+C; i++) {110 add(S,i,1);111 for(int j = 1; j <= K; j++) {112 if(mp[i][j] <= mid) {113 add(i,j,INF);114 }115 }116 }117 for(int i = 1; i <= K; i++) add(i,T,M);118 if(Dinic() < C) low = mid+1;119 else high = mid;120 }121 printf("%d\n",low);122 }123 return 0;124 }
POJ 2112 Optimal Milking
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。