poj2112 二分最大流+Floyd
最大 二分 Floyd
2023-09-11 14:14:00 时间
题意:
一个农场主有一些奶牛,和一些机器,每台机器有自己的服务上限,就是一天最多能给多少头奶牛挤奶,给你任意两点的距离,问你让所有的奶牛都被挤奶时,奶牛于机器最远距离的最近是多少。
思路:
一个农场主有一些奶牛,和一些机器,每台机器有自己的服务上限,就是一天最多能给多少头奶牛挤奶,给你任意两点的距离,问你让所有的奶牛都被挤奶时,奶牛于机器最远距离的最近是多少。
思路:
求最远的最近,二分,然后用最大流去判断是否所有的奶牛都被挤奶了,简单题目,不多解释了,还有注意一点就是二分前记得Floyd一下,他没说给的是最短距离。
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 250
#define N_edge 150000
#define INF 1000000000
using namespace std;
typedef struct
{
int to ,next ,cost;
}STAR;
typedef struct
{
int x ,t;
}DEP;
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node] ,map[N_node][N_node];
void add(int a ,int b ,int c)
{
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot;
}
int minn(int x ,int y)
{
return x < y ? x : y;
}
bool BFS_Deep(int s ,int t ,int n)
{
memset(deep ,255 ,sizeof(deep));
xin.x = s ,xin.t = 0;
deep[xin.x] = xin.t;
queue<DEP>q;
q.push(xin);
while(!q.empty())
{
tou = q.front();
q.pop();
for(int k = list[tou.x] ;k ;k = E[k].next)
{
xin.x = E[k].to;
xin.t = tou.t + 1;
if(deep[xin.x] != -1 || !E[k].cost)
continue;
deep[xin.x] = xin.t;
q.push(xin);
}
}
for(int i = 0 ;i <= n ;i ++)
listt[i] = list[i];
return deep[t] != -1;
}
int DFS_Flow(int s ,int t ,int flow)
{
if(s == t) return flow;
int nowflow = 0;
for(int k = listt[s] ;k ;k = E[k].next)
{
int to = E[k].to ,c = E[k].cost;
listt[s] = k;
if(deep[to] != deep[s] + 1 || !E[k].cost)
continue;
int tmp = DFS_Flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp;
if(nowflow == flow) break;
}
if(!nowflow) deep[s] = 0;
return nowflow;
}
int DINIC(int s ,int t ,int n)
{
int ans = 0;
while(BFS_Deep(s ,t ,n))
{
ans += DFS_Flow(s ,t ,INF);
}
return ans;
}
void Floyd(int n)
{
for(int k = 1 ;k <= n ;k ++)
for(int i = 1 ;i <= n ;i ++)
for(int j = 1 ;j <= n ;j ++)
map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]);
}
bool ok(int mid ,int K ,int C ,int M)
{
memset(list ,0 ,sizeof(list));
tot = 1;
for(int i = 1 ;i <= K ;i ++)
add(0 ,i ,M);
for(int i = 1 ;i <= K ;i ++)
for(int j = K + 1 ;j <= K + C ;j ++)
if(mid >= map[i][j]) add(i ,j ,1);
for(int i = 1 ;i <= C ;i ++)
add(i + K ,K + C + 1 ,1);
return DINIC(0 ,C + K + 1 ,C + K + 1) == C;
}
int main ()
{
int K ,C ,M;
int i ,j ,a;
while(~scanf("%d %d %d" ,&K ,&C ,&M))
{
for(i = 1 ;i <= K + C ;i ++)
for(j = 1 ;j <= K + C ;j ++)
{
scanf("%d" ,&map[i][j]);
if(!map[i][j]) map[i][j] = INF;
}
Floyd(K + C);
int Max = 0;
for(i = 1 ;i <= K ;i ++)
for(j = K + 1 ;j <= K + C ;j ++)
if(Max < map[i][j])Max = map[i][j];
int low = 0 ,up = Max ,mid ,ans;
while(low <= up)
{
mid = (low + up) >> 1;
if(ok(mid ,K ,C ,M))
{
up = mid - 1;
ans = mid;
}
else low = mid + 1;
}
printf("%d\n" ,ans);
}
return 0;
}
相关文章
- POJ 3228 二分最大流
- poj2112 二分最大流+Floyd
- POJ3228二分最大流
- POJ3189二分最大流(枚举下界,二分宽度,最大流判断可行性)
- 【BZOJ3291】Alice与能源计划 二分图最大匹配
- 【BZOJ3280】小R的烦恼 最小费用最大流
- uni-app - 单行文字和多行文字溢出隐藏显示...(超出容器最大宽度不换行)
- 凯文.凯利:最大的颠覆来自创业公司与边缘产业
- 史上最大的远程直播
- MYSQL最大连接数修改
- 如何从管理IT服务提供商获得最大收益
- [LeetCode]剑指 Offer 17. 打印从1到最大的n位数
- 七种常见分布式事务详解(2PC、3PC、TCC、Saga、本地事务表、MQ事务消息、最大努力通知)
- 华为OD机试 - 停车场最大距离(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 求数组中最大n个数和最小n个数的和(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 获取最大软件版本号(Python)| 真题+思路+考点+代码+岗位
- hdoj 5093 Battle ships 【二分图最大匹配】
- 分析师观点:WiFi将成为5G技术的最大竞争对手
- [LeetCode] 479. Largest Palindrome Product 最大回文串乘积
- Nimble Storage:全闪存阵列是财报中最大亮点
- 【bzoj3130】[Sdoi2013]费用流 二分+网络流最大流
- 【bzoj5085】最大 二分+暴力
- 【bzoj2044】三维导弹拦截 dp+二分图最大匹配
- 【bzoj3291】Alice与能源计划 模拟费用流+二分图最大匹配
- 【bzoj1532】[POI2005]Kos-Dicing 二分+网络流最大流
- 【bzoj4554】[Tjoi2016&Heoi2016]游戏 二分图最大匹配
- 【bzoj1059】[ZJOI2007]矩阵游戏 二分图最大匹配