地址
题意就是求最小周长,一开始我想画成图论,然后用类似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;
}