地址
题意就是求最小周长,一开始我想画成图论,然后用类似dij的算法求最小环长,可是发现两个端点会出现冲突.我一开始的思路是,把每块木板当成一个点,然后选一个端点当成出边,另外一个端点当成入边,权值等于"起点"[这里是某快木板]的长度,可是会出现冲突,样例就是一个很好的例子,会出现到了某个点是,它必须又是起始点又是终止点.那么这样就出问题了.

[看了官方的题解后发现原来是可以用最小环解这题的,转化为图的时候,把木板看成边,然后木板的每个端点都看成一个独立的端点,这样的话,如果两块木板相连,就把他们的端点相连,并且权为0,木板代表的边权值为木板的长度,这样的话,就可以比较好的转化成最小环问题了,具体的可以看这里的附件]
于是只能再想办法了,我想的是硬搜,不过不知道能不能过,但是一时没什么其他的好办法,就想这样写吧,思路如下:
dfs(now,use,l)其中now代表当前点,use表示哪个端点可用,l表示当前的长度.那么就比较好实现了,代码如下,当然第一次我没加注释掉的那一句
if(l[这个是字母l] >= min) continue;然后死在第7组数据上,死了之后就想能在哪优化不,突然发现可以加上这句,因为如果当前的已经大于等于最优值了,那么这个周长就不可能比最优值还短,改了之后就过了。不过这个优化应该第一次就想到的 - -||惭愧     我当时还有一个想法,就是记录下那些"环"已经算过,那么在这个"环"上的以其他边为起点的就不用算了,比如说1-2-3形成一个环,那么一开始以1为起点算了这个"环"的周长了,这样的话,就不用算以2 3为起点的这个"环"的长度了,不过我想不出有什么好的记录方法,所以就没加了,如果那个有什么想法的话,可以在下面写出来。

/*
   ID:qcx97811
   LANG:C++
   PROG:fence6
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int n;
int used[102][3],val[102];
//used[i][j]表示第i块的第j个端点是否已用 val[i]表示第i块的长度
int idx[102];
//idx[i]第i个的下标
short num[102][102];
//num[i][j]表示第j块连在第i块的哪个端点上
int next[102][3][102];
//next[i][j][k]第i块的第j个端点连着的第k个是哪块
int a[102][2];
//a[i][j]表示和第i块木板的第j个端点连在一起的一共有多少块木板
int min;//min:最后的结果 t_min:中间的最优值
int start;//start表示从那块木板出发

void dfs(int now,int use,int l)
{//now:当前点的下标  use:端点可用情况   l:当前路径的长度
    int i,j;
    int t_use;
    if(now == start && (0 != l))
        {//已经找到一个 "环"
            if(min > l)
                {
                    min = l;
                    //printf("%d   %d\n",start,l);
                }
            return ;
        }
    for(i = 1;i < 3;i++)
        {
            if(i&use)
                {//如果这个端点可用
                    for(j = 0;j < a[now][i-1];j++)
                        {//每举和这个端点相连的那些木板
                           if(0 == used[next[now][i][j]][num[next[now][i][j]][now]])
                                {//如果接下来的那块木板和这块木板相连的这个端点可用
                                    t_use = 0;//算这个点的下一阶段的use值
                                    if(used[next[now][i][j]][0] == 0)
                                        t_use += 1;
                                    if(used[next[now][i][j]][1] == 0)
                                        t_use += 2;
                                   /* if(l >= min) ///这里不能注释掉 注释掉就TLE  --------------------------------------
                                       continue; *//这里     ===================================
                                    t_use = t_use-num[next[now][i][j]][now];
                                    used[next[now][i][j]][num[next[now][i][j]][now]] = 1;//改变状态
                                    dfs(next[now][i][j],t_use,l+val[now]);//下一阶段的搜索
                                    used[next[now][i][j]][num[next[now][i][j]][now]] = 0;//状态改回来,回溯
                             }   
                        }
                }               

        }
}
int main(int argv,char **argc)
{
    freopen("fence6.in","r",stdin);
    freopen("fence6.out","w",stdout);
    int i,j,k;
    scanf("%d",&n);
    for(i = 0;i < n;i++)
        {
            scanf("%d",&idx[i]);
            scanf("%d",&val[idx[i]]);
            scanf("%d%d",&a[idx[i]][0],&a[idx[i]][1]);
            for(j = 0;j < a[idx[i]][0];j++)
                {
                    scanf("%d",&k);
                    num[idx[i]][k] = 1;//这些点连在idx[i]这块木板的第1个端点上
                    next[idx[i]][1][j] = k;
                    //第idx[i]块木板的第1个端点连着的第j块木板的下标是k
                }
            for(j = 0;j < a[idx[i]][1];j++)
                {
                    scanf("%d",&k);
                    num[idx[i]][k] = 2;
                    next[idx[i]][2][j] = k;
                    //注释和上面相似 不过这里是第idx[i]块木板的第2个端点
                }   

        }
    min = 999999999;//初始化min
    for(i = 1;i <= n;i++)
        {
            start = i;//start用来判断是否已经是个"环"了
            dfs(i,3,0);
        }
    printf("%d\n",min);
    return 0;
}