听懂了

我用10楼的代码测试了一下~发现还有更优解~

12345321345
51234521345
还有更优解
153421345
不过题主思路还是很不错的~输入一组数据直接在输出序列里面处理然后就可以不利用原来的输入序列了~这个可以借鉴~我还是关注一下吧~还要抽个时间看看具体哪里有漏洞才行~

[此贴子已经被作者于2017-4-30 08:49编辑过]

这题应该属于拓补排序~拓补排序在排序处理过程难免会出现等权值的分支~这时候要对每个分支进行讨论~所以感觉算法复杂度还是蛮高的~最后结果也可能没有唯一解甚至无解(这题虽然不能确保有唯一解但不会无解)~

对于这题数字理解应该是它不是唯一的~只是代表一个 "类"~~还是以12楼的测试数据为例~第一行的3和第二行的3可以指同一个"3"也可以指是不同的"3"~对于第一行"5"要在"3"后面而第二行则要求"3"在"5"的后面~这样就会出现条件冲突~所以有两种解决方案~第一种是把"5"加在"3"的后面第二种是把"3"加在"5"的后面~~
但这样符合条件的分支就有4个~就要对这四个分支进行下一步讨论然后剪枝~

512345
152345
125345
123453

局部考虑最优解是否行得通还有待验证~

@楼主

这题要求输出其中一个解~不过往往没有唯一解~
不如把输出条件换成输出合并后数列长度(输出解只是辅助补充验证说明)~~~

[此贴子已经被作者于2017-4-30 08:41编辑过]

收到的鲜花

• 寒风中的细雨 于 2017-05-01 00:12 送鲜花  5朵   附言：取得的结果最短就可

我觉得只是看起来有点像拓朴排序。问题是拓朴排序不支持有向环路。这里出现了有向环路情况大不一样了。还能不能在拓朴排序的基础上改都不一定吧？我觉得

收到的鲜花

• 九转星河 于 2017-04-30 08:53 送鲜花  10朵   附言：多谢提醒~

对哦~我也查过一下拓补排序不支持有回路~~我可以自己人为优化推导出最优解~不过还不能找到一个系统的程序方法~不过就算想到了算法复杂度也应该不低~

PS:@楼主

一楼的案例另解

385753214~~~

[此贴子已经被作者于2017-4-30 09:00编辑过]

目前想到的方法就是先找其中一个解~然后再通过不断调整数字来满足条件的解能否删去一些数字~~这样数据较大的时候可能会出现庞大的数据分支~可能除了全面搜索外没有一个能确保最优解的算法~这题有环路就是和普通拓补排序不同的地方~

而且感觉队列数据不能用完就删~因为优化时还需要通过队列数据来作为条件判断~

[此贴子已经被作者于2017-4-30 10:12编辑过]

嗯，再想想！

。。。怎么删掉自己的发言，不会

[此贴子已经被作者于2017-5-1 08:47编辑过]

劳动节的劳动！不知道正确与否，还望各大神测试。
上午和闺蜜就在附近海滩逛了逛，玩的也不尽兴，脑子一直在考虑这个题目解决方法。突然想到把行变成列，那么这一列的数据顺序可随便调换的，只要每列的顺序正确即可，迫不及待回宿舍码代码，弄得头昏眼花的，简单测试了题主和九版主的数据，结果一致，现提交如下：

5
5 1 2 3 4 5
5 5 3 2 1 4
5 1 3 4 2 5
5 4 2 1 3 5
5 2 1 3 4 5
3
6 5 7 3 2 1 4
3 3 8 5
4 7 5 3 2
0
总系列函数(0退出)：1 5 3 4 2 1 3 4 5 
总系列函数(0退出)：5 3 7 8 5 3 2 1 4 
总系列函数(0退出)：

#include <stdio.h>
int finddat(int *a,int l,int dat)
{//在长度为l的数组a里找数dat；找到返回其位置，否则返回-1
    int j=-1;
    for(;l&&a[l-1]!=dat;l--);
    if(l)j=l-1;
    return j;
}
void list(char a[][100],char *b,int row)
{//显示调试步骤用，正常情况下不调用。
    int i,j;
    for(i=0,printf("\n");i<row;i++,printf("\n"))
        for(j=0;a[i][j]>=0;j++)
            printf("%d ",a[i][j]);;
    printf("---");
    for(i=0;b[i]>=0;i++)printf("%d ",b[i]);
    printf("\n");
}
void shortser(char a[][100],char *b,int row)
{//求最短系列，结果在数组b中返回
    int i,j,k,p,c,t;
    for(i=0;i<row;i++)
    {//对第一列的处理
        c=a[i][0];
        for(j=0;j<row&&a[i][0]==a[j][0];j++);
        if(j>=row)break;
        for(j=0;b[j]>=0;j++);
        b[j]=c;
        b[j+1]=-1;
        for(j=0;j<row;j++)
        {
            if(a[j][0]==c)
            {
                for(k=0;a[j][k]>=0;k++)a[j][k]=a[j][k+1];
            }
        }
    }
    while(1)
    {//差不多等效我在http://bbs.bccn.net/thread-472197-1-1.html里5楼的递归处理
        for(i=0;i<row&&a[i][0]<0;i++);
        if(i>=row)break;
        for(i=p=0,c=100;i<row;i++)
        {
            for(j=t=0;j<row;j++)
            {
                for(k=1;a[j][k]>=0;k++)if(a[j][k]==a[i][0])t++;
            }
            if(t<c)
            {
                c=t;
                p=a[i][0];
            }
        }
        for(i=0;i<row;i++)
        {
            if(a[i][0]==p||p<0)
            {
                if(p<0)p=a[i][0];
                for(j=0;a[i][j]>=0;j++)a[i][j]=a[i][j+1];
            }
        }
        for(i=0;b[i]>=0;i++);
        b[i]=p;
        b[i+1]=-1;
    }
}
void main()
{
    int i,j,k,m,n,t,s,a[10000];
    char b[100][100],c[10000];    //数组a用于存储输入的数，数组b用于存储每组数据的索引表，数组c为结果索引表
    printf("总系列函数(0退出)：");
    while(scanf("%d",&n)&&n)
    {
        for(i=s=0;i<n;i++)
        {//接受输入，建立索引表
            scanf("%d",&k);
            for(j=0;j<k;j++)
            {
                scanf("%d",&t);
                m=finddat(a,s,t);
                if(m<0)
                {
                    b[i][j]=s;
                    a[s]=t;
                    s++;
                }
                else b[i][j]=m;
                b[i][j+1]=-1;
            }
        }
        c[0]=-1;
        shortser(b,c,n);
        for(i=0;c[i]>=0;i++)printf("%d ",a[c[i]]);  //输出最短系列
        printf("\n");
        printf("总系列函数(0退出)：");
    }
}

用列来比较这个我还没有完全消化~不过感觉已经比之前的代码解接近了很多~再看看~~~