现在位置: 首页 > 算法 > 文章
2018年12月14日 算法 ⁄ 共 2358字 暂无评论
用的是EdmondsKarp 程序可以再优化的,懒得优化了 EdmondsKarp #include <iostream> #include<stdio.h> #include <queue> #include <limits> #include <cstring> using namespace std; const int maxNode = 202; int N = 201;//edge int M = 201;//node const int maxInt = numeric_limits<int>::max(); int g[maxNode][maxNode]; int f[maxNode][maxNode]; int residual[maxNode][max...
阅读全文
2018年12月14日 算法 ⁄ 共 3544字 暂无评论
#include<iostream> #include<cstring> using namespace std; const int MAXN = 1000; int uN, vN; // u, v数目,要初始化!!! bool g[MAXN][MAXN]; // g[i][j] 表示xi与yj相连 int xM[MAXN], yM[MAXN]; // xM[i]:cow i已经被分配到stall xM[i]; stall j 已经被分配给cow yM[j] bool chk[MAXN]; // 辅助量检查某轮y[v]是否被check bool SearchPath(int u){ int v; for(v = 0...
阅读全文
2018年12月13日 算法 ⁄ 共 1101字 评论关闭
http://www.cppblog.com/ArcTan/articles/167131.html 贪心。从左到右建立雷达,要尽量多地覆盖岛屿。以岛屿的圆心d为半径的圆与x轴有或者没有交点。如果存在没有交点的则不能实现!都存在交点的话,对于第i个岛屿计算出左右交点的x坐标保存在a[i],b[i]里。对a,b排序,然后一次从左到右找雷达。初始right=b[1]为当前最右边的左标,则对于下一个考虑岛屿i,如果a[i]>right则当前需要建立的雷达不能覆盖它,需要以此开始建立...
阅读全文
2018年11月09日 算法 ⁄ 共 2570字 评论关闭
题意:某个冰块上有a只企鹅,总共可以跳出去b只,问是否可能所有的企鹅都跳到某一块冰块上,输出所有的可能的冰块的编号。 由于每个点只能跳出去m只企鹅,所以要拆点假如不拆点,一个点到另一个点可能会跳多于m只企鹅通过拆点后u->u'间的容量来完成题目的要求(对点的一些限制) 建图:i->i+n 容量为m i+n->j容量为INF新建源点s,s->i的容量为i点企鹅的个数然后枚举汇点求最大流就可以判断某个点是否符合条件 Sour...
阅读全文
2018年11月09日 算法 ⁄ 共 620字 评论关闭
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; bool cmp(int a,int b) { return a>b; } int n; int a[66]; int v[66]; int dfs(int s,int s1,int minn) { int i; if(s==0) return 1; if(s1 > s) return 0; if(s1==0) s1=minn; for(i=0;i<n;i++) { if(i&&(a[i]==a[i-1])&&(v[i-1]==0)) continue; if((v[i]) || (s1 < ...
阅读全文
2018年09月23日 算法 ⁄ 共 884字 评论关闭
题目链接:http://poj.org/problem?id=2782 题目大意:  给出n袋长度不一定相同的垃圾,把它们全部装在长度不超过L的垃圾桶里;                     每个垃圾桶至多有两袋垃圾,并且垃圾的长度相加小于L;                     求最少用多少个垃圾桶可以装入全部垃圾; 解题思路:  每个垃圾桶最多只能有两袋垃圾,也就是说可以装是一袋或者两袋;                     先排序,然后分别从最小、最大两个极端开始枚举:      ...
阅读全文
2018年09月23日 算法 ⁄ 共 1654字 评论关闭
题目链接:http://poj.org/problem?id=2785 题目大意:  给出四个长度为n的列表(从上到下)                     从每个列表分别取出一个数据,使得相加的结果为0                     问最多存在多少种情况? 解题思路:  n的范围(1<=n<=4000),如果直接搜索 O(n^4) 那么肯定TLE.(计算机每秒钟的运行速度大概是10^8)                     可以转化为O(2*n^2):                     把1组和2组列表分别相加存到a[ ]数组中...
阅读全文
2018年09月23日 算法 ⁄ 共 1564字 评论关闭
题目链接:    http://poj.org/problem?id=3233 题目大意:    给出矩阵n*n的矩阵A,求对m取模后的结果 解题思路:    k的非常大,直接求解时间复杂度太高                    定义F[k]=A+A^2+A^3+....A^k                                                                   利用乘法的分配律可以减少运算 F[6]=A+A^2+A^3+A^4+A^5+A^6=(A+A^2+A^3)+(A+A^2+A^3)*A^3                                         每次运算二分减少规...
阅读全文
2018年09月23日 算法 ⁄ 共 1199字 评论关闭
题目链接:    http://poj.org/problem?id=3070 题目大意:    求Fibonacci数列第n项(0 ≤ n ≤ 1,000,000,000),对m取模后的结果 解题思路:    直接求解第n项,由于n太大,时间复杂度非常高                    我们需要构造一个矩阵使得与(a,b)相乘后等于(b,a+b)                    不防假设2x2矩阵为:                     x1      x2                     a               b                                            X  ...
阅读全文
2018年09月23日 算法 ⁄ 共 1561字 评论关闭
题目链接:   poj 1330 题目大意:   给出你一棵树,最后一行询问顶点a和顶点b的最近公共祖先 解题思路:   Tarjan离线查找最近公共祖先:                  搜到新的顶点,此顶点的临时祖先就是上一层的顶点                  直到搜到叶子就开始回溯,回溯的时候                  从这点出发搜过的顶点的临时祖先合并为这个顶点的上一层顶点 代码: //Final LCA离线算法求最近公共祖先 #include <stdio.h> #include &l...
阅读全文