- 博客(6)
- 收藏
- 关注
RSS订阅原创 poj 1287||zoj 1372 Networking 最小生成树 kruskal 克鲁斯卡尔算法
这道题的难点在于边的数量是unlimited的，有无限条，用prim算法可以很容易的解出，不过个人比较喜欢用Kruskal算法，所以就想了办法处理了一下数据，然后就可以用Kruskal算法解了主要在于对于数据的去重，因为边数不会超过点数*（点数-1）/2，所以只将两个点最小的边存下来就可以进行kruskal算法了，数组开到1800就绰绰有余了。#include#includeusing
2015-03-11 20:33:24
348
转载 【自用模板】广度优先搜索
#include#includeint ux[30]/*所走过路数的列坐标*/,uy[30]/*所走过路数的行坐标*/,mark[30][30]/*标记走过的点*/,m/*棋盘行数*/,n/*棋盘列数*/,flag/*控制输出impossible变量*/;int to[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1
2014-10-22 17:49:56
450
转载 【自用模板】二分dp
#include#includeusing namespace std;int dp1[10005];int dp2[10005];int num1[10005];int num2[10005];int n;void LIS(int *dp,int *num){ int stk[10005]; int up=0; stk[up]=-1; for(
2014-10-22 17:42:57
366
转载 【自用模板】贪心
#include#includeusing namespace std;struct stick//记录木板长度，宽度，以及是否被处理过{ int l,w; int mark;}st[5005];int cmp(stick a,stick b){ return a.l==b.l?a.w>b.w:a.l>b.l;//长度由大到小，相等时，宽度由大到小}
2014-10-22 17:36:29
278
转载 【自用模板】数位dp
#include#includeint dp[10][3];/*dp[i][0]为位数小于等于i且不含62也不含4的数字的个数dp[i][1]为位数为i且首位为2且不含62也不含4的数字的个数dp[i][2]为位数小于等于i且含62或4的数字的个数*/int digit[10];void er(){ dp[0][0]=1; for(int i=1;i<=
2014-10-22 17:34:06
284
原创 【自用模板】高精度GCD（二进制）
#include#includestruct BN{ int len; int num[1005];};int wei=0;char str1[1005];char str2[1005];int cmp(BN a,BN b)//1:a>b;0:b>a;-1:a=b;{ if(a.len>b.len) {
2014-10-22 17:29:34
497
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人