没有合适的资源?快使用搜索试试~ 我知道了~
吉大 各种基本ACM必备算法基础
需积分: 0 11 下载量 143 浏览量
2014-01-05
01:40:07
上传
评论 3
收藏 648KB PDF 举报
温馨提示
试读
46页
吉大 各种基本ACM必备算法基础
资源推荐
资源详情
资源评论
吉林大学 ACM Group
1
目录
目录 .............................................. 1
Graph 图论 ........................................ 3
| DAG 的深度优先搜索标记 ............................................. 3
| 无向图找桥 ..................................................................... 3
| 无向图连通度(割) ........................................................ 3
| 最大团问题 DP + DFS ................................................. 3
| 欧拉路径 O(E) ............................................................... 3
| DIJKSTRA 数组实现 O(N^2) ..................................... 3
| DIJKSTRA O(E * LOG E) ............................................. 4
| BELLMANFORD 单源最短路 O(VE) ................................. 4
| SPFA(SHORTEST PATH FASTER ALGORITHM) .............. 4
| 第 K 短路(DIJKSTRA) ................................................. 5
| 第 K 短路(A*) ............................................................ 5
| PRIM 求 MST .................................................................... 6
| 次小生成树 O(V^2) ...................................................... 6
| 最小生成森林问题(K 颗树)O(MLOGM). ...................... 6
| 有向图最小树形图 ......................................................... 6
| MINIMAL STEINER TREE ................................................ 7
| TARJAN 强连通分量 ........................................................ 7
| 弦图判断 ......................................................................... 7
| 弦图的 PERFECT ELIMINATION 点排列 .......................... 7
| 稳定婚姻问题 O(N^2) .................................................. 8
| 拓扑排序 ......................................................................... 8
| 无向图连通分支(DFS/BFS 邻接阵) ............................. 8
| 有向图强连通分支(DFS/BFS 邻接阵)O(N^2) ............ 8
| 有向图最小点基(邻接阵)O(N^2)............................... 9
| FLOYD 求最小环 .............................................................. 9
| 2-SAT 问题 ..................................................................... 9
Network 网络流 ................................... 11
| 二分图匹配(匈牙利算法 DFS 实现) ...................... 11
| 二分图匹配(匈牙利算法 BFS 实现) ...................... 11
| 二分图匹配(HOPCROFT-CARP 的算法) .................. 11
| 二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N)) 11
| 无向图最小割 O(N^3) ............................................... 12
| 有上下界的最小(最大)流 .......................................... 12
| DINIC 最大流 O(V^2 * E) ....................................... 12
| HLPP 最大流 O(V^3) ................................................ 13
| 最小费用流 O(V * E * F) ....................................... 14
| 最小费用流 O(V^2 * F) ........................................... 14
| 最佳边割集 ................................................................... 15
| 最佳点割集 ................................................................... 15
| 最小边割集 ................................................................... 15
| 最小点割集(点连通度) ........................................... 16
| 最小路径覆盖 O(N^3) ................................................ 16
| 最小点集覆盖 ............................................................... 16
Structure 数据结构 ............................... 17
| 求某天是星期几 ........................................................... 17
| 左偏树 合并复杂度 O(LOG N) ................................... 17
| 树状数组 ....................................................................... 17
| 二维树状数组 ............................................................... 17
| TRIE 树(K 叉) .............................................................. 18
| TRIE 树(左儿子又兄弟) ............................................. 18
| 后缀数组 O(N * LOG N) ............................................ 18
| 后缀数组 O(N) ............................................................ 18
| RMQ 离线算法 O(N*LOGN)+O(1) ............................. 19
| RMQ(RANGE MINIMUM/MAXIMUM QUERY)-ST 算法
(O(
NLOGN + Q)) ............................................................. 19
| RMQ 离线算法 O(N*LOGN)+O(1)求解 LCA ............. 19
| LCA 离线算法 O(E)+O(1) ........................................ 20
| 带权值的并查集 ........................................................... 20
| 快速排序 ....................................................................... 20
| 2 台机器工作调度 ........................................................ 20
| 比较高效的大数 ........................................................... 20
| 普通的大数运算 ........................................................... 21
| 最长公共递增子序列 O(N^2) .................................... 22
| 0-1 分数规划 ............................................................... 22
| 最长有序子序列(递增/递减/非递增/非递减) .... 22
| 最长公共子序列 ........................................................... 23
| 最少找硬币问题(贪心策略-深搜实现) ................. 23
| 棋盘分割 ....................................................................... 23
| 汉诺塔 ........................................................................... 24
| STL 中的 PRIORITY_QUEUE .......................................... 24
| 堆栈 ............................................................................... 24
| 区间最大频率 ............................................................... 24
| 取第 K 个元素................................................................ 25
| 归并排序求逆序数 ....................................................... 25
| 逆序数推排列数 ........................................................... 25
| 二分查找 ....................................................................... 25
| 二分查找(大于等于 V 的第一个值)........................ 26
| 所有数位相加 ............................................................... 26
吉林大学 ACM Group
2
Number 数论 ...................................... 27
|递推求欧拉函数 PHI(I) ............................................... 27
|单独求欧拉函数 PHI(X) ............................................... 27
| GCD 最大公约数 .......................................................... 27
| 快速 GCD ...................................................................... 27
| 扩展 GCD ...................................................................... 27
| 模线性方程 A * X = B (% N) .................................. 27
| 模线性方程组 ............................................................... 27
| 筛素数 [1..N] ............................................................ 27
| 高效求小范围素数 [1..N] ........................................ 27
| 随机素数测试(伪素数原理) ...................................... 27
| 组合数学相关 ............................................................... 27
| POLYA 计数 .................................................................... 28
| 组合数 C(N, R) ........................................................... 28
| 最大 1 矩阵 ................................................................... 28
| 约瑟夫环问题(数学方法) ....................................... 28
| 约瑟夫环问题(数组模拟) ....................................... 28
| 取石子游戏 1 ................................................................ 28
| 集合划分问题 ............................................................... 28
| 大数平方根(字符串数组表示) ............................... 29
| 大数取模的二进制方法 ............................................... 29
| 线性方程组 A[][]X[]=B[] ....................................... 29
| 追赶法解周期性方程 ................................................... 30
| 阶乘最后非零位,复杂度 O(NLOGN) ........................... 30
递归方法求解排列组合问题 ......................... 31
| 类循环排列 ................................................................... 31
| 全排列 ........................................................................... 31
| 不重复排列 ................................................................... 31
| 全组合 ........................................................................... 32
| 不重复组合 ................................................................... 32
| 应用 ............................................................................... 33
模式串匹配问题总结 ............................... 33
| 字符串 HASH .................................................................. 33
| KMP 匹配算法 O(M+N) ............................................... 33
| KARP-RABIN 字符串匹配 ............................................. 33
| 基于 KARP-RABIN 的字符块匹配................................. 33
| 函数名: STRSTR ........................................................... 34
| BM 算法的改进的算法 SUNDAY ALGORITHM ................ 34
| 最短公共祖先(两个长字符串) ............................... 34
| 最短公共祖先(多个短字符串) ............................... 34
Geometry 计算几何 ................................ 35
| GRAHAM 求凸包 O(N * LOGN) .................................... 35
| 判断线段相交 ............................................................... 35
| 求多边形重心 ............................................................... 35
| 三角形几个重要的点 ................................................... 35
| 平面最近点对 O(N * LOGN) ...................................... 35
| LIUCTIC 的计算几何库 ................................................ 36
| 求平面上两点之间的距离 ........................................... 36
| (P1-P0)*(P2-P0)的叉积 ....................................... 36
| 确定两条线段是否相交 ............................................... 36
| 判断点 P 是否在线段 L 上 ............................................ 36
| 判断两个点是否相等 ................................................... 36
| 线段相交判断函数 ....................................................... 36
| 判断点 Q 是否在多边形内 .......................................... 37
| 计算多边形的面积 ....................................................... 37
| 解二次方程 AX^2+BX+C=0 ........................................ 37
| 计算直线的一般式 AX+BY+C=0 ................................. 37
| 点到直线距离 ............................................................... 37
| 直线与圆的交点,已知直线与圆相交 ....................... 37
| 点是否在射线的正向 ................................................... 37
| 射线与圆的第一个交点 ............................................... 37
| 求点 P1 关于直线 LN 的对称点 P2 .............................. 37
| 两直线夹角(弧度) ................................................... 37
ACM/ICPC 竞赛之 STL ............................... 38
ACM/ICPC 竞赛之 STL 简介 .......................................... 38
ACM/ICPC 竞赛之 STL--PAIR ...................................... 38
ACM/ICPC 竞赛之 STL--VECTOR .................................. 39
ACM/ICPC 竞赛之 STL--ITERATOR 简介 ...................... 39
ACM/ICPC 竞赛之 STL--STRING .................................. 40
ACM/ICPC 竞赛之 STL--STACK/QUEUE ........................ 40
ACM/ICPC 竞赛之 STL--MAP ........................................ 41
ACM/ICPC 竞赛之 STL--ALGORITHM ............................. 42
STL IN ACM ..................................................................... 43
头文件 ............................................................................... 44
线段树 ........................................... 44
求矩形并的面积(线段树+离散化+扫描线) ............... 44
求矩形并的周长(线段树+离散化+扫描线) ............... 45
吉林大学 ACM Group
3
Graph 图论
/*==================================================*\
| DAG 的深度优先搜索标记
| INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;
| CALL: dfstag(i, n); pre/post:开始/结束时间
\*==================================================*/
int edge[V][V], pre[V], post[V], tag;
void dfstag(int cur, int n )
{ // vertex: 0 ~ n-1
pre[cur] = ++tag;
for (int i=0; i<n; ++i) if (edge[cur][i]) {
if (0 == pre[i]) {
printf("Tree Edge!\n");
dfstag(i, n);
} else {
if (0 == post[i]) printf("Back Edge!\n");
else if (pre[i] > pre[cur])
printf("Down Edge!\n");
else printf("Cross Edge!\n");
}
}
post[cur] = ++tag;
}
/*==================================================*\
| 无向图找桥
| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;
| CALL: dfs(0, -1, 1, n);
\*==================================================*/
int bridge, edge[V][V], anc[V], pre[V], vis[V];
void dfs(int cur, int father, int dep, int n)
{ // vertex: 0 ~ n-1
if (bridge) return;
vis[cur] = 1; pre[cur] = anc[cur] = dep;
for (
int i=0; i<n; ++i) if (edge[cur][i]) {
if (i != father && 1 == vis[i]) {
if (pre[i] < anc[cur])
anc[cur] = pre[i];//back edge
}
if (0 == vis[i]) { //tree edge
dfs(i, cur, dep+1, n);
if (bridge) return;
if (anc[i] < anc[cur]) anc[cur] = anc[i];
if (anc[i] > pre[cur]) { bridge = 1; return; }
}
}
vis[cur] = 2;
}
/*==================================================*\
| 无向图连通度(割)
| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0;
| CALL: dfs(0, -1, 1, n);
| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数
| 注意:0作为根比较特殊!
\*==================================================*/
int edge[V][V], anc[V], pre[V], vis[V], deg[V];
void dfs(int cur, int father, int dep, int n)
{// vertex: 0 ~ n-1
int cnt = 0;
vis[cur] = 1; pre[cur] = anc[cur] = dep;
for (int i=0; i<n; ++i) if (edge[cur][i]) {
if (i != father && 1 == vis[i]) {
if (pre[i] < anc[cur])
anc[cur] = pre[i];//back edge
}
if (0 == vis[i]) { //tree edge
dfs(i, cur, dep+1, n);
++cnt; // 分支个数
if (anc[i] < anc[cur]) anc[cur] = anc[i];
if ((cur==0 && cnt>1) ||
(cnt!=0 && anc[i]>=pre[cur]))
++deg[cur]; // link degree of a vertex
}
}
vis[cur] = 2;
}
/*==================================================*\
| 最大团问题 DP + DFS
| INIT: g[][]邻接矩阵;
| CALL: res = clique(n);
\*==================================================*/
int g[V][V], dp[V], stk[V][V], mx;
int dfs(int n, int ns, int dep){
if (0 == ns) {
if (dep > mx) mx = dep;
return 1;
}
int i, j, k, p, cnt;
for (i = 0; i < ns; i++) {
k = stk[dep][i]; cnt = 0;
if (dep + n - k <= mx) return 0;
if (dep + dp[k] <= mx) return 0;
for (j = i + 1; j < ns; j++) {
p = stk[dep][j];
if (g[k][p]) stk[dep + 1][cnt++] = p;
}
dfs(n, cnt, dep + 1);
}
return 1;
}
int clique(int n){
int i, j, ns;
for (mx = 0, i = n - 1; i >= 0; i--) {
// vertex: 0 ~ n-1
for (ns = 0, j = i + 1; j < n; j++)
if (g[i][j]) stk[1][ ns++ ] = j;
dfs(n, ns, 1); dp[i] = mx;
}
return mx;
}
/*==================================================*\
| 欧拉路径 O(E)
| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;
| CALL: elpath(0); 注意
:不要有自向边
\*==================================================*/
int adj[V][V], idx[V][V], cnt[V], stk[V], top;
int path(int v){
for (int w ; cnt[v] > 0; v = w) {
stk[ top++ ] = v;
w = adj[v][ --cnt[v] ];
adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];
// 处理的是无向图—-边是双向的,删除v->w后,还要处理删除w->v
}
return v;
}
void elpath (int b, int n){ // begin from b
int i, j;
for (i = 0; i < n; ++i) // vertex: 0 ~ n-1
for (j = 0; j < cnt[i]; ++j)
idx[i][ adj[i][j] ] = j;
printf("%d", b);
for (top = 0; path(b) == b && top != 0; ) {
b = stk[ --top ];
printf("-%d", b);
}
printf("\n");
}
/*==================================================*\
| Dijkstra 数组实现 O(N^2)
| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)
| lowcost[] --- beg到其他点的最近距离
| path[] -- beg为根展开的树,记录父亲结点
\*==================================================*/
#define INF 0x03F3F3F3F
const int N;
int path[N], vis[N];
void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){
int i, j, min;
memset(vis, 0, sizeof(vis));
vis[beg] = 1;
for (i=0; i<n; i++){
lowcost[i] = cost[beg][i]; path[i] = beg;
}
lowcost[beg] = 0;
吉林大学 ACM Group
4
path[beg] = -1; // 树根的标记
int pre = beg;
for (i=1; i<n; i++){
min = INF;
for (j=0; j<n; j++)
// 下面的加法可能导致溢出,INF不能取太大
if (vis[j]==0 &&
lowcost[pre]+cost[pre][j]<lowcost[j]){
lowcost[j] = lowcost[pre] + cost[pre][j];
path[j] = pre;
}
for (j=0; j<n; j++)
if (vis[j] == 0 && lowcost[j] < min){
min = lowcost[j]; pre = j;
}
vis[pre] = 1;
}
}
/*==================================================*\
| Dijkstra O(E * log E)
| INIT: 调用init(nv, ne)读入边并初始化;
| CALL: dijkstra(n, src); dist[i]为src到i的最短距离
\*==================================================*/
#define typec int // type of cost
const typec inf = 0x3f3f3f3f; // max of cost
typec cost[E], dist[V];
int e, pnt[E], nxt[E], head[V], prev[V], vis[V];
struct qnode {
int v; typec c;
qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {}
bool operator < (const qnode& r) const { return c>r.c; }
};
void dijkstra(int n, const int src){
qnode mv;
int i, j, k, pre;
priority_queue<qnode> que;
vis[src] = 1; dist[src] = 0;
que.push(qnode(src, 0));
for (pre = src, i=1; i<n; i++) {
for (j = head[pre]; j != -1; j = nxt[j]) {
k = pnt[j];
if (vis[k] == 0 &&
dist[pre] + cost[j] < dist[k]){
dist[k] = dist[pre] + cost[j];
que.push(qnode(pnt[j], dist[k]));
prev[k] = pre;
}
}
while (!que.empty() && vis[que.top().v] == 1)
que.pop();
if (que.empty()) break;
mv = que.top(); que.pop();
vis[pre = mv.v] = 1;
}
}
inline void addedge(int u, int v, typec c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
void init(int nv, int ne){
int i, u, v; typec c;
e = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
memset(prev, -1, sizeof(prev));
for (i = 0; i < nv; i++) dist[i] = inf;
for (i = 0; i < ne; ++i) {
scanf("%d%d%d", &u, &v, &c);// %d: type of cost
addedge(u, v, c); // vertex: 0 ~ n-1, 单向边
}
}
/*==================================================*\
| BellmanFord 单源最短路 O(VE)
| 能在一般情况下,包括存在负权边的情况下,解决单源最短路径问题
| INIT: edge[E][3]为边表
| CALL: bellman(src);有负环返回0;dist[i]为src到i的最短距
| 可以解决差分约束系统: 需要首先构造约束图,构造不等式时>=表示求最
小值, 作为最长路,<=表示求最大值, 作为最短路 (v-u <= c:a[u][v] =
c)
\*==================================================*/
#define typec int // type of cost
const typec inf=0x3f3f3f3f; // max of cost
int n, m, pre[V], edge[E][3];
typec dist[V];
int relax (int u, int v, typec c){
if (dist[v] > dist[u] + c) {
dist[v] = dist[u] + c;
pre[v] = u; return 1;
}
return 0;
}
int bellman (int src){
int i, j;
for (i=0; i<n; ++i) {
dist[i] = inf; pre[i] = -1;
}
dist[src] = 0; bool flag;
for (i=1; i<n; ++i){
flag = false; // 优化
for (j=0; j<m; ++j) {
if( 1 == relax(edge[j][0], edge[j][1],
edge[j][2]) ) flag = true;
}
if( !flag ) break; }
for (j=0; j<m; ++j) {
if (1 == relax(edge[j][0], edge[j][1], edge[j][2]))
return 0; // 有负圈
}
return 1;
}
/*==================================================*\
| SPFA(Shortest Path Faster Algorithm)
Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。 它可以在
O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
原理:只有那些在前一遍松弛中改变了距离估计值的点,才可能引起他们的邻
接点的距离估计值的改变。
判断负权回路:记录每个结点进队次数,超过|V|次表示有负权。
\*==================================================*/
// POJ 3159 Candies
const int INF = 0x3F3F3F3F;
const int V = 30001;
const int E = 150001;
int pnt[E], cost[E], nxt[E];
int e, head[V]; int dist[V]; bool vis[V];
int main(void){
int n, m;
while( scanf("%d%d", &n, &m) != EOF ){
int i, a, b, c;
e = 0;
memset(head, -1, sizeof(head));
for( i=0; i < m; ++i )
{// b-a <= c, 有向边(a, b):c ,边的方向!!!
scanf("%d%d%d", &a, &b, &c);
addedge(a, b, c);
}
printf("%d\n", SPFA(1, n));
}
return 0;
}
int relax(int u, int v, int c){
if( dist[v] > dist[u] + c ) {
dist[v] = dist[u] + c; return 1;
}
return 0;
}
inline void addedge(int u, int v, int c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
int SPFA(int src, int n)
{ // 此处用堆栈实现,有些时候比队列要快
int i;
for( i=1; i <= n; ++i ){ // 顶点1...n
vis[i] = 0; dist[i] = INF;
}
dist[src] = 0;
int Q[E], top = 1;
Q[0] = src; vis[src] = true;
while( top ){
int u, v;
u = Q[--top]; vis[u] = false;
for( i=head[u]; i != -1; i=nxt[i] ){
吉林大学 ACM Group
5
v = pnt[i];
if( 1 == relax(u, v, cost[i]) && !vis[v] ) {
Q[top++] = v; vis[v] = true;
}
}
}
return dist[n];
}
// 队列实现,而且有负权回路判断—POJ 3169 Layout
#define swap(t, a, b) (t=a, a=b, b=t)
const int INF = 0x3F3F3F3F;
const int V = 1001;
const int E = 20001;
int pnt[E], cost[E], nxt[E];
int e, head[V], dist[V];
bool vis[V];
int cnt[V]; // 入队列次数
int main(void){
int n, ml, md;
while( scanf("%d%d%d", &n, &ml, &md) != EOF ){
int i, a, b, c, t;
e = 0;
memset(head, -1, sizeof(head));
for( i=0; i < ml; ++i ) // 边方向!!!
{// 大-小<=c, 有向边(小, 大):c
scanf("%d%d%d", &a, &b, &c);
if( a > b) swap(t, a, b);
addedge(a, b, c);
}
for( i=0; i < md; ++i )
{// 大-小>=c ==> 小-大<=-c, 有向边(大, 小):-c
scanf("%d%d%d", &a, &b, &c);
if( a < b ) swap(t, a, b);
addedge(a, b, -c);
}
//for( i=1; i <= n; ++i ) printf("%d\n", dist[i]);
printf("%d\n", SPFA(1, n));
}
return 0;
}
int relax(int u, int v, int c){
if( dist[v] > dist[u] + c ) {
dist[v] = dist[u] + c; return 1;
}
return 0;
}
inline void addedge(int u, int v, int c){
pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++;
}
int SPFA(int src, int n){// 此处用队列实现
int i;
memset(cnt, 0, sizeof(cnt)); // 入队次数
memset(vis, false, sizeof(vis));
for( i=1; i <= n; ++i ) dist[i] = INF;
dist[src] = 0;
queue<int> Q;
Q.push(src); vis[src] = true; ++cnt[src];
while( !Q.empty() ){
int u, v;
u = Q.front(); Q.pop(); vis[u] = false;
for( i=head[u]; i != -1; i=nxt[i] ){
v = pnt[i];
if( 1 == relax(u, v, cost[i]) && !vis[v] ) {
Q.push(v); vis[v] = true;
if( (++cnt[v]) > n ) return -1; // cnt[i]
为入队列次数,用来判断是否存在负权回路
}
}
}
if( dist[n] == INF ) return -2; // src与n不可达,有些题
目可省!!!
return dist[n]; // 返回src到n的最短距离,根据题意不同而改变
}
/*==================================================*\
| 第 K 短路(Dijkstra)
| dij变形,可以证明每个点经过的次数为小于等于K,所有把dij的数组dist
| 由一维变成2维,记录经过该点1次,2次。。。k次的最小值。
| 输出dist[n-1][k]即可
\*==================================================*/
//WHU1603
int g[1010][1010];
int n,m,x;
const int INF=1000000000;
int v[1010];
int dist[1010][20];
int main(){
while (scanf("%d%d%d",&n,&m,&x)!=EOF){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
g[i][j]=INF;
for (int i=0;i<m;i++){
int p,q,r;
scanf("%d%d%d",&p,&q,&r);
if (r<g[p][q]) g[p][q]=r;
}
for (int i=1;i<=n;i++){
v[i]=0;
for (int j=0;j<=x;j++)
dist[i][j]=INF;
}
dist[1][0]=0;
dist[0][0]=INF;
while (1){
int k=0;
for (int i=1;i<=n;i++)
if (v[i]<x && dist[i][v[i]]<dist[k][0])
k=i;
if (k==0) break;
if (k==n && v[n]==x-1) break;
for (int i=1;i<=n;i++){
if (v[i]<x &&
dist[k][v[k]]+g[k][i]<dist[i][x]){
dist[i][x]=dist[k][v[k]]+g[k][i];
for (int j=x;j>0;j--)
if (dist[i][j]<dist[i][j-1])
swap(dist[i][j],dist[i][j-1]);
}
}
v[k]++;
}
if (dist[n][x-1]<INF) printf("%d\n",dist[n][x-1]);
else printf("-1\n");
}
return 0;
}
/*==================================================*\
| 第 K
短路(A*)
| A* 估价函数 fi为到当前点走过的路经长度, hi为该点到终点的长度
| gi=hi+fi;
\*==================================================*/
//WHU1603
int n,m,x,ct;
int g[1010][1010],gr[1010][1010];
int dist[1010],v[1010];
const int INF=1000000000;
struct node{
int id,fi,gi;
friend bool operator <(node a,node b){
if (a.gi==b.gi) return a.fi>b.fi;
return a.gi>b.gi;
}
}s[2000010];
int init(){
for (int i=0;i<=n;i++){
dist[i]=INF;
v[i]=1;
}
dist[n-1]=0;
for (int i=0;i<n;i++){
int k=n;
for (int j=0;j<n;j++)
if (v[j] && dist[j]<dist[k]) k=j;
if (k==n) break;
v[k]=0;
for (int j=0;j<n;j++)
if (v[j] && dist[k]+gr[k][j]<dist[j])
dist[j]=dist[k]+gr[k][j];
}
return 1;
}
剩余45页未读,继续阅读
资源评论
GejinZ
- 粉丝: 37
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功