---

题目描述：

　　有N段篱笆(1≤N≤100)，给出与每段篱笆两段相连的篱笆，输出其中周长最小的环的长度（没有篱笆自己形成一个环）。

思考&分析：

　　首先这个输入很坑爹，竟然是边与边的关系--你需要把它转化成一个正常一点的图。

　　感谢USACO，本题并不存在重边。

　　记一条边的两端分别为A端和B端，首先对于一条边A端连出去的边，如果该边已经处理过，那么判断连该边连它的是哪一端，如果是A端，那么其A端与该边A端一样，否则与该边B端一样（幸好不存在一条边两端都连了另一条边的情况），如果没有连边已经处理过，那么就认为这个点是新开的一个点。B端同理。这样你就能得到一个正常一点的图了。

　　然而本题的核心是求一个最小环，下面给出一个比较容易想到的思路：

　　由于不存在重边，你先假设这条边是最小环中的，然后你把这条边断掉，求出这条边的一个端点到另一个端点的最短路，最短路+这条边的权值就是这条边的最小环，更新最小值即可。

　　USACO的ANALYSIS提供了一个加速方法：如果一条边大于等于当前的最小值，那么这条边就是无用的，在求后面的最短路时可以将这条边删去。

　　这个做法的总时间复杂度为O(边数*单源最短路的时间复杂度)。

　　然后另一种方法直接是用floyd求的（神奇）。

　　注意floyd的DP本质：f[k][i][j]表示前k个点从i到j的最短路（当然k这一维省去了）。

　　那么在用点k更新之前，f[i][j]+edge[i][k]+edge[k][j]就是i到j的最小环（但是问题是i!=j，不要以为这个没关系，我就因为这个WA了）。

　　总时间复杂度O(N^3)，而且代码非常简短。

贴代码：

最短路+删边：

#include
     
      using namespace std;const int maxn=205;int n,N,A[105],B[105],head[205],tot;int Q[205],front,rear,dis[205];bool flag[205],vis[205];bool Left[105][105],Right[105][105];struct E{    int to,len,next;}edge[105*2];void init(){    memset(head,-1,sizeof(head)),tot=0;    memset(flag,1,sizeof(flag));}void makedge(int u,int v,int t){    edge[tot].to=v;    edge[tot].len=t;    edge[tot].next=head[u];    head[u]=tot++;}void push(int x){    vis[x]=1;    Q[rear]=x;    rear=(rear+1)%maxn;}void spfa(int s){    int u,v;    memset(dis,31,sizeof(dis));    memset(vis,0,sizeof(vis));    front=rear=dis[s]=0,push(s);    while (front
      
       =Min)            flag[j*2-2]=flag[j*2-1]=0;    }    printf("%d\n",Min);    return 0;}
      
     

floyd：

#include
     
      using namespace std;int n,N,A[105],B[105];int f[205][205],edge[205][205];bool Left[105][105],Right[105][105];int main(){    freopen("fence6.in","r",stdin);    freopen("fence6.out","w",stdout);    memset(Left,0,sizeof(Left));    memset(Right,0,sizeof(Right));    memset(f,31,sizeof(f));    memset(edge,31,sizeof(edge));    scanf("%d",&n),N=0;    for (int i=1,s,L,n1,n2,x;i<=n;i++){        scanf("%d%d%d%d",&s,&L,&n1,&n2);        for (int j=1;j<=n1;j++){            scanf("%d",&x);            if (Left[x][s]) A[s]=A[x];            if (Right[x][s]) A[s]=B[x];            Left[s][x]=1;        }        if (!A[s]) A[s]=++N;        for (int j=1;j<=n2;j++){            scanf("%d",&x);            if (Left[x][s]) B[s]=A[x];            if (Right[x][s]) B[s]=B[x];            Right[s][x]=1;        }        if (!B[s]) B[s]=++N;        f[A[s]][B[s]]=f[B[s]][A[s]]=L;        edge[A[s]][B[s]]=edge[B[s]][A[s]]=L;    }    int Min=1e8;    for (int k=1;k<=N;k++){        for (int i=1;i<=N;i++)        for (int j=1;j<=N;j++)        if (i!=j)            Min=min(Min,f[i][j]+edge[i][k]+edge[k][j]);        for (int i=1;i<=N;i++)        for (int j=1;j<=N;j++)            f[i][j]=min(f[i][j],f[i][k]+f[k][j]);    }    printf("%d\n",Min);    return 0;}