动态规划类似FLOYD dp[i][j][k] 表示第i个点经过K次到达j点能获得的最大利润
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} #define MAXN 25 double G[MAXN][MAXN]; double dp[MAXN][MAXN][MAXN]; int fa[MAXN][MAXN][MAXN]; int N; int cnt,ans; void init() { memset(dp,0,sizeof(dp)); memset(fa,0,sizeof(fa)); for (int i = 1; i <= N; i++) { dp[i][i][1] = 1.0; for (int j = 1; j <= N; j++) { fa[i][j][1] = i; if (i == j) continue; scanf("%lf",&dp[i][j][1]); } } } bool judge() { for (int k = 2; k <= N; k++) for (int i = 1; i <= N; i++) if (dp[i][i][k] > 1.01) { ans = i; cnt = k; //8 printf("%d %d ",ans,cnt); return true; } return false; } void output(int x,int y,int cnt) { if (cnt == 0) {printf("%d",x);return ;} //printf("%d %d %d %d ",x,y,cnt,fa[x][y][cnt]); output(x,fa[x][y][cnt],cnt - 1); printf(" %d",y); } int main()//节点i通过K次转换到达节点j能拿到的钱 { // freopen("sample.txt","r",stdin); while (scanf("%d",&N) != EOF) { init(); for (int k = 2; k <= N; k++) for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) for (int p = 1; p <= N; p++) { if (dp[i][j][k] < dp[i][p][k - 1] * dp[p][j][1]) { dp[i][j][k] = dp[i][p][k - 1] * dp[p][j][1]; fa[i][j][k] = p;//在i经过K次转换到P的过程中第K 是p->j } } bool found = judge(); if (!found) puts("no arbitrage sequence exists"); else { output(ans,ans,cnt); putchar(' ');} } return 0; }