好贷网好贷款

POJ 2112 Optimal Milking

发布时间:2016-12-4 22:23:36 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ 2112 Optimal Milking",主要涉及到POJ 2112 Optimal Milking方面的内容,对于POJ 2112 Optimal Milking感兴趣的同学可以参考一下。

Description 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 cowsand the milking machines. The milking machine locations are named by ID numbers1..K; the cow locations are named by ID numbers K+1..K+C.  Each milking point can "process" at most M (1 <= M <= 15) cowseach day.  Write a program to find an assignment for each cow to some milking machine sothat the distance the furthest-walking cow travels is minimized (and, ofcourse, the milking machines are not overutilized). At least one legalassignment is possible for all input data sets. Cows can traverse several pathson the way to their milking machine.  Input * Line 1: A singleline with three space-separated integers: K, C, and M.  * Lines 2.. ...: Each of these K+C lines of K+C space-separated integersdescribes the distances between pairs of various entities. The input forms asymmetric matrix. Line 2 tells the distances from milking machine 1 to each ofthe other entities; line 3 tells the distances from machine 2 to each of theother entities, and so on. Distances of entities directly connected by a pathare positive integers no larger than 200. Entities not directly connected by apath have a distance of 0. The distance from an entity to itself (i.e., allnumbers on the diagonal) is also given as 0. To keep the input lines ofreasonable length, when K+C > 15, a row is broken into successive lines of15 numbers and a potentially shorter line to finish up a row. Each new rowbegins on its own line.  Output A single line witha single integer that is the minimum possible total distance for the furthestwalking cow.  Sample Input 2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0 Sample Output 2   集训期间,实在太累,不写了。。。。。。待到开学再来慢慢写吧 #include <algorithm> #include <iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> using namespace std; #define INF 99999999 #define MAX 250 struct Edge { int st, ed; int next; int flow; } edge[MAX*MAX]; int k ,c ,m; int dis[250][250]; int head[MAX], out[MAX*MAX]; int stack[MAX*MAX], p[MAX*MAX]; int leve[MAX]; int Count, s, t ,sum ,ans; void build_edge ( int u, int v, long long flw ) { edge[Count].st = u; edge[Count].ed = v; edge[Count].flow = flw; edge[Count].next = head[u]; head[u] = Count++; }; bool BFS(int mid) { memset(leve,-1,sizeof(leve)); int front, rear, u, v, i; front = rear = 0; p[rear++] = s; leve[s] = 0; while(front!=rear) { u = p[front++]; for (i = head[u];i!=-1;i = edge[i].next ) { v = edge[i].ed; if(edge[i].flow > 0&&leve[v]==-1) { leve[v] = leve[u] + 1; p[rear++] = v; } } } return leve[t]!=-1; }; int Dinic (int mid) { int maxFlow = 0 ,re ,er; while (BFS(mid)) { int top = 0, u = s, i; for(i = s;i <= t;i++) { out[i] = head[i]; } while(out[s]!=-1) { er = out[u]; if(u==t) { int dd = INF; for (i = top - 1;i >=0;i--) { dd = min (edge[stack[i]].flow,dd); } for (i = top - 1;i >= 0;i--) { re = stack[i]; edge[re].flow -= dd; edge[re^1].flow += dd; if (edge[re].flow==0) { top = i; } } maxFlow += dd; u = edge[stack[top]].st; } else if (er!=-1&&edge[er].flow > 0&&leve[u] + 1==leve[edge[er].ed]) { stack[top++] = er; u = edge[er].ed; } else { while (top > 0&&u!=s&&out[u]==-1) { u = edge[stack[--top]].st; } out[u] = edge[out[u]].next; } } } return maxFlow; }; int main() { int no ,ans ,a; while(~scanf("%d%d%d",&k,&c,&m)) { no = k + c; memset(dis,0,sizeof(dis)); for(int i = 1;i<=no;i++) { for(int j = 1;j<=no;j++) { scanf("%d",&a); dis[i][j] = a; if(dis[i][j]==0) { dis[i][j] = INF; } } } for(int k = 1;k<=no;k++) { for(int i = 1;i<=no;i++) { for(int j = 1;j<=no;j++) { dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]); } } } int left = 0 ,right = 20000; s = 0 ,t = no + 1; ans = INF; while(left<=right) { int mid = (left + right) / 2; Count = 0; memset(head,-1,sizeof(head)); for(int i = k+1;i<=no;i++) { for(int j = 1;j<=k;j++) { if(dis[i][j] <= mid) { build_edge (i,j,1); build_edge (j,i,0); } } } for(int i = k + 1;i<=no;i++) { build_edge (0,i,1); build_edge (i,0,0); } for(int i = 1;i<=k;i++) { build_edge (i,no+1,m); build_edge (no+1,i,0); } if(Dinic(mid)!=c) { left = mid + 1; } else { right = mid - 1; if(ans > mid) { ans = mid; } } } printf("%d\n",ans); } return 0; }  

上一篇:程序员人生之路(分析的非常透彻!)http://www.open-open.com/news/view/233f5f
下一篇:Xcode 之nib文件

相关文章

相关评论