poj 2112(二分+网络流)
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 15749 | Accepted: 5617 | |
Case Time Limit: 1000MS |
Description
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
* 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
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
题意:有K台挤奶机,C头奶牛,每台挤奶机可以容纳M头奶牛,挤奶机和奶牛两两之间都有个距离,现在问在保证所有的奶牛都可以产奶的情况下,走到挤奶机需要走最远的奶牛的最短要走的距离是多少?
题解:先用floyed算法算出每头奶牛和挤奶机之间的最短路径,在保证所有奶牛都能够产奶的情况下二分求解,设立超级源点S,S向每台挤奶机之间连容量为M的边,每台挤奶机向奶牛连容量为1的边,所有奶牛
向超级汇点连容量为1的边,求解最大流。
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include <iostream>
#include <math.h>
using namespace std;
const int N = ;
const int INF = ;
struct Edge
{
int v,next;
int w;
} edge[N*N];
int head[N];
int level[N];
int tot;
void init()
{
memset(head,-,sizeof(head));
tot=;
}
void addEdge(int u,int v,int w,int &k)
{
edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;
edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;
}
int BFS(int src,int des)
{
queue<int >q;
memset(level,,sizeof(level));
level[src]=;
q.push(src);
while(!q.empty())
{
int u = q.front();
q.pop();
if(u==des) return ;
for(int k = head[u]; k!=-; k=edge[k].next)
{
int v = edge[k].v;
int w = edge[k].w;
if(level[v]==&&w!=)
{
level[v]=level[u]+;
q.push(v);
}
}
}
return -;
}
int dfs(int u,int des,int increaseRoad)
{
if(u==des||increaseRoad==) return increaseRoad;
int ret=;
for(int k=head[u]; k!=-; k=edge[k].next)
{
int v = edge[k].v,w=edge[k].w;
if(level[v]==level[u]+&&w!=)
{
int MIN = min(increaseRoad-ret,w);
w = dfs(v,des,MIN);
if(w > )
{
edge[k].w -=w;
edge[k^].w+=w;
ret+=w;
if(ret==increaseRoad) return ret;
}
else level[v] = -;
if(increaseRoad==) break;
}
}
if(ret==) level[u]=-;
return ret;
}
int Dinic(int src,int des)
{
int ans = ;
while(BFS(src,des)!=-) ans+=dfs(src,des,INF);
return ans;
}
int graph[N][N];
int k,c,m;
int floyed(int n)
{
int MAX=-;
for(int k=; k<=n; k++)
{
for(int i=; i<=n; i++)
{
for(int j=; j<=n; j++)
{
graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j]);
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(graph[i][j]!=INF)
MAX = max(MAX,graph[i][j]);
}
}
return MAX;
}
int build(int v){
init();
int src = ,des = k+c+;
for(int i=;i<=k;i++) addEdge(src,i,m,tot);
for(int i=k+;i<=k+c;i++) addEdge(i,des,,tot);
for(int i=;i<=k;i++){
for(int j=k+;j<=k+c;j++){
if(graph[i][j]<=v) addEdge(i,j,,tot);
}
}
return Dinic(src,des);
}
int main()
{
while(scanf("%d%d%d",&k,&c,&m)!=EOF)
{
for(int i=;i<=k+c;i++){
for(int j=;j<=k+c;j++){
scanf("%d",&graph[i][j]);
if(graph[i][j]==&&i!=j) graph[i][j] = INF;
}
}
int MAX = floyed(k+c);
int l=,r = MAX;
int ans = MAX;
while(l<=r){
int mid = (l+r)>>;
if(build(mid)==c) {
ans = mid;
r = mid-;
}
else l =mid+;
}
printf("%d\n",ans);
}
}
最新文章
- 转:MVC 数据验证
- mysql 表迁移
- WCF + EF 遇到的问题
- phpstorm配置Xdebug进行调试PHP教程
- highgui.h备查 分类: C/C++ OpenCV 2014-11-08 18:11 292人阅读 评论(0) 收藏
- gcc编译时头文件库文件搜索顺序(转)
- google 历史版本浏览器下载
- 基本的CRUD操作
- Maven——settings.xml配置
- C# 反编译
- jenkins Pipeline 使用
- 插件Vue.Draggable(5000&#127775;)
- Flask从入门到精通之Flask-Moment本地化日期和时间
- SQL事务在存储过程的应用
- 20155234 2016-2017-2《Java程序设计》课程总结
- linux shell 正则表达式(BREs,EREs,PREs)的比较
- centos6.5挂载windows共享的文件夹
- Web Tracking
- 如何修改element.style样式
- 全面了解linux服务器
热门文章
- nmap命令扫描存活主机
- 12864点阵液晶显示模块的原理和实例程序(HJ12864M-1)
- Java中对象方法的调用过程&;动态绑定(Dynamic Binding)
- 利用Windbg深入理解变量的存储模型
- luogu3369 【模板】普通平衡树(Treap/SBT) treap splay
- __block 和__weak
- Python面试题(练习一)
- HTTP的一些概念
- 精通CSS高级Web标准解决方案(2-1 可视化格式模型之框模型)
- [错误解决]Ubuntu中使用dpkg安装deb文件提示依赖关系问题,仍未被配置