博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj 2455 Secret Milking Machine
阅读量:6764 次
发布时间:2019-06-26

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

题意:有N个点,之间有P条路(双向),要求每次从1到N走不同的路T次,求这T次中两点间路最长的一条

思路:二分+最大流,如果两点之间有路,就建立流量为1的网络,然后二分路径长度,从新建立符合要求的图,求最大流

注意重边的情况,如果是邻接表没事,否则注意,边不是取最小,要都存下,因为有可能都符合要求,WA了很多次都是错在这了

三个小时就这么没了……今天一早,看出了原因了,于是用vector解决了,明显很慢啊,不知道是不是模板的原因……

核心code:

vector
map[nMax][nMax];  //原始图 void rebuild(int mid) {
memset(G, 0, sizeof(G)); memset(F, 0, sizeof(F));  //流 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) {
int tt=map[i][j].size(); for(int t=0; t
Min) {
mid=(Max+Min)/2; rebuild(mid); //cout<
<<" "; flow=find_max_flow(); if(flow>=t) Max=mid; else Min=mid+1; } printf("%d\n", Max); return 0; }

 

转载于:https://www.cnblogs.com/FreeAquar/archive/2011/08/18/2144149.html

你可能感兴趣的文章
JavaScript权威指南笔记
查看>>
R语言分析nginx日志
查看>>
android启动activity文本框不获得焦点
查看>>
linux运维实战练习-2015年8月30日课程作业(练习)安排
查看>>
给新手的最佳类Windows界面的Linux发行版
查看>>
Centos7下按照配置nexus2
查看>>
第13章 使用Bind提供域名解析服务
查看>>
MT47H64M16NF-25EM相关参数介绍
查看>>
C# FileStream简单介绍和使用
查看>>
我的友情链接
查看>>
Centos7 mount/ rpm/ yum 软件仓库搭建
查看>>
EC2上源安装vnstat
查看>>
高性能Web服务之varnish应用详解及实战应用
查看>>
我的友情链接
查看>>
Docker容器管理--CentOS7安装docker
查看>>
CentOS 6网卡名称修改 以及 centos7 采用传统命名方式
查看>>
Maven 中的jar包冲突
查看>>
lvs基于fwm定义集群服务
查看>>
awk 系列Part3:如何使用 awk 按模式筛选文本或字符串
查看>>
用cxfreeze打包Python3.3成exe文件
查看>>