poj 1511 题目链接 题意：和那道奶牛的舞会类似，要求所有点到点1的距离和加上1点到所有点的距离和。 思路：正反存边建两次图，跑两次spfa. 然而用vector会TLE....所以去学习了新的建图方式。。。也就是链式前向星：链式前向星（边表）学习链接 也叫边表。 是一种几乎没有什么缺点的存图方式。。。？ 比起普通的前向星少了个排序。 哦，还有我发现貌似很多人把这个东西叫邻接表。。但是根据这里：几种建图方式 这个东西还是交边表或者链式前向星比较合适。。。？ /* *********************************************** Author :111qqz Created Time :2016 …

1614: [Usaco2007 Jan]Telephone Lines架设电话线 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1325 Solved: 570 [Submit][Status][Discuss] Description Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线， …

1631: [Usaco2007 Feb]Cow Party Time Limit: 5 Sec Memory Limit: 64 MB Submit: 670 Solved: 493 [Submit][Status][Discuss] Description  农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？ Input 第1行:三个用空格隔开的整数. 第2行到第M+1行,每行三个用空格隔开的整 …

hdu 3790 题目链接 题意：给出n个点m条无向边，每条边有一个距离和一个花费。给出s,t。问从s到t的最短距离以及最短距离时的最小花费。当有多个距离最短的方案时，选取花费最少的。 spfa学习链接 usetc 每周算法讲堂之spfa 先写几道题加深理解。 记得初始化。。。。。。 /* *********************************************** Author :111qqz Created Time :2016年05月21日 星期六 18时42分24秒 File Name :code/hdu/3790.cpp …

zoj 3195题目链接 题意：求树上三点的最短距离。。。 思路：两两求，和除以2. 因为忘记初始化p=0..WA了将近两个小时。。。？ 妈的智障。 /* *********************************************** Author :111qqz Created Time :2016年05月21日 星期六 14时44分39秒 File Name :code/zoj/3195.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu2874题目链接 题意：给一个森林，问两点的最短距离，或者输出两点不联通。 思路：最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 最最重要的一点是:添加虚点！ 所谓虚点，就是之前假设某个不存在的点，有点类似做辅助线。 通过添加虚点，我们可以把这个森林转化成一棵树。 这样求两点的距离就可以转化成一棵树上的两点的距离。 用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。 不联通的话就是LCA 为0的情况（0是添加的虚点，作为新的树的根） 具体添加虚点的方法是：森林中每棵树的根连边到虚点上。权值大小随意，因为最后会抵消（？） 为了知道每棵树的根，需要用到并查 …

题目链接 题意：求树上两点的最短距离？ 思路： dis[i]表示点i到根节点的距离，那么任意两点u,v的最短距离d = dis[u]+dis[v]-2*dis[LCA(u,v)]. 只需要求出rmq+dfs的在线方法求出lca(u,v)即可。 /* *********************************************** Author :111qqz Created Time :2016年05月20日 星期五 15时36分47秒 File Name :code/poj/1986.cpp ************************************************ */ #include …

hdu 3530题目链接 题意：给出n个数，m,k，问最大的j-i+1,使得【i,j】间的最大值与最小值的差属于[m,k] 思路：rmq+尺取。 2A. /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 16时52分03秒 File Name :code/hdu/3530.cpp ************************************************ */ #include <cstdio> #include <cstring> …

poj1470题目链接 题意：求两点的lca. 思路：dfs+rmq. 读入技巧。 读入比较坑爹。。。 学会了一种新的读入技巧。 scanf("%2s",st); 表示读一个长度为2的字符串。。。读的时候会忽略各种空白字符。 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时44分12秒 File Name :code/poj/1470.cpp ************************************************ */ #include …

poj1330题目链接 题意：给出一棵树，求两点的lca. 思路：将lca转化成rmq在线求解。 代码部分参考了：参考代码 感觉实现得很巧妙。。。 把树存成了有向图，dfs遇到的时候一定是第一次遇到，此时更新R. 然后第二次遇到某个点就是在回溯的时候了。 算法学习链接 /* *********************************************** Author :111qqz Created Time :2016年05月19日 星期四 15时05分31秒 File Name :code/poj/1330.cpp ************************************************ …