本文主要是介绍UVa125 - Numbering Paths，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：一个有向图，统计每对顶点间有多少条路径，如果有无数条（路径中有环），用-1表示。
思路：Floyd算法变形。是这样的，假设i和j是两个顶点，它们之间的一条完整的路，除了i到j直连，路径中序号最大的顶点可以是k（k=0，1，2，3......）。用ans[i][j]表示i和j之间路径的数目，那么路径中最大序号顶点为k的那一类路径的数目为ans[i][k]*ans[k][j]，循环统计一次就好了。
还有个问题，如果有无数条路径，需要检测出来。我的方法是重新循环一遍，当ans[k][k]不为0时，说明遇到了环，作相应的处理就好了。
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;int ans[50][50];
int main(){int n;int count=0;while(cin>>n){memset(ans,0,sizeof(ans));int u,v;int maxspe=0;for(int i=1;i<=n;i++){scanf("%d%d",&u,&v);if(u>maxspe)maxspe=u;if(v>maxspe)maxspe=v;ans[u][v]++;}//for(int k=0;k<=maxspe;k++){for(int i=0;i<=maxspe;i++){if(i==k)continue;for(int j=0;j<=maxspe;j++){if(j==k)continue;ans[i][j]+=ans[i][k]*ans[k][j];}}}for(int k=0;k<=maxspe;k++){for(int i=0;i<=maxspe;i++){for(int j=0;j<=maxspe;j++){if(ans[k][k]&&ans[i][k]&&ans[k][j])ans[i][j]=-1;}}}printf("matrix for city %d\n",count);count++;for(int i=0;i<=maxspe;i++){for(int j=0;j<=maxspe;j++){cout<<ans[i][j];if(j!=maxspe)cout<<" ";}cout<<endl;}}return 0;
}
这篇关于UVa125 - Numbering Paths的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
