一看就是求最小環(huán)，但是構(gòu)圖非常惡心。按照我樸素的思維方式，想了N天N夜，想到了利用BFS（或DFS）給定點(diǎn)標(biāo)號(hào)，然后在建邊的算法。
時(shí)空復(fù)雜度理論上都是很好的。但今天一上機(jī)就慫了，因?yàn)榫幊虖?fù)雜度太大。又思考了一段時(shí)間無解之后，我求助于NOCOW。
了解了一種把邊看作點(diǎn)，然后給邊直接連上“邊”的算法。實(shí)際操作中也遇到一些困惑，這里就不提了，主要是floyd算法的細(xì)節(jié)要注意。
我對(duì)該算法的細(xì)節(jié)認(rèn)識(shí)：
1.k在外循環(huán)，只有前k個(gè)點(diǎn)是更新完的。
2.Infinity 不能取太大，會(huì)爆的。
具體的注釋在代碼中了
代碼
/*
USER:zyn19961
LANG:C++
TASK:fence6
*/
#include<cstdio>
#include<cstring>
const int INF=1<<25;//不能取太大
int n,a[200][200],b[200][200],l[200],left[200][200],right[200][200];
int inline min(int a,int b){return a<b?a:b;}
int s,ans;
int main()
{
freopen("fence6.in","r",stdin);
freopen("fence6.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=INF;
for(int i=1;i<=n;i++){
scanf("%d",&s);
scanf("%d",&l[s]);
scanf("%d %d",&left[s][0],&right[s][0]);
for(int j=1;j<=left[s][0];j++)
scanf("%d",&left[s][j]);
for(int j=1;j<=right[s][0];j++)
scanf("%d",&right[s][j]);
}
//邊->點(diǎn) 轉(zhuǎn)化
for(int i=1;i<=n;i++){
for(int j=1;j<=left[i][0];j++)
a[i][left[i][j]]=l[i]+l[left[i][j]];//取兩邊的邊長和作為兩邊之間“邊”的權(quán)值
for(int j=1;j<=right[i][0];j++)
a[i][right[i][j]]=l[i]+l[right[i][j]];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][j];//a為i，j間的最短路，b為邊權(quán).
//
ans=INF<<4;
for(int k=1;k<=n;k++){//經(jīng)過k點(diǎn)
for(int i=1;i<=left[k][0];i++){//向左
int x=left[k][i];//只是寫起來方便而已，下同
if(x<k){//只能更新前k-1個(gè)點(diǎn)換
for(int j=1;j<=right[k][0];j++){//向右
int y=right[k][j];
if(y<k)//只能更新前k-1個(gè)點(diǎn)之間的環(huán)
ans=min(ans,a[x][y]+b[k][x]+b[k][y]);
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
printf("%d\n",ans/2);//這個(gè)顯然
fclose(stdin);
fclose(stdout);
return 0;
}
關(guān)于代碼最后輸出 顯然的結(jié)論的說明:
在一個(gè)環(huán)中，每條邊經(jīng)過一次，且首尾相接。
這個(gè)環(huán)上的“邊”連接這圖中的邊集中的兩個(gè)邊，
且每條邊恰好被連接兩次.故ans要/2