[看了官方的題解后發(fā)現(xiàn)原來是可以用最小環(huán)解這題的,轉(zhuǎn)化為圖的時(shí)候,把木板看成邊,然后木板的每個(gè)端點(diǎn)都看成一個(gè)獨(dú)立的端點(diǎn),這樣的話,如果兩塊木板相連,就把他們的端點(diǎn)相連,并且權(quán)為0,木板代表的邊權(quán)值為木板的長度,這樣的話,就可以比較好的轉(zhuǎn)化成最小環(huán)問題了,具體的可以看這里的附件]
于是只能再想辦法了,我想的是硬搜,不過不知道能不能過,但是一時(shí)沒什么其他的好辦法,就想這樣寫吧,思路如下:
dfs(now,use,l)其中now代表當(dāng)前點(diǎn),use表示哪個(gè)端點(diǎn)可用,l表示當(dāng)前的長度.那么就比較好實(shí)現(xiàn)了,代碼如下,當(dāng)然第一次我沒加注釋掉的那一句
if(l[這個(gè)是字母l] >= min) continue;然后死在第7組數(shù)據(jù)上,死了之后就想能在哪優(yōu)化不,突然發(fā)現(xiàn)可以加上這句,因?yàn)槿绻?dāng)前的已經(jīng)大于等于最優(yōu)值了,那么這個(gè)周長就不可能比最優(yōu)值還短,改了之后就過了。不過這個(gè)優(yōu)化應(yīng)該第一次就想到的 - -||慚愧 我當(dāng)時(shí)還有一個(gè)想法,就是記錄下那些"環(huán)"已經(jīng)算過,那么在這個(gè)"環(huán)"上的以其他邊為起點(diǎn)的就不用算了,比如說1-2-3形成一個(gè)環(huán),那么一開始以1為起點(diǎn)算了這個(gè)"環(huán)"的周長了,這樣的話,就不用算以2 3為起點(diǎn)的這個(gè)"環(huán)"的長度了,不過我想不出有什么好的記錄方法,所以就沒加了,如果那個(gè)有什么想法的話,可以在下面寫出來。
/*
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個(gè)端點(diǎn)是否已用 val[i]表示第i塊的長度
int idx[102];
//idx[i]第i個(gè)的下標(biāo)
short num[102][102];
//num[i][j]表示第j塊連在第i塊的哪個(gè)端點(diǎn)上
int next[102][3][102];
//next[i][j][k]第i塊的第j個(gè)端點(diǎn)連著的第k個(gè)是哪塊
int a[102][2];
//a[i][j]表示和第i塊木板的第j個(gè)端點(diǎn)連在一起的一共有多少塊木板
int min;//min:最后的結(jié)果 t_min:中間的最優(yōu)值
int start;//start表示從那塊木板出發(fā)
void dfs(int now,int use,int l)
{//now:當(dāng)前點(diǎn)的下標(biāo) use:端點(diǎn)可用情況 l:當(dāng)前路徑的長度
int i,j;
int t_use;
if(now == start && (0 != l))
{//已經(jīng)找到一個(gè) "環(huán)"
if(min > l)
{
min = l;
//printf("%d %d\n",start,l);
}
return ;
}
for(i = 1;i < 3;i++)
{
if(i&use)
{//如果這個(gè)端點(diǎn)可用
for(j = 0;j < a[now][i-1];j++)
{//每舉和這個(gè)端點(diǎn)相連的那些木板
if(0 == used[next[now][i][j]][num[next[now][i][j]][now]])
{//如果接下來的那塊木板和這塊木板相連的這個(gè)端點(diǎn)可用
t_use = 0;//算這個(gè)點(diǎn)的下一階段的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;//改變狀態(tài)
dfs(next[now][i][j],t_use,l+val[now]);//下一階段的搜索
used[next[now][i][j]][num[next[now][i][j]][now]] = 0;//狀態(tài)改回來,回溯
}
}
}
}
}
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;//這些點(diǎn)連在idx[i]這塊木板的第1個(gè)端點(diǎn)上
next[idx[i]][1][j] = k;
//第idx[i]塊木板的第1個(gè)端點(diǎn)連著的第j塊木板的下標(biāo)是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個(gè)端點(diǎn)
}
}
min = 999999999;//初始化min
for(i = 1;i <= n;i++)
{
start = i;//start用來判斷是否已經(jīng)是個(gè)"環(huán)"了
dfs(i,3,0);
}
printf("%d\n",min);
return 0;
}