• 最短路题单练习

    1.Frogger（最大路径最小值）

    题目链接

     题目大意：求所有路径中的最长的边，在这些最长边中找到最小值并输出

    思路：我们可以改变dijkstra的dis数组的含义，即所有点到点v的路径上的最小值，例如现在有一条路径为 u->v,我们可以用 dis[u] 和 len（u->v）的长度取最大，再用此时的得到的值，与dis[v]取最小

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. using namespace std;
    8.  
    9. const int maxn = 220;
    10.  
    11. const double INF = 1e60;
    12.  
    13. int n;
    14. double G[maxn][maxn], d[maxn];
    15.  
    16. struct Pos {
    17.     int x, y;
    18. }num[maxn];
    19.  
    20. double calc(int i, int j) {
    21.     return (sqrt(pow((double)num[i].x-num[j].x, 2)+pow((double)num[i].y-num[j].y, 2)));
    22. }
    23.  
    24. double dijkstra() {
    25.     bool vis[maxn];
    26.     
    27.     memset(vis, false, sizeof(vis));
    28.  
    29.     for(int i=0; i
    30.         d[i] = G[0][i];
    31.     }
    32.  
    33.     d[0] = 0;
    34.     vis[0] = true;
    35.  
    36.     for(int i=0; i-1; i++) {
    37.         double m = INF; int x;
    38.         for(int y=0; yif(!vis[y] && m >= d[y]) m = d[x=y];
    39.         vis[x] = true;
    40.         for(int y=0; y
    41.             if(!vis[y]) {
    42.                 double maxx = max(d[x], G[x][y]);
    43.                 if(d[y] > maxx) d[y] = maxx;
    44.             }
    45.         }
    46.     }
    47.     
    48.     return d[1];
    49. }
    50.  
    51. int main() {
    52.     int cnt = 0;
    53.     while(scanf("%d", &n) == 1) {
    54.         if(n == 0) break;
    55.  
    56.         for(int i=0; iscanf("%d%d", &num[i].x, &num[i].y);
    57.  
    58.         for(int i=0; i
    59.             for(int j=0; j
    60.                 G[i][j] = G[j][i] = calc(i, j);
    61.             }
    62.             G[i][i] = 0;
    63.         }
    64.  
    65.         printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++cnt, dijkstra());
    66.     }
    67.  
    68.     return 0;
    69. }

    2.Heavy Transportation(最小路径最大值)

    题目链接

    题目大意：N个点，M条边，每条边有权值。求一条1号点到N号点的路径，要求使得路径中的边权最小值最大。

    思路：这道题和上一道思路类似，我们可以改变dis数组的含义，在更新dis的过程中与上一道题相反即可

    1. #include
    2. #include
    3.  
    4. using namespace std;
    5.  
    6. const int N = 1010, M = 1e6+10;
    7. int h[N], e[M], ne[M], w[M], idx;
    8. int dis[N],vis[N];
    9.  
    10. int n,m;
    11.  
    12. void add(int a,int b,int c){
    13. 	e[idx] = b;
    14. 	ne[idx] = h[a];
    15. 	w[idx] = c;
    16. 	h[a] = idx++;
    17. }
    18.  
    19. int dj(){
    20. 	for(int i=h[1];~i;i=ne[i]){
    21. 		int j = e[i];
    22. 		dis[j] = w[i];
    23. 	}
    24.  
    25. 	for(int i=0;i
    26. 		int t = -1;
    27. 		for(int j=1;j<=n;j++){
    28. 			if(!vis[j]&&(t==-1||dis[t]
    29. 				t = j;
    30. 			}
    31. 		}
    32. 		vis[t] = 1;
    33. 		for(int i = h[t]; ~i ; i = ne[i]){
    34. 			int j = e[i];
    35. 			int minn = min(w[i],dis[t]);
    36. 			dis[j] = max(dis[j],minn); 
    37. 		} 
    38. 	}
    39. 	return dis[n];
    40. }
    41.  
    42. int main(){
    43. 	
    44. 	int t;
    45. 	scanf("%d",&t);
    46. 	int cnt=0;
    47. 	while(t--){
    48. 	
    49. 		scanf("%d%d",&n,&m);
    50. 		memset(h,-1,sizeof h);
    51. 		idx = 0;
    52. 		memset(vis,0,sizeof vis);
    53. 		memset(dis,-0x3f,sizeof dis);
    54. 		while(m--){
    55. 			int a ,b,c;
    56. 			scanf("%d%d%d",&a,&b,&c);
    57. 			add(a,b,c);
    58. 			add(b,a,c);
    59. 		}
    60. 		printf("Scenario #%d:\n%d\n\n",++cnt,dj());
    61. 	}
    62. }

    判断正环的题目

    Currency Exchange

     思路：如果有正环，那么一定可以循环无限次，让初始值变正

    1. #include
    2. #include
    3. #include
    4.  
    5. using namespace std;
    6. const int N = 200, M = N * 2;
    7.  
    8. int h[N],e[M],ne[M],idx;
    9. double wr[M],w[M];
    10.  
    11. int vis[N];
    12. double dis[N];
    13. int cnt[N];
    14. int n,m,s;
    15. double st;
    16.  
    17. void add(int a,int b,double r,double c){
    18. 	e[idx] = b;
    19. 	ne[idx] = h[a];
    20. 	wr[idx] = r;
    21. 	w[idx] = c;
    22. 	h[a] = idx++;
    23. }
    24.  
    25. bool spfa(int s)
    26. {
    27.     queue<int > q;
    28. 	q.push(s);
    29. 	vis[s] = true;
    30. 	dis[s] = st;
    31.     
    32. 	for (int i = 1; i <= n; i ++)
    33. 	{
    34. 		if(i==s)continue;
    35. 		q.push(i);
    36. 		vis[i] = 1;
    37. 	}
    38. 	
    39. 	
    40.     while (!q.empty())
    41.     {
    42.         int t = q.front();
    43.         q.pop();
    44.         vis[t] = false;
    45.         
    46.         for (int i = h[t]; ~i; i = ne[i])
    47.         {
    48.             int j = e[i];
    49.             if ((dis[t] - w[i]) * wr[i] > dis[j])
    50.             {
    51.                 dis[j] = (dis[t] - w[i]) * wr[i];
    52.                 cnt[j] = cnt[t] + 1;
    53.                 if (cnt[j] >= n) return true;
    54.                 if (!vis[j])
    55.                 {
    56.                     q.push(j);
    57.                     vis[j] = true;
    58.                 }
    59.             }
    60.         }
    61.     }
    62.     
    63.     return false;
    64. }
    65.  
    66.  
    67. int main(){
    68. 	cin >> n >> m >> s >>st;
    69. 	memset(h,-1,sizeof h);
    70. 	while(m--){
    71. 		int a,b;
    72. 		double r1,r2,c1,c2;
    73. 		cin >> a >> b >> r1 >> c1 >> r2 >> c2;
    74. 		add(a,b,r1,c1);
    75. 		add(b,a,r2,c2);
    76. 	}
    77. 	
    78. 	if(spfa(s)){
    79. 		puts("YES");
    80. 	} 
    81. 	else{
    82. 		puts("NO");
    83. 	}
    84. }

    相关题目：https://vjudge.net/problem/POJ-3259

    MPI Maelstrom

    MPI Maelstrom - POJ 1502 - Virtual Judge

    题目大意：

    建模之最短路问题
    ppt 0星 超过10%的资源 2.06MB
    下载

    题目大意：给定一个下三角矩阵，询问从1开始到其他点的最短路径中，最长的那个是多少

    思路：其实就是一个很简单的dijkstra的板子题，我们可以一遍dijkstra，跑一遍最短路，找到最大的值输出即可

    代码复制的别人的

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. const int N=110;
    6. #define MAX 0x7fffffff
    7. int map[N][N];
    8. int dis[N],visted[N],n;
    9. int dijkstra(){
    10. 	memset(visted,0,sizeof(visted));
    11. 	for(int i=0;i<=n;++i){
    12.       dis[i]=MAX;	   
    13. 	}
    14. 	dis[1]=0;
    15. 	int pos=1;visted[pos]=1;
    16. 	for(int i=1;i<=n;++i){
    17. 		for(int j=1;j<=n;++j){
    18. 		  if(!visted[j]&&map[pos][j]!=MAX&&dis[j]>dis[pos]+map[pos][j])
    19. 			  dis[j]=dis[pos]+map[pos][j];
    20. 		}
    21. 		int mmin=MAX;
    22. 		for(int j=1;j<=n;++j){
    23. 			if(!visted[j]&&dis[j]
    24. 			  mmin=dis[j];
    25. 			  pos=j;
    26. 			}
    27. 		}
    28. 		//printf("pos==%d\n",pos);
    29. 		visted[pos]=1;
    30. 	}
    31. 	int mmax=0;
    32. 	for(int i=1;i<=n;++i){
    33. 	  //printf("%d  ",dis[i]);
    34. 	  if(mmax
    35. 		  mmax=dis[i];
    36. 	}
    37. 	//cout<
    38. 	return mmax;
    39. }
    40. int main(){
    41.   //freopen("1.txt","r",stdin);
    42.   while(~scanf("%d",&n)){
    43. 	  int m;
    44. 	  char x;
    45. 	  for(int i=2;i<=n;++i){
    46. 		  for(int j=1;j
    47. 		    if(scanf("%d",&m)!=0)
    48. 				map[i][j]=map[j][i]=m;
    49. 			else{
    50. 			  map[i][j]=map[j][i]=MAX;
    51. 			  scanf("%c",&x);
    52. 			}
    53. 		  }
    54. 	  }
    55. 	  for(int i=1;i<=n;++i)
    56. 		  map[i][i]=0;
    57. 	  int xx=dijkstra();
    58. 	  printf("%d\n",xx);
    59.   }
    60.   return 0;
    61. }

    Cow Contest（floyd + 传递闭包）

    Cow Contest - POJ 3660 - Virtual Judge

    题目大意：有N头牛，评以N个等级，各不相同，先给出部分牛的等级的高低关系，问最多能确定多少头牛的等级

    思路：如果有一头关系已经确定， 那么他一定与其他所有牛关系已经确定了，即n-1头牛

    1. #include
    2. #include
    3. using namespace std;
    4. const int N = 110, M = N * 2;
    5.  
    6. int g[N][N];
    7.  
    8. int n,m;
    9.  
    10. void floyd(){
    11. 	for(int k=1;k<=n;k++){
    12. 		for(int i=1;i<=n;i++){
    13. 			for(int j=1;j<=n;j++){
    14. 				g[i][j]|=g[i][k]&&g[k][j];
    15. 			}
    16. 		}
    17. 	}
    18. }
    19.  
    20. int main(){
    21. 	cin >> n >> m;
    22. 	while(m--){
    23. 		int a, b;
    24. 		cin >> a >> b;
    25. 		g[a][b] = 1; 
    26. 	}
    27. 	
    28. 	floyd();
    29. 	
    30. 	int res = 0;
    31. 	for(int i=1;i<=n;i++){
    32. 		int cnt = 0;
    33. 		for(int j=1;j<=n;j++){
    34. 			if(g[i][j]||g[j][i]) cnt++;
    35. 		}
    36. 		if(cnt==n-1)res++;
    37. 	}
    38. 	
    39. 	cout << res <
    40. }

    队列优化的Bellmanford最短路算法（SPFA）C++实现
    zip 3星 超过45%的资源 889.0B
    下载

    Arbitrage

    套利是指利用货币汇率的差异，将一种货币的一个单位转换为同一货币的多个单位。例如，假设1美元买0.5英镑，1英镑买10.0法国法郎，1法国法郎买0.21美元。然后，通过兑换货币，聪明的交易者可以从1美元开始，购买0.5 * 10.0 * 0.21 = 1.05美元，获得5%的利润。
    您的工作是编写一个程序，以货币汇率列表作为输入，然后确定是否可能进行套利。

    输入：

    将包含一个或多个测试用例。每个测试用例的第一行有一个整数n (1<=n<=30)，表示不同货币的数量。接下来的n行每一行都包含一种货币的名称。名称中不会出现空格。下一行包含一个整数m，表示接下来的表的长度。最后的m行分别包含源货币的名称ci、表示从ci到cj的汇率的实数rij和目标货币的名称cj。没有出现在表格中的交易是不可能的。

    测试用例通过空行彼此分开。对于n，输入以0(0)的值结束

    思路：和上面找正环的思路差不多

    1. //floyed
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9.  
    10. using namespace std;
    11. int n,m;
    12. double dist[40][40];
    13. mapint> money;
    14.  
    15. void init()
    16. {
    17.     for(int i = 0;i < n;i++) {
    18.         for(int j = 0;j < n;j++){
    19.             if(i == j) dist[i][j] = 1;
    20.             else dist[i][j] = 0;
    21.         }
    22.     }
    23. }
    24.  
    25. void floyd()
    26. {
    27.     for(int k = 0;k < n;k++) {
    28.         for(int i = 0;i < n;i++) {
    29.             for(int j = 0;j < n;j++) {
    30.                 if(dist[i][j] < dist[i][k] * dist[k][j])
    31.                     dist[i][j] = dist[i][k] * dist[k][j];
    32.             }
    33.         }
    34.     }
    35. }
    36.  
    37. int main()
    38. {
    39.     int cas = 1;
    40.     string s,ss;
    41.     double r;
    42.     while(~scanf("%d",&n) &&n) {
    43.         init();
    44.         for(int i = 0;i < n;i++) {
    45.             cin >> s;
    46.             money[s] = i;
    47.         }
    48.         cin >> m;
    49.  
    50.         for(int i = 0;i < m;i++) {
    51.             cin >> s >> r >> ss;
    52.             dist[money[s] ][money[ss] ] = r;
    53.         }
    54.         floyd();
    55.         printf("Case %d: ",cas++);
    56.         for(int i = 0;i < n;i++) {
    57.             if(dist[i][i] > 1) {
    58.                 cout << "Yes" << endl;
    59.                 break;
    60.             }
    61.             else if(i == n - 1)
    62.                 cout << "No" <
    63.         }
    64.     }
    65.     return 0;
    66. }

    差分约束见另外一篇文章

  • 相关阅读:
    Netty 进阶学习（十）-- 协议设计与解析
    JavaScript 63 JavaScript 对象 63.4 JavaScript 显示对象
    Eclipse连接Mysql超详细教程
    JSR303校验,分组校验,自定义注解校验,全局异常处理
    C# 压缩图片
    【快应用】网络图片保存到相册失败案例
    lftp服务与http服务(包含scp服务)详解
    Unity开发过程中的一些小知识点
    Linux中使用Docker安装ElasticSearch7.10.x集群
    uniapp搜索功能
  • 原文地址：https://blog.csdn.net/qq_52280112/article/details/126173559