40-实战演练

4.7.5　实战演练

//program 4-5
#include<iostream>
#include<sstream>
#include<cmath>
#include<algorithm>
using namespace std;
const int M= 1000 + 5 ;
int n ;
int s[M][M] ;
double m[M][M],g[M][M];
void Convexpolygontriangulation()
{
    for(int i = 1 ;i <= n ; i++)           // 初始化
    {
         m[i][i] = 0 ;
         s[i][i] = 0 ;
    }
    for(int d = 2 ;d <= n ; d++)        //d为问题规模，d=2时，实际上是三个点
                                        //因为我们的m[i][j]表示的是{vi-1，vi，vj}
      for(int i = 1 ;i <= n - d + 1 ; i++)  // 控制i值
      {
           int j = i + d - 1 ;          // j值
           m[i][j] = m[i+1][j] + g[i-1][i] + g[i][j] + g[i-1][j] ;
           s[i][j] = i ;
           for(int k = i + 1 ;k < j ; k++)     // 枚举划分点
           {
                double temp = m[i][k] + m[k+1][j] + g[i-1][k] + g[k][j] + g[i-1][j] ;
                if(m[i][j] > temp)
                {
                     m[i][j] = temp ;   // 更新最优值
                     s[i][j] = k ;      // 记录划分点
                }
           }
       }
}
void print(int i , int j)               // 输出所有的弦
{
     if(i == j)  return ;
     if(s[i][j]>i)
        cout<<"{v"<<i-1<<"v"<<s[i][j]<<"}"<<endl;
     if(j>s[i][j]+1)
        cout<<"{v"<<s[i][j]<<"v"<<j<<"}"<<endl;
     print(i ,s[i][j]);
     print(s[i][j]+1 ,j);
 }
int main()
{
     int i,j;
     cout << "请输入顶点的个数 n:";
     cin >> n;
     n-- ;
     cout << "请依次输入各顶点的连接权值:";
     for(i = 0 ;i <= n ; ++i)           // 输入各个顶点之间的连接权值
          for( j = 0 ;j <= n ; ++j)
                cin>>g[i][j] ;
     Convexpolygontriangulation ();
     cout<<m[1][n]<<endl;
     print(1 ,n);                       // 打印路径
     return 0 ;
}

算法实现和测试

（1）运行环境

Code::Blocks

Visual C++ 6.0

（2）输入

6
0  2  3   1   5   6
2  0  3   4   8   6
3  3  0   10  13  7
1  4  10  0   12  5
5  8  13  12  0   3
6  6  7   5   3   0

（3）输出

54
{ v0 v3 }
{ v3 v5 }
{ v0 v2 }