P2738 [USACO4.1]籬笆回路Fence Loops

題目描述

農(nóng)夫布朗的牧場(chǎng)上的籬笆已經(jīng)失去控制了。它們分成了1~200英尺長(zhǎng)的線段。只有在線段的端點(diǎn)處才能連接兩個(gè)線段，有時(shí)給定的一個(gè)端點(diǎn)上會(huì)有兩個(gè)以上的籬笆。結(jié)果籬笆形成了一張網(wǎng)分割了布朗的牧場(chǎng)。布朗想將牧場(chǎng)恢復(fù)原樣，出于這個(gè)考慮，他首先得知道牧場(chǎng)上哪一塊區(qū)域的周長(zhǎng)最小。 布朗將他的每段籬笆從1到N進(jìn)行了標(biāo)號(hào)（N=線段的總數(shù)）。他知道每段籬笆有如下屬性：

該段籬笆的長(zhǎng)度

該段籬笆的一端所連接的另一段籬笆的標(biāo)號(hào)

該段籬笆的另一端所連接的另一段籬笆的標(biāo)號(hào)

幸運(yùn)的是，沒(méi)有籬笆連接它自身。對(duì)于一組有關(guān)籬笆如何分割牧場(chǎng)的數(shù)據(jù)，寫(xiě)一個(gè)程序來(lái)計(jì)算出所有分割出的區(qū)域中最小的周長(zhǎng)。

例如，標(biāo)號(hào)1~10的籬笆由下圖的形式組成（下面的數(shù)字是籬笆的標(biāo)號(hào)）：

1+---------------+|\ /|2| \7 / | | \ / | +---+ / |6 | 8 \ /10 | 3| \9 / | | \ / | +-------+-------+ 4 5

上圖中周長(zhǎng)最小的區(qū)域是由2，7，8號(hào)籬笆形成的。

輸入輸出格式

輸入格式：

?

第1行: N (1 <= N <= 100)

第2行到第3*N+1行: 每三行為一組，共N組信息:

每組信息的第1行有4個(gè)整數(shù): s, 這段籬笆的標(biāo)號(hào)(1 <= s <= N); Ls, 這段籬笆的長(zhǎng)度 (1 <= Ls <= 255); N1s (1 <= N1s <= 8) 與本段籬笆的一端 所相鄰的籬笆的數(shù)量; N2s與本段籬笆的另一端所相鄰的籬笆的數(shù)量。 (1 <= N2s <= 8).

每組信息的的第2行有 N1s個(gè)整數(shù), 分別描述與本段籬笆的一端所相鄰的籬笆的標(biāo)號(hào)。

每組信息的的第3行有N2s個(gè)整數(shù), 分別描述與本段籬笆的另一端所相鄰的籬笆的標(biāo)號(hào)。

?

輸出格式：

?

輸出的內(nèi)容為單獨(dú)的一行，用一個(gè)整數(shù)來(lái)表示最小的周長(zhǎng)。

?

輸入輸出樣例

輸入樣例#1：
10 1 16 2 2 2 7 10 6 2 3 2 2 1 7 8 3 3 3 2 1 8 2 4 4 8 1 3 3 9 10 5 5 8 3 1 9 10 4 6 6 6 1 2 5 1 10 7 5 2 2 1 2 8 9 8 4 2 2 2 3 7 9 9 5 2 3 7 8 4 5 10 10 10 2 3 1 6 4 9 5 輸出樣例#1：
12

說(shuō)明

題目翻譯來(lái)自NOCOW。

USACO Training Section 4.1

思路：floyed找最小環(huán)

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 110 using namespace std; int n,num,tot,minn=0x3f3f3f3f; struct nond{int id,len,lsum,rsum;int a[2][110];int b[2][110]; }edge[110]; int dy[240]; int map[110][110],dis[110][110]; int cmp(nond x,nond y){return x.id<y.id; } int main(){memset(dy,-1,sizeof(dy));memset(map,0x3f,sizeof(map));memset(dis,0x3f,sizeof(dis));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d",&edge[i].id,&edge[i].len,&edge[i].lsum,&edge[i].rsum);for(int j=1;j<=edge[i].lsum;j++){int z;scanf("%d",&z);edge[i].a[0][j]=z;edge[i].b[0][z]=1;}for(int j=1;j<=edge[i].rsum;j++){int z;scanf("%d",&z);edge[i].a[1][j]=z;edge[i].b[1][z]=1;}}sort(edge+1,edge+1+n,cmp);for(int i=1;i<=n;i++){for(int j=1;j<=edge[i].lsum;j++){int v=edge[i].a[0][j];if(edge[v].b[0][i]&&dy[v*2-1]!=-1)dy[i*2-1]=dy[v*2-1];else if(edge[v].b[1][i]&&dy[v*2]!=-1)dy[i*2-1]=dy[v*2];if(dy[i*2-1]!=-1) break;}if(dy[i*2-1]==-1)dy[i*2-1]=++tot;for(int j=1;j<=edge[i].rsum;++j){int v=edge[i].a[1][j];if(edge[v].b[0][i]&&dy[v*2-1]!=-1)dy[i*2]=dy[v*2-1];else if(edge[v].b[1][i]&&dy[v*2]!=-1)dy[i*2]=dy[v*2];if(dy[i*2]!=-1) break;}if(dy[i*2]==-1)dy[i*2]=++tot;map[dy[i*2-1]][dy[i*2]]=map[dy[i*2]][dy[i*2-1]]=edge[i].len;dis[dy[i*2-1]][dy[i*2]]=dis[dy[i*2]][dy[i*2-1]]=edge[i].len;}for(int k=1;k<=tot;k++){for(int i=1;i<k;i++)for(int j=i+1;j<k;j++)minn=min(dis[i][j]+map[j][k]+map[k][i],minn);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j&&j!=k&&i!=k)if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];}cout<<minn; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cangT-Tlan/p/7576931.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 P2738 [USACO4.1]篱笆回路Fence Loops的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。