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

本文共 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

你可能感兴趣的文章
转:在VS2010下编译、调试和生成mex文件
查看>>
知识分析作业(二)-----朴素贝叶斯
查看>>
学了N年英语,你学会翻译了吗?——最基本的数据库连接
查看>>
lunix安装
查看>>
三.文件与目录基本指令
查看>>
ACM HDU 1094
查看>>
2012CSU_ACM集训中期检测 简要题解
查看>>
DOS命令如何进入指定的下一级目录?
查看>>
svn 系统找不到路径
查看>>
python——continue的应用
查看>>
Android应用开发实例篇(1)-----简易涂鸦板
查看>>
System V 信号量
查看>>
js提交成功后,清空表单
查看>>
随机变量的期望和方差
查看>>
求正弦型函数的参数的取值范围
查看>>
rabbits php实现文件下载!
查看>>
关于抽象类和接口的讨论
查看>>
PHP计算每月几周,每周的开始结束日期
查看>>
业务流程图怎么画
查看>>
html字符字体转换
查看>>