POJ2112 Optimal Milking (网络流)(Dinic)
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 16461 | Accepted: 5911 | |
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 <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define inf 0x3f3f3f3f
#define mod 10000
typedef long long ll;
using namespace std;
const int N=;
const int M=;
int power(int a,int b,int c){int ans=;while(b){if(b%==){ans=(ans*a)%c;b--;}b/=;a=a*a%c;}return ans;}
int dis[N][N];
int w[N][N];
bool sign[N][N];
bool used[N];
int k,c,n,m;
void Build_Graph(int min_max)
{
memset(w,,sizeof(w));
for(int i=;i<=k;i++)w[][i]=m;
for(int i=k+;i<=n;i++)w[i][n+]=;
for(int i=;i<=k;i++){
for(int j=k+;j<=n;j++){
if(dis[i][j]<=min_max) w[i][j]=;
}
}
}
bool BFS()
{
memset(used,false,sizeof(used));memset(sign,,sizeof(sign));
queue<int>q;
q.push();used[]=true;
while(!q.empty()){
int t=q.front();q.pop();
for(int i=;i<=n+;i++){
if(!used[i]&&w[t][i]){
q.push(i);
used[i]=true;
sign[t][i]=;
}
}
}
if(used[n+])return true;
return false;
}
int DFS(int v,int sum)
{
if(v==n+)return sum;
int s=sum,t;
for(int i=;i<=n+;i++){
if(sign[v][i]){
t=DFS(i,min(w[v][i],sum));
w[v][i]-=t;
w[i][v]+=t;
sum-=t;
}
}
return s-sum;
}
int main()
{
scanf("%d%d%d",&k,&c,&m);
n=k+c;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&dis[i][j]);
if(!dis[i][j])dis[i][j]=inf;
}
}
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
if(dis[i][k]!=inf){
for(int j=;j<=n;j++){
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
}
int l=,r=;
while(l<r){
int mid=(l+r)/;
int ans=;
Build_Graph(mid);
while( BFS() )ans+=DFS(,inf);//Dinic求最大流
if(ans>=c) r=mid;
else l=mid+;
}
printf("%d\n",r);
return ;
}
最新文章
- iOS 强制退出程序APP代码
- oracle去除重复字段
- redis常用命令、常见错误、配置技巧等分享
- [纯干货] MySQL索引背后的数据结构及算法原理
- 那天有个小孩跟我说LINQ(八)学会Func
- 微信公众平台开发3:订阅事件subscribe处理
- php删除多重数组对象属性,重新赋值的方法
- 搭建hdfs服务器集群的搭建+trash
- android真机调试
- document.write 存在几个问题?应该注意
- Oracle数据库top10物理段
- Java学习之道:空指针错误求解救????????????
- Linux之VI搜索相关命令
- SpringAop源码情操陶冶-JdkDynamicAopProxy
- 去除 chrome 上保存密码后的 input 框的屎黄色背景
- 42.PHP--电商网站的询价插件
- Zabbix poller processes more than 75% busy
- javascript函数以及作用域简介
- java代码分析及分析工具
- mysql5.7.22的安装与配置(适用mysql5.7.20至mysql5.7.22版本)
热门文章
- [转]android Intent机制详解
- kali linux SET工具包
- adaboost算法
- oracle 之关键字exists
- Note_Master-Detail Application(iOS template)_06_ YJYDetailViewController.h
- Python网络编程03----Python3.*中socketserver
- 使用respondsToSelector:来发现对象是否响应消息
- js 微信分享
- 【LeetCode OJ】LRU Cache
- Date and Time