poj 2112 最优挤奶方案

Optimal Milking

Time Limit: 2000MS		Memory Limit: 30000K
Total Submissions: 16550		Accepted: 5945
Case Time Limit: 1000MS

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 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

水平太差，做这个题可谓是历经千辛万苦，差不多做了两天多。开始想要偷懒，一次见图，再DINIC种根据边的大小进行判断是否可以搜索，失败！然后改为每次建图，然后dinic,然后就OK了，提交的时候有出了个低级失误，在POJ提交时用的C++，结果提示“

Main.cpp
xlocale(1242) : fatal error C1088: Cannot flush compiler intermediate file: '_CL_75c8ace5ex': No space left on device

”磁盘空间不足，但是就懵了，尝试了N次才发现，我的智商啊！！！！

题目：floyd算出牛和挤奶器相互之间的最短距离，二分答案用最大流进行判断，如果最大流==牛数就可能是答案，否则不是。

代码如下：

  1 Source Code
  2 #include<cstdio>
  3 #include<iostream>
  4 #include<cstring>
  5 #include<vector>
  6 #include<queue>
  7 
  8 using namespace std;
  9 int k,c,m,ans;
 10 int map[240][240];
 11 int tu[240][240];
 12 int lays[240];
 13 int vis[240];
 14 void floyd()
 15 {
 16     for(int kk=1;kk<=k+c;kk++)
 17     for(int i=1;i<=k+c;i++)
 18     for(int j=1;j<=k+c;j++)
 19         if(map[i][kk]+map[kk][j]<map[i][j])
 20             map[i][j]=map[i][kk]+map[kk][j];
 21 }
 22 void mideg(int mid)
 23 {
 24     memset(tu,0,sizeof(tu));
 25     for(int i=1;i<=k;i++)
 26     {
 27         tu[0][i]=m;
 28         map[0][i]=1;
 29     }    
 30     for(int i=1;i<=k;i++)
 31     {
 32         for(int j=k+1;j<=k+c;j++)
 33         if(map[i][j]<=mid)
 34         tu[i][j]=1;
 35     }
 36     for(int i=k+1;i<=k+c;i++)
 37     {
 38         tu[i][k+c+1]=1;
 39         map[i][k+c+1]=1;
 40     }    
 41 }
 42 bool bfs()
 43 {
 44     memset(lays,-1,sizeof(lays));
 45     queue<int>q;
 46     q.push(0);
 47     lays[0]=0;
 48     while(!q.empty())
 49     {
 50         int u=q.front();
 51         q.pop();
 52         for(int i=0;i<=k+c+1;i++)
 53         {
 54             if(tu[u][i]>0&&lays[i]==-1)
 55             {
 56                 lays[i]=lays[u]+1;
 57                 if(i==k+c+1)return 1;
 58                 else q.push(i);
 59             }
 60         }
 61     }
 62     return 0;
 63 }
 64 bool dinic()
 65 {
 66     int maxf=0;
 67     vector<int>q;
 68     while(bfs())
 69     {
 70         memset(vis,0,sizeof(vis));
 71         q.push_back(0);
 72         vis[0]=1;
 73         while(!q.empty())
 74         {
 75             int nd=q.back();
 76             if(nd==k+c+1)
 77             {
 78                 int minn,minx=0x7fffffff;
 79                 for(int i=1;i<q.size();i++)
 80                 {
 81                     int u=q[i-1],v=q[i];
 82                     if(minx>tu[u][v])
 83                     {
 84                         minx=tu[u][v];
 85                         minn=u;
 86                     }
 87                 }
 88                 maxf+=minx;
 89                 for(int i=1;i<q.size();i++)
 90                 {
 91                     int u=q[i-1],v=q[i];
 92                     tu[u][v]-=minx;
 93                     tu[v][u]+=minx;
 94                 }
 95                 while(!q.empty()&&q.back()!=minn)
 96                 {
 97                     vis[q.back()]=0;
 98                     q.pop_back();
 99                 }
100             }
101             else
102             {
103                 int i;
104                 for(i=0;i<=k+c+1;i++)
105                 {
106                     if(tu[nd][i]>0&&!vis[i]&&lays[i]==lays[nd]+1)
107                     {
108                         q.push_back(i);
109                         vis[i]=1;
110                         break;
111                     }
112                 }
113                 if(i>k+c+1)q.pop_back();
114             }
115         }
116     }
117     return maxf==c;
118 }
119 int main()
120 {
121 
122     cin>>k>>c>>m;
123     memset(map,0x3f,sizeof(map));
124     for(int i=1;i<=k+c;i++)
125     for(int j=1;j<=k+c;j++)
126     {
127         int a;
128         scanf("%d",&a);
129         if(a)map[i][j]=a;
130         if(i==j)map[i][j]=0;
131     }
132     
133     floyd();
134 
135     int l=0,r=50000;
136     while(l<=r)
137     {
138         int mid=(l+r)/2;
139         mideg(mid);
140         bool pd=dinic();
141         if(pd)
142         {
143             ans=mid;
144             r=mid-1;
145         }
146         else
147         l=mid+1;
148     }
149     cout<<ans<<endl;
150     return 0;
151 }