(0)Dijstra 最短路径和prim最小生成树算法,神似,只是在更新dist时的if条件不同;主要是这类prime 的计算两个集合间的最小值的思想非常重要。
(1)某省自从实行了很多年的畅通工程计划后,终究修建了很多路。不过路多了也不好,每次要从1个城镇到另外一个城镇时,都有许多种道路方案可以选择,而某些方案要比另外一些方案行走的距离要短很多。这让行人很困扰。
现在,已知出发点和终点,请你计算出要从出发点到终点,最短需要行走多少距离。
Input
本题目包括多组数据,请处理到文件结束。
每组数据第1行包括两个正整数N和M(0<N<200,0<M<1000),分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0~N⑴编号。
接下来是M行道路信息。每行有3个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有1条长度为X的双向道路。
再接下1行有两个整数S,T(0<=S,T<N),分别代表出发点和终点。
Output
对每组数据,请在1行里输出最短需要行走的距离。如果不存在从S到T的线路,就输出⑴.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
⑴
// prime 和 dij算法的核心 ―― 如何保证当前的最小边是终究的最小边,
// 上
面试最小生成树的算法,下面是最短路径的算法了
#include <iostream>
#include <cstring>
using namespace std;
const int INF = 1000000;
const int MAX_SIZE = 200;
int map[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE];
int disit[MAX_SIZE]; //存储距离
//s开始位置,e结束位置
void dij_method(int s, int e, int N)
{
// init the params of dij
memset(visited, false, sizeof(visited));
for (int i = 0; i < N; i++)
{
if (map[s][i] == ⑴)
disit[i] = INF;
else
disit[i] = map[s][i];
}
// 从s 点开始计算
visited[s] = true;
for (int i = 1; i < N; i++)
{
int min = INF;
int index = 0;
// 找当前最小的 (这与prime1样,只是if条件更强了)
for (int j = 0; j < N; j++)
{
if (!visited[j] && j != s && disit[j] != ⑴ && disit[j] < min)
{
min = disit[j];
index = j;
}
}
visited[index] = true;//顶点并入U集
if (index == e) //如果已到达终点
break;
// 调剂更新目前的最短距离(这与这与prime1样,只是if条件不1样而已)
for (int j = 0; j < N; j++)
{
if (!visited[j] && map[index][j] != ⑴
&& (min + map[index][j]) < disit[j])
{
disit[j] = min + map[index][j];
}
}// end of for
}// end of for
}
int main()
{
int N, M;// 点数和记录数
int ori, des, len;//
int start, end;
while (cin >> N >> M)
{
memset(map, ⑴, sizeof(map)); //⑴表示不可达
while (M--)
{
cin >> ori >> end >> len;
//有可能有更小的路径
if (map[ori][des] == ⑴ || len < map[ori][des])
{
map[ori][des] = len;
map[des][ori] = len;
}
}
// input and input start and end.
cin >> start >> end;
if (start == end)
{
cout << 0 << endl;
continue;
}
// 调用无负权边的图(Dijkstra算法)
dij_method(start, end, N);
if (visited[end] && disit[end] < INF)
cout << disit[end] << endl;
else
cout << ⑴ << endl;
}
return 0;
}
(2)* About: 有向图的Dijkstra算法实现
输入数据:
5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
输出数据:
999999 10 999999 30 100
10 999999 50 999999 999999
999999 50 999999 20 10
30 999999 20 999999 60
100 999999 10 60 999999
源点到最后1个顶点的最短路径长度: 60
源点到最后1个顶点的路径为: 1 -> 4 -> 3 -> 5
#include <iostream>
using namespace std;
const int maxnum = 100;
const int maxint = 999999;
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
bool s[maxnum]; // 判断是不是已存入该点到S集合中
for(int i=1; i<=n; ++i)
{
dist[i] = c[v][i];
s[i] = 0; // 初始都未用过该点
if(dist[i] == maxint)
prev[i] = 0;
else
prev[i] = v;
}
dist[v] = 0;
s[v] = 1;
// 顺次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中
// 1旦S包括了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度
for(int i=2; i<=n; ++i)
{
int tmp = maxint;
int u = v;
// 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!s[j]) && dist[j]<tmp)
{
u = j; // u保存当前邻接点中距离最小的点的号码
tmp = dist[j];
}
s[u] = 1; // 表示u点已存入S集合中
// 更新dist
for(int j=1; j<=n; ++j)
if((!s[j]) && c[u][j]<maxint)
{
int newdist = dist[u] + c[u][j];
if(newdist < dist[j])
{
dist[j] = newdist;
prev[j] = u;
}
}
}
}
void searchPath(int *prev,int v, int u)
{
int que[maxnum];
int tot = 1;
que[tot] = u;
tot++;
int tmp = prev[u];
while(tmp != v)
{
que[tot] = tmp;
tot++;
tmp = prev[tmp];
}
que[tot] = v;
for(int i=tot; i>=1; --i)
if(i != 1)
cout << que[i] << " -> ";
else
cout << que[i] << endl;
}
int main()
{
freopen("input.txt", "r", stdin);
// 各数组都从下标1开始
int dist[maxnum]; // 表示当前点到源点的最短路径长度
int prev[maxnum]; // 记录当前点的前1个结点
int c[maxnum][maxnum]; // 记录图的两点间路径长度
int n, line; // 图的结点数和路径数
// 输入结点数
cin >> n;
// 输入路径数
cin >> line;
int p, q, len; // 输入p, q两点及其路径长度
// 初始化c[][]为maxint
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
c[i][j] = maxint;
for(int i=1; i<=line; ++i)
{
cin >> p >> q >> len;
if(len < c[p][q]) // 有重边
{
c[p][q] = len; // p指向q
c[q][p] = len; // q指向p,这样表示无向图
}
}
for(int i=1; i<=n; ++i)
dist[i] = maxint;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=n; ++j)
printf("%8d", c[i][j]);
printf("
");
}
Dijkstra(n, 1, dist, prev, c);
// 最短路径长度
cout << "源点到最后1个顶点的最短路径长度: " << dist[n] << endl;
// 路径
cout << "源点到最后1个顶点的路径为: ";
searchPath(prev, 1, n);
}
(3)
//poj2367题意: 知道1个数n, 然后n行,编号1到n, 每行输入几个数,
//该行的编号排在这几个数前面,输出1种符合要求的编号名次排序。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 105;
bool adj[MAXN][MAXN];// 林街边
int in_degree[MAXN];// 入度
int result[MAXN];// 结果顺序
void topo_sort(const int n)
{
int i,j,k;
memset(in_degree,0,sizeof(in_degree));
for(i=1; i<=n; i++) //寻觅入度为零的节点
{
for(j=1; j<=n; j++)
{
if(adj[i][j])
in_degree[j]++;
}
}// 可以在输入的时候就计算入度的数值
for(i=1; i<=n; i++)// 这1个i表示个数的
{
for(j=1; j<=n; j++)
{
if(in_degree[j]==0)
{
k=j;
break;
}
}
in_degree[k]=⑴;// 标志,已访问过
result[i]=k;
for(j=1; j<=n; j++) //入度减1
{
if(adj[k][j])
{
in_degree[j]--;
}
}// end of for
}// end of for
}
int main()
{
int i,tem;
int n;
//init and input
memset(adj,false,sizeof(adj));
scanf("%d",&n);
for(i=1; i<=n; i++)
{
while(scanf("%dtem",&tem),tem)
{
adj[i][tem]=true;
}
}
// topo_sort
topo_sort(n);
for(i=1; i<=n; i++)
{
if(i==1)
printf("%d",result[i]);
else
printf(" %d",result[i]);
}
printf("
");
return 0;
}
(4)
POJ 3249 拓扑排序+动态计划
分类: ACM 2012-06⑴1 13:38 812人浏览 评论(0) 收藏 举报
inputdelete存储struct
该题是让求在1个有向无环图中,从1个入度为 0 的节点动身,到1个出度为 0 的节点的最大的权值问题。我们可使用广搜,但是会超时,上网查了1下解题报告,可使用拓扑排序+动态计划来解决此问题:
dp[1] = max{ dp[2] + cost[1] , dp[3] + cost[1] };
dp[2] = cost[2] + dp[4];
dp[3] = cost[3] + dp[4];
dp[4] = cost[4];
dp[5] = cost[5] + dp[6];
dp[6] = cost[6];
在拓扑排序的进程中,是入度为0的节点先入队列,所以我们可以做1个逆置思考,是的 dp[i] 存储的是入度为零的节点到当前节点的最大权值和,而最后在出度为 0 的节点的 dp[i] 中搜索最大的权值。代码实现以下:
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
#define N 100100
#define M 1000100
#define INF 1<<29
struct node
{
int v;
int next;
} edge[M];
int dp[N]; // 最大价值 存储 由 拓扑排序后 入度为0的节点到当前节点最大的 profit
int enext[N]; //记录节点 i 当前的边,由当前的边 推出 下1条边
int indegree[N]; //入度
int cost[N]; //价值
int res;
int idx;
std::queue<int > q;
int m,n,a,b,i,j;
void input()
{
for(i=1;i<=n;i++)
{
scanf("%d",&cost[i]);
dp[i] = -INF;
indegree[i] = 0;
}
idx=0;
//memset(dp,-INF,sizeof(int)*(n+10) );
//memset(indegree,0,sizeof(int)*(n+10) ); //节点度数初始化为0
memset(enext,⑴,sizeof(enext) ); //说明当前节点只此1条边
for(i=1;i<=m;i++)
{
scanf("%d %d",&a,&b);
edge[idx].v = b;
edge[idx].next = enext[a];
enext[a] = idx++;
indegree[b]++;
}
while( !q.empty() )
q.pop();
for( i=1;i<=n;i++)
if( !indegree[i] )
q.push(i),dp[i]=cost[i];
}
int dag()
{
res = -INF;
while( !q.empty() )
{
int cur = q.front();
q.pop();
bool flag = true; //只有节点的出度为 0 的时候,我们才判断其是不是有最大profit
int nextid;
// cout<<"cur : "<<cur<<endl;
for( i=enext[cur] ; i != ⑴ ; i = edge[i].next) //遍历当前顶点的所有的边
{
flag = false;
nextid = edge[i].v ;
// cout<<"nextid : "<<nextid<<endl;
if( dp[nextid] < cost[ nextid ] + dp[cur])
dp[nextid] = cost[nextid] + dp[cur];
indegree[nextid]--;
if( !indegree[nextid] )
{
q.push(nextid);
}
}
if( flag && dp[cur] > res )
res = dp[cur];
}
return res;
}
int main()
{
while(scanf("%d %d",&n,&m) != EOF)
{
input();
printf("%d
",dag());
}
return 0;
}