首页 > POJ 2455Secret Milking Machine（二分+网络流之最大流）

POJ 2455Secret Milking Machine（二分+网络流之最大流）

题目地址：POJ2455

手残真浪费时间啊。。又拖到了今天才找出了错误。。每晚两道题不知不觉又变回了每晚一道题、。。sad。。

第一次在isap中忘记调用bfs，第二次则是遍历的时候竟然是从1開始遍历的。。。sad。。。

这题思路倒是非常easy，就是有一个比較坑的地方，就是这里的重边要当两条边来用，曾经受最短路什么的影响，直接把慢的删了，非常明显不正确。。。这里的两条重边都是能够走的。

建图思路是，将1当作源点，将n当作汇点。右边的地方就连边，注意是无向边。最后推断最大流是否等于道路条数。二分找最小值。

代码例如以下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include using namespace std;
const int INF=1e9;
int head[500], s, t, nv, cnt, sum;
int num[500], d[500], pre[500], cur[500], q[500];
struct node
{int u, v, cap, next;
}edge[5000000];
struct N
{int u, v, w;
}bian[5000000];
void add(int u, int v, int cap)
{edge[cnt].v=v;edge[cnt].cap=cap;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].v=u;edge[cnt].cap=cap;edge[cnt].next=head[v];head[v]=cnt++;
}
void bfs()
{memset(num,0,sizeof(num));memset(d,-1,sizeof(d));int f1=0, f2=0, i;q[f1++]=t;d[t]=0;num[0]=1;while(f1>=f2){int u=q[f2++];for(i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(d[v]==-1){d[v]=d[u]+1;num[d[v]]++;q[f1++]=v;}}}
}
int isap()
{memcpy(cur,head,sizeof(cur));int flow=0, u=pre[s]=s, i;bfs();while(d[s]edge[cur[i]].cap){f=edge[cur[i]].cap;pos=i;}}for(i=s;i!=t;i=edge[cur[i]].v){edge[cur[i]].cap-=f;edge[cur[i]^1].cap+=f;}flow+=f;if(flow>=sum){return flow;}u=pos;}for(i=cur[u];i!=-1;i=edge[i].next){if(d[edge[i].v]+1==d[u]&&edge[i].cap){break;}}if(i!=-1){cur[u]=i;pre[edge[i].v]=u;u=edge[i].v;}else{if(--num[d[u]]==0) break;int mind=nv;for(i=head[u];i!=-1;i=edge[i].next){if(mind>d[edge[i].v]&&edge[i].cap){mind=d[edge[i].v];cur[u]=i;}}d[u]=mind+1;num[d[u]]++;u=pre[u];}}return flow;
}
int main()
{int n, p, a, b, c, i, j, top;while(scanf("%d%d%d",&n,&p,&sum)!=EOF){top=0;while(p--){scanf("%d%d%d",&a,&b,&c);bian[top].u=a;bian[top].v=b;bian[top++].w=c;}int high=1000001, mid, low=1, ans, x;while(low<=high){mid=(high+low)/2;s=1;t=n;nv=t+1;memset(head,-1,sizeof(head));cnt=0;for(i=0;i=sum){ans=mid;high=mid-1;}else{low=mid+1;}}printf("%d
",ans);}return 0;
}




更多相关：

  • 数据结构 -- 图与图存储

    我们在使用像QQ ，微信，微博，快手，抖音等社交软件的过程中经常需要添加好友，关注好友和被好友关注。这个过程中 这样的社交网络中的好友关系就需要被存储下来，存储在各个公司的后台服务器之上，都会作为每个公司的数据资产来进行自己核心业务的开发（视频推荐、好友推荐。。。） 这个用来保存好友关系的数据结构就是 图，接下来探索一下这个非线性数...

  • vijos 1476 旅游规划题解

    题目链接：https://vijos.org/p/1476 解：因为这一定是一棵树，所以我们多画几次图，就会发现所有的最长路径中心点都一样，且中心点把这条最长路径分成两段等长的路。 那么做法就很简单啦，先求出图的最长路径长度（称为直径），然后找到中心点（如果最长路径长度为偶数的话，就新建一个点，连上中间的两个点，并把原来两点间的路径删...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 二维指针操作链表

    背景 Linus slashdot:    https://meta.slashdot.org/story/12/10/11/0030249 Linus大婶在slashdot上回答一些编程爱好者的提问，其中一个人问他什么样的代码是他所喜好的，大婶表述了自己一些观点之后，举了一个指针的例子，解释了什么才是core low-level...

  • leetcode-386 字典序排数

    给定一个整数 n, 返回从 1 到 n 的字典顺序。 例如， 给定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。 请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。 根据题目描述，所谓字典顺序，即数值按照类似字符串首字母的ASCII大小进行排序...

  • 二叉树 2.0 -- 非递归遍历

    二叉树递归遍历存在的问题 如果我们的二叉树只有左子树，而且树的高度还很深的时候，这个时候递归调用遍历的时候，栈帧空间开辟的较大，很可能造成栈溢出。但是我们一个程序中，为堆分配的空间要比栈大的多，这个时候我们可以实现一个二叉树遍历的非递归的实现形式，模拟栈帧调用的过程，自己模拟一个栈用于保存节点，然后实现遍历。 非递归实现树的遍历...

  • BZOJ 3085: 反质数加强版SAPGAP （反素数搜索）

    题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3085 题意：求n(<=10^100)之内最大的反素数。 思路： 优化2：   int prime[]= {1, 2, 3, 5, 7,11, 13, 17, 19, 23,29, 31, 37, 41,...

  • HDU 4832 Chess 排列组合 DP

    Chess Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 351    Accepted Submission(s): 124 Problem Description 小度和...

©2024 11GX.COM