#define _CRT_SECURE_NO_WARNINGS /* 7 10 0 1 5 0 2 2 1 2 4 1 3 2 2 3 6 2 4 10 3 5 1 4 5 3 4 6 5 5 6 9 0 6 */ #include <iostream> #include <vector> #include <utility> #include <queue> #include <functional> #include <algorith

C.Coolest Ski Route 题意:n个点,m条边组成的有向图,求任意两点之间的最长路径 dfs记忆化搜索 #include<iostream> #include<string.h> #include<string> #include<algorithm> #include<math.h> #include<string> #include<string.h> #include<vector> #in

  Going from u to v or from v to u? Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 17993   Accepted: 4816 Description In order to make their sons brave, Jiajia and Wind take them to a big cave. The cave has n rooms, and one-way corridor

[Bellman-Ford算法] [算法]Bellman-Ford算法(单源最短路径问题)(判断负圈) 结构: #define MAX_V 10000 #define MAX_E 50000 int V,E; //顶点和边的数量 struct edge{ int from,to,cost; }; edge es[MAX_E];//边集 int d[MAX_V]; //d[i]表示从某个点出发到i的最短路径 算法特点:1.每次都用所有的边更新所有的边,直到无可更新为止. 2.无负圈最多更新 V-1

原题:http://acm.hdu.edu.cn/showproblem.php?pid=2376 经典问题,求的是树上任意两点和的平均值. 这里我们不能枚举点,这样n^2的复杂度.我们可以枚举每一条边,设这条边的端点分别为A.B,则通过这条边的路径总数为与A点相连的端点数乘以与B点相连的端点数,再乘以这条边的权值,将所有的和相加,最后除以n*(n-1)/2就可以了(除以2是因为这里每条边重复计算了两次). 这里统计求和的时候,一遍深搜就可以了,需要注意的是,假设某个点子树所包含点的个数为k,则

1.Floyd-Warshall 算法 给定一张图,在o(n3)时间内求出任意两点间的最小距离,并可以在求解过程中保存路径 2.Floyd-Warshall 算法概念 这是一个动态规划的算法. 将顶点编号,假设依次为0,1,2-n-1,现在假设DP[i][j][k]表示从i出发,结束于j的满足经过结点的编号至多为k的最短路径,由此性质易知,在易知DP[i][j][k]时,若要求DP[i][j][k+1],有两种情况要考虑: DP[i][j][k+1]所表征的路径经过结点k+1,此时DP[i][j

原创 除了DFS和BFS求图中最短路径的方法,算法Floyd-Warshall也可以求图中任意两点的最短路径. 从图中任取两点A.B,A到B的最短路径无非只有两种情况: 1:A直接到B这条路径即是最短路径(前提是存在此路径): 2:A先通过其他点,再由其他点到B. 我们并不知道A是否需要通过其他点间接到达B,所以只能比较,用A到B的直接路径和A先通过其他点 再间接到达B的路径长度进行比较,然后更新为较小值. 上图中若要求顶点4到顶点3的最短路径,可以比较顶点4直接到3的路径和顶点4先到1,再到3

求解所有两点间的最短路问题叫做任意两点间的最短路问题. 可以用动态规划来解决, d[k][i][j] 表示只用前k个顶点和顶点i到顶点j的最短路径长度. 分两种情况讨论: 1.经过顶点k,  d[k][i][j] = d[k-1][i][j].  即等于只用前k-1个顶点时的最短路径 2.不经过顶点k,  d[k][i][j] = d[k-1][i][k] + d[k-1][k][j].  即等于i离k的最路路径+j离k的最短路径. 可以得到递推式 d[k][i][j]  =  min( d[k

Tree and Permutation Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 0    Accepted Submission(s): 0 Problem Description There are N vertices connected by N−1 edges, each edge has its own length.

golang获取程序运行路径: /* 获取程序运行路径 */ func getCurrentDirectory() string { dir, err := filepath.Abs(filepath.Dir(os.Args[0])) if err != nil { beego.Debug(err) } return strings.Replace(dir, "\\", "/", -1) }

/** * 计算地球上任意两点(经纬度)距离 * * @param long1 * 第一点经度 * @param lat1 * 第一点纬度 * @param long2 * 第二点经度 * @param lat2 * 第二点纬度 * @return 返回距离 单位:米 */ public static double Distance(double long1, double lat1, double long2, double lat2) { double a, b, R; R = 637813

caioj 1237: [最近公共祖先]树上任意两点的距离 倍增ST 题目链接:http://caioj.cn/problem.php?id=1237 思路: 针对询问次数多的时候,采取倍增求取LCA,同时跟新距离数组 因为 \(2^{14} > 10000\) 所以所以表示祖先的数组dp[][]第二维取到14即可 代码: #include <iostream> #include <algorithm> #include <stdio.h> #include &l

地球是一个近乎标准的椭球体,它的赤道半径为6378.140千米,极半径为6356.755千米,平均半径6371.004千米.如果我们假设地球是一个完美的球体,那么它的半径就是地球的平均半径,记为R.如果以0度经线为基准,那么根据地球表面任意两点的经纬度就可以计算出这两点间的地表距离(这里忽略地球表面地形对计算带来的误差,仅仅是理论上的估算值).设第一点A的经纬度为(LonA, LatA),第二点B的经纬度为(LonB, LatB),按照0度经线的基准,东经取经度的正值(Longitude),西经

Problem DescriptionAn abandoned country has n(n≤100000) villages which are numbered from 1 to n. Since abandoned for a long time, the roads need to be re-built. There are m(m≤1000000) roads to be re-built, the length of each road is wi(wi≤1000000). G

题意:有一棵n个点的树,点之间用无向边相连.现把这棵树对应一个序列,这个序列任意两点的距离为这两点在树上的距离,显然,这样的序列有n!个,加入这是第i个序列,那么这个序列所提供的贡献值为:第一个点到其他所有点距离之和.求所有序列贡献值之和. 思路:假如第一个点是k,那么后面n-1个点共有(n - 1)!种排列,也就是说,第一个点是k那么这样的序列的贡献值为(n - 1)!*(k到其他点距离之和),显然最后答案应该是所有点之间的距离和的两倍 *(n - 1)!.问题转化为了求一棵树上所有点之间的距

题目: http://poj.org/problem?id=2139 题解:N只牛,在一组的两只牛,分别两只之间为 “1度”,自己到自己为0度,M组牛.求,N只牛之中,两只牛之间 平均最短度数*100.模板Floyd算法,求任意两点之间最短路径. #include <iostream> #include <algorithm> #include <iomanip> using namespace std; + ; ; int N, M; // N个牛 ,M组电影 //不

floyd-warshall算法 通过dp思想 求任意两点之间最短距离 重复利用数组实现方式dist[i][j] i - j的最短距离 for(int k = 1; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]); 非常好实现 O(V^3) 这里贴一道刚好用到的题 http://poj.org

Abandoned country Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 3449    Accepted Submission(s): 846 Problem DescriptionAn abandoned country has n(n≤100000)villages which are numbered from 1 to

题目链接:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_C All Pairs Shortest Path Input An edge-weighted graph G (V, E). |V| |E| s0 t0 d0 s1 t1 d1 : s|E|−1 t|E|−1 d|E|−1 |V| is the number of vertices and |E| is the number of edges in G. T

前言:之前在博问求助过这个问题.经过几天的思考,算是解决了(但仍有不足),另一方面对Geotools不是很熟,有些描述可能不正确,希望大家批评指正. 问题:作为一个新手,我并没有发现Geotools中能够计算路网上任意两点之间最短路径的函数(虽然到现在我仍然不相信,但是我就是没有找到).Geotools中有用迪杰斯特拉算法求最短路径的函数,但是这个函数需要的起点和终点参数都是Node类型(这个node类型是道路的首尾节点) DijkstraShortestPathFinder pf = new

题意:牛之间有绝对的强弱,给出一些胜负关系,问有多少头牛可以确定其绝对排名. #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <stack> #include <map> #i