博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
bzoj1070题解
阅读量:5327 次
发布时间:2019-06-14

本文共 540 字,大约阅读时间需要 1 分钟。

【解题思路】

  考虑拆点,得到一个二分图:左边点<i,j>表示第i个技师按顺序第j辆修的车,右边点k表示第k个车主,连接左右的边表示第k个车主可能成为第i个技师的第j个客户。

  因为是二分图,所以直接跑KM即可,复杂度O(n3m);或者考虑费用流,左图都和源点连边,右图都和汇点连边,容费均为1,跑个流即可,复杂度O(松)。

【参考代码】

  费用流实现:

1 #pragma GCC optimize(2) 2 #include 
3 #include
4 #define REP(i,low,high) for(register int i=(low);i<=(high);i++) 5 #define INF 0x7f7f7f7f 6 using namespace std; 7 template
inline bool getmin(T &tar,const T &pat) {
return pat
View Code

 

转载于:https://www.cnblogs.com/spactim/p/6623446.html

你可能感兴趣的文章
Could not resolve view with name '***' in servlet with name 'dispatcher'
查看>>
[转载] redis 的两种持久化方式及原理
查看>>
MyBaits学习
查看>>
管道,数据共享,进程池
查看>>
[Cypress] Stub a Post Request for Successful Form Submission with Cypress
查看>>
SDUTOJ3754_黑白棋(纯模拟)
查看>>
php中的isset和empty的用法区别
查看>>
把word文档中的所有图片导出
查看>>
ubuntu 18.04取消自动锁屏以及设置键盘快捷锁屏
查看>>
正则表达式
查看>>
arcgis api 4.x for js 结合 Echarts4 实现散点图效果(附源码下载)
查看>>
YTU 2625: B 构造函数和析构函数
查看>>
apache自带压力测试工具ab的使用及解析
查看>>
加固linux
查看>>
WPF中Image显示本地图片
查看>>
Hyper-V虚拟机上安装一个图形界面的Linux系统
查看>>
js千分位处理
查看>>
字符串类型的相互转换
查看>>
基础学习:C#中float的取值范围和精度
查看>>
Vim配置Node.js开发工具
查看>>