poj2112 网络流+二分答案
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 18083 | Accepted: 6460 | |
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
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int head[N],dis[N],tot,K,C,M,st,ed,mp[N][N];
struct node
{
int to,next,w;
} e[N*N*];
void add(int u,int v,int w)
{
e[tot].to=v;
e[tot].next=head[u];
e[tot].w=w;
head[u]=tot++;
}
void init()
{
tot=;
memset(head,-,sizeof(head));
}
bool bfs()
{
queue<int>Q;
memset(dis,-,sizeof(dis));
Q.push();
dis[]=;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=head[u]; i+; i=e[i].next)
{
int v=e[i].to;
if(dis[v]==-&&e[i].w>)
{
dis[v]=dis[u]+;
Q.push(v);
if(v==K+C+) return true;
}
}
}
return false;
}
int dfs(int s,int low)
{
if(s==ed||low==) return low;
int ans=low,a;
for(int i=head[s]; i+; i=e[i].next)
{
int v=e[i].to;
if(e[i].w>&&dis[v]==dis[s]+&&(a=dfs(v,min(ans,e[i].w))))
{
ans-=a;
e[i].w-=a;
e[i^].w+=a;
if(!ans) return low;
}
}
if(ans==low) dis[s]=-;
return low-ans;
}
void build(int lim)
{
init();
for(int i=; i<=K; ++i) for(int j=K+; j<ed; ++j) if(mp[i][j]<=lim&&mp[i][j])
{
add(i,j,);
add(j,i,);
}
for(int i=; i<=K; ++i) add(,i,M),add(i,,);
for(int i=K+; i<ed; ++i) add(i,ed,),add(ed,i,);
}
bool Ju()
{
int ans=;
while(bfs()) ans+=dfs(,);
if(ans==C) return true;
return false;
}
void Floyd()
{
for(int k=; k<ed; ++k) for(int i=; i<ed; ++i) if(mp[i][k]) for(int j=; j<ed; ++j) if(mp[k][j])
{
if(mp[i][j]==) mp[i][j]=mp[i][k]+mp[k][j];
else if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j];
}
}
int main()
{
while(scanf("%d%d%d",&K,&C,&M)!=EOF)
{
st=;
ed=K+C+;
for(int i=; i<ed; ++i) for(int j=; j<ed; ++j) scanf("%d",&mp[i][j]);
Floyd();
int r=,l=;
while(r!=l)
{
int mid=(r+l)>>;
build(mid);
if(Ju()) r=mid;
else l=mid+;
}
printf("%d\n",(l+r)>>);
}
}
最新文章
- [转]在html中控制自动换行
- html页面的绝对路径和相对路径
- PrintWriter 和 BufferedWriter 写入文件.
- The executable was signed with invalid entitlements.
- Eclipse搭建Android开发环境(安装ADT,Android4.4.2)(转)
- Android 从AndroidManifest获取meta-data
- 在标记的HREF属性中javascript:alert(this.innerHTML)会怎么样?
- Qt5:图片彩色键控,设置图片中指定颜色的像素为透明
- [BZOJ]1005 明明的烦恼(HNOI2008)
- redis基础篇
- Zabbix中获取各用户告警媒介分钟级统计
- chrome浏览器下载内容存放位置
- Mybatis 使用了哪些设计模式?
- 嵌入式开发之hi3519---lvds ,mipi,camera sensor,/DVI/HDMI Interface
- 第39级台阶|2013年蓝桥杯B组题解析第三题-fishers
- Linux命令对应英文全称
- kafka重复数据问题排查记录
- ajaxfileupload.js上传文件兼容IE7及以上版本
- linux socket talkclient talkserver示例
- http 中的 Get 与 Post