我说哥们，我觉得你做的不对呀。我试了你的做法，但是边的去除是可以随便去的，不是顺序去掉的。你去除的边每次只能是先前去，或者向后去。
如果边数为6，暴力的话是6的阶乘，您能够给出具体的实现算法吗。求教。

这题如果要效率就是个动态规划

这么说吧，首先考虑不是环，6个数，5条边，假设是a1 b1 a2 b2 a3 b3 a4 b4 a5 b5 a6，其中a表示数，b表示符号，包括{+,*}

用Max[i,j]表示第i个数到第j个数运算后可能的最大值是多少，Min[i,j]表示可能的最小值

在求Max[i,j]时，考虑最后一个运算的符号是什么，如果是bk，如果bk是+，则Max[i,j]=Max[i,k]+Max[k+1,j]
                                                        如果bk是*，则Max[i,j]=(Max[i,k]*Max[k+1,j],Max[i,k]*Min[k+1,j],Min[i,k]*Max[k+1,j],Min[i,k]*Min[k+1,j])

求Min函数方法类似

然后考虑环的问题，之前我们一直考虑的链，一种方法是把环拆成n个链，对每个链算一次，总的时间复杂度就是O(N^3)

另外一种方法就是把链在结尾再复制一遍，a1 b1 a2 b2.......a6 b6 --->   a1 b1 a2 b2.....a6 b6 a1 b1 .....a6

对这个链进行动态规划就只有O(n^2)复杂度了，可以在1s内求出最多10W个顶点左右的数据的最大值

[ 本帖最后由 czz5242199 于 2012-10-17 15:51 编辑 ]

首先谢谢你的回复，你的递推式我能够看懂，但是如果是环的话，你说复制到链表的最后，那么此时算呢，可以给出代码或者有没有参考的网页或书籍吗？

     1    //bccn.c
     2    #include <stdio.h>
     3    #include <stdlib.h>
     4   
     5    enum opr
     6    {
     7        ADD = 1,
     8    //    SUB,
     9        MUL = 2,
    10    //    DIV,
    11    };
    12   
    13    int *head_array;
    14    int *node_array;
    15   
    16    int f(int x, int y, int size)
    17    {
    18        int i;
    19        int sum = 0;
    20   
    21        for (i=0; i<x; ++i)
    22        {
    23            --size;
    24            sum += size;
    25        }
    26        sum += y;
    27   
    28        return sum;
    29    }
    30   
    31    void uf(int *x, int *y, int size, int sum)
    32    {
    33        for (*x = 0; *x <= sum; ++(*x))
    34        {
    35            --size;
    36            *x += size;
    37        }
    38        if (0 != *x)
    39        {
    40            *x -= size;
    41        }
    42        *y = sum - *x;
    43    }
    44   
    45    int cacu(int size)
    46    {
    47        int i = (size * (size - 1))/2;
    48        int x = 0, y = 0;
    49        int flag = 1;
    50        int max = 0;
    51   
    52        while (i)
    53        {
    54            uf(&x, &y, size, i-1);
    55            switch (node_array[i-1])
    56            {
    57            case ADD:
    58                node_array[i-1] = head_array[x+1] + head_array[y+2+x];
    59                break;
    60    //        case SUB:
    61                break;
    62            case MUL:
    63                node_array[i-1] = head_array[x+1] * head_array[y+2+x];
    64                break;
    65    //        case DIV:
    66                break;
    67            default:
    68                break;
    69            }
    70            if (flag)
    71            {
    72                flag = 0;
    73                max = node_array[i-1];
    74            }
    75            else
    76            {
    77                max = max>node_array[i-1]? max : node_array[i-1];
    78            }
    79   
    80            --i;
    81        }
    82   
    83        return max;
    84    }
    85   
    86    int main(void)
    87    {
    88        int size;
    89        int arc;
    90        int i;
    91        int vec1, vec2;//边的两点
    92        int operator;//操作码[1, 4]
    93   
    94        printf ("输入结点个数:");
    95        scanf("%d", &size);
    96   
    97        head_array = malloc (sizeof(int)*(size+1));
    98        memset(head_array, 0, sizeof(int)*(size+1));
    99        node_array = malloc (sizeof(int)*((size*(size-1))/2));
   100        memset(node_array, 0, sizeof(int)*((size*(size-1))/2));
   101   
   102        printf ("依次输入结点上的数据:");
   103        for (i = 1; i <= size; ++i)
   104        {
   105            scanf("%d", &(head_array[i]));
   106        }
   107        printf ("\t结点上的数据分别为");
   108        for (i = 1; i <= size; ++i)
   109        {
   110            printf ("(%d, %d) ", i, head_array[i]);
   111        }
   112        printf ("\n");
   113   
   114        printf ("\t输入边的条数\n");
   115        scanf("%d", &arc);
   116        for (i = 1; i <= arc; ++i)
   117        {
   118            printf ("输入边的信息(1<=vec1<vec2):");
   119            scanf("%d %d %d", &vec1, &vec2, &operator);
   120            node_array[f(vec1-1, vec2-1-vec1, size)] = operator;
   121        }
   122       
   123        printf ("最大值为:%d\n", cacu(size));
   124   
   125        return 0;
   126    }

输入结点个数:3
依次输入结点上的数据:40 50 2
    结点上的数据分别为(1, 40) (2, 50) (3, 2)
    输入边的条数
3
输入边的信息(1<=vec1<vec2):1 2 1
输入边的信息(1<=vec1<vec2):2 3 2
输入边的信息(1<=vec1<vec2):1 3 2
最大值为:100

typedef struct elme{
    int num;                /*顶点数据存放位置*/
   char yuansuanfu;        /*运算符的存放位置*/
struct elme *next;        /*前驱*/
struct elme *prev;       /*后驱*/
}elem;
int main()
{
   int bian;  
   elem *head;
   elem *creat_duobian(int n);
   int  jisuanjieguo(elem *head);
  
   printf("请输入多边形的边数：  ");
   scanf("%d\n",&bian);
   head=creat_duobian(bian);
   jisuanjieguo(head);
}

elem *creat_duobian(int n)
{
   elem *p,*p1,head;
   int i=1;
   head=(elem *)malloc(sizeof(elem));
   printf("请输入%d顶点数据: ",i);
   scanf("%d\n",&head->num);
   printf("请输入%d边上的运算符"，i);
   scanf("%c\n",&head->yuansuanfu);
   head->next=NULL;
   head->prev=NULL;
   p=head;
   for(i=2;i<=n;i++){
     p1=(elem *)malloc(sizeof(elem));
     printf("请输入%d顶点数据: ",i);
     scanf("%d\n",&p1->num);
     printf("请输入%d边上的运算符"，i);
     scanf("%c\n",&p1->yuansuanfu);
     p->next=p1;
     p1->prev=p;
     p1->next=NULL;
     p=p1;
    }
    head->prev=p;
    p->next=head;
}
计算过程自己写  上面是循环链表的建立。
  
   
   
     
     
   
   

[ 本帖最后由 zhu224039 于 2012-10-18 15:23 编辑 ]