POJ 2112 Optimal Milking

时间：2014-09-16 23:37:01 阅读：546 评论：0 收藏：0 [点我收藏+]

Optimal Milking

Time Limit: 2000ms

Memory Limit: 30000KB

This problem will be judged on PKU. Original ID: 2112
64-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.

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.

Output

A single line with a single integer that is the minimum possible total distance for the furthest walking cow.

Sample Input

Sample Output

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 }

View Code

加速版

  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 }

View Code

POJ 2112 Optimal Milking

原文：http://www.cnblogs.com/crackpotisback/p/3975930.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)