POJ 2112 Optimal Milking（二分+最大流）

题意：

现在有K台挤奶器和C头奶牛，奶牛和挤奶器之间有距离，每台挤奶器每天最多为M头奶挤奶，现在要安排路程，使得C头奶牛所走的路程中的最大路程最小。

思路：

很明显的二分题目。

源点和每头牛相连，容量为1。汇点和每台挤奶器相连，容量为M。

接下来每次二分枚举最大距离，然后在图中寻找每一条边，如果小于等于该最大距离，那么就将这条边加入图中，最后判断是否满流即可。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 using namespace std;
 12 typedef long long ll;
 13 typedef pair<int,int> pll;
 14 const int INF=0x3f3f3f3f3f;
 15 const int maxn=500+5;
 16 
 17 struct Edge
 18 {
 19     int from,to,cap,flow;
 20     Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){}
 21 };
 22 
 23 struct Dinic
 24 {
 25     int n,m,s,t;
 26     vector<Edge> edges;
 27     vector<int> G[maxn];
 28     bool vis[maxn];
 29     int cur[maxn];
 30     int d[maxn];
 31 
 32     void init(int n)
 33     {
 34         this->n=n;
 35         for(int i=0;i<n;++i) G[i].clear();
 36         edges.clear();
 37     }
 38 
 39     void AddEdge(int from,int to,int cap)
 40     {
 41         edges.push_back( Edge(from,to,cap,0) );
 42         edges.push_back( Edge(to,from,0,0) );
 43         m=edges.size();
 44         G[from].push_back(m-2);
 45         G[to].push_back(m-1);
 46     }
 47 
 48     bool BFS()
 49     {
 50         queue<int> Q;
 51         memset(vis,0,sizeof(vis));
 52         vis[s]=true;
 53         d[s]=0;
 54         Q.push(s);
 55         while(!Q.empty())
 56         {
 57             int x=Q.front(); Q.pop();
 58             for(int i=0;i<G[x].size();++i)
 59             {
 60                 Edge& e=edges[G[x][i]];
 61                 if(!vis[e.to] && e.cap>e.flow)
 62                 {
 63                     vis[e.to]=true;
 64                     d[e.to]=d[x]+1;
 65                     Q.push(e.to);
 66                 }
 67             }
 68         }
 69         return vis[t];
 70     }
 71 
 72     int DFS(int x,int a)
 73     {
 74         if(x==t || a==0) return a;
 75         int flow=0, f;
 76         for(int &i=cur[x];i<G[x].size();++i)
 77         {
 78             Edge &e=edges[G[x][i]];
 79             if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0)
 80             {
 81                 e.flow +=f;
 82                 edges[G[x][i]^1].flow -=f;
 83                 flow +=f;
 84                 a -=f;
 85                 if(a==0) break;
 86             }
 87         }
 88         return flow;
 89     }
 90 
 91     int Maxflow(int s,int t)
 92     {
 93         this->s=s; this->t=t;
 94         int flow=0;
 95         while(BFS())
 96         {
 97             memset(cur,0,sizeof(cur));
 98             flow +=DFS(s,0x3f3f3f3f);
 99         }
100         return flow;
101     }
102 }DC;
103 
104 
105 int k,c,m;
106 int g[maxn][maxn];
107 
108 void floyd()
109 {
110     for(int t=1;t<=k+c;t++)
111         for(int i=1;i<=k+c;i++)
112         for(int j=1;j<=k+c;j++)
113         g[i][j]=min(g[i][j],g[i][t]+g[t][j]);
114 }
115 
116 void solve(int dis)
117 {
118     int src=0,dst=k+c+1;
119     DC.init(dst+1);
120 
121     for(int i=1;i<=k;i++)
122         DC.AddEdge(i,dst,m);
123     for(int i=k+1;i<=k+c;i++)
124         DC.AddEdge(src,i,1);
125 
126     for(int i=1;i<=k;i++)
127     {
128         for(int j=k+1;j<=k+c;j++)
129             if(g[i][j]<=dis)  DC.AddEdge(j,i,1);
130     }
131 }
132 
133 int main()
134 {
135     //freopen("D:\input.txt","r",stdin);
136     while(scanf("%d%d%d",&k,&c,&m)!=EOF)
137     {
138         int L=0,R=0;
139         memset(g,0,sizeof(g));
140 
141         for(int i=1;i<=k+c;i++)
142         {
143             for(int j=1;j<=k+c;j++)
144             {
145                 scanf("%d",&g[i][j]);
146                 if(g[i][j]==0)  g[i][j]=INF;
147 
148             }
149         }
150 
151         floyd();
152 
153         for(int i=1;i<=k;i++)
154             for(int j=i+1;j<=k+c;j++)
155                if(g[i][j]!=INF) R=max(R,g[i][j]);
156 
157         int ans;
158         while(L<=R)
159         {
160             int mid=(L+R)/2;
161             solve(mid);
162             if(DC.Maxflow(0,k+c+1)==c)  {ans=mid;R=mid-1;}
163             else L=mid+1;
164         }
165         printf("%d
",ans);
166     }
167     return 0;
168 }