[看了官方的題解后發現原來是可以用最小環解這題的,轉化為圖的時候,把木板看成邊,然后木板的每個端點都看成一個獨立的端點,這樣的話,如果兩塊木板相連,就把他們的端點相連,并且權為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;
}