Fence Loops 篱笆回路
Time Limit: 1 Sec Memory Limit: 128 MBDescription
农夫布朗的牧场上的篱笆已经失去控制了.它们分成了1~200 英尺长的线段.只有在线段的端点处才能连接两个线段,有时给定的一个端点上会有两个以上的篱笆.结果篱笆形成了一张网分割了布朗的牧场.布朗想将牧场恢复原样,出于这个考虑,他首先得知道牧场上哪一块区域的周长最小.
布朗将他的每段篱笆从1 到N 进行了标号（N=线段的总数）.他知道每段篱笆的有如下属性:
该段篱笆的长度
该段篱笆的一端所连接的另一段篱笆的标号
该段篱笆的另一端所连接的另一段篱笆的标号
幸运的是,没有篱笆连接它自身.
对于一组有关篱笆如何分割牧场的数据,写一个程序来计算出所有分割出的区域中最小的周长.
例如,标号1~10 的篱笆由下图的形式组成（下面的数字是篱笆的标号）:
上图中周长最小的区域是由2,7,8 号篱笆形成的.
Input
第1 行: N (1 <= N <= 100)
第2 行到第3*N+1 行:
每三行为一组,共N 组信息:每组信息的第1 行有4 个整数:
s, 这段篱笆的标号(1 <= s <= N); Ls, the这段篱笆的长度 (1 <= Ls <= 255); N1s (1 <= N1s <= 8) 与本段篱笆的一端所相邻的篱笆的数量; and N2s 与本段篱笆的另一端所相邻的篱笆的数量. (1 <= N2s <= 8).
每组信息的的第2 行有 N1s 个整数, 分别描述与本段篱笆的一端所相邻的篱笆的标号.
每组信息的的第3 行有N2s 个整数, 分别描述与本段篱笆的另一端所相邻的篱笆的标号.
Output
输出的内容为单独的一行,用一个整数来表示最小的周长.
Sample Input
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 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
Sample Output
12
分析:
本题要求最小环,特殊的是给图的方式是给边。这里我们可以把边通过哈希转化成点,如1,2,7边相交的点,设其哈希值为21,权值为001002007(通过字符串记录),编号顺延
哈希函数如下
int hash1(int n)
{
int x=0;
for(int i=1;i<n;i++)
x+=node[i];
x*=node[n];
return ((x+1231)%101+101)%101;
}
int search(int h,int n)//查找该点是否在哈希链中,若在则返回他的标号
{
int cnt=0;
for(int i=1;i<=n;i++)
{
v_search[++cnt]=node[i]/100;
v_search[++cnt]=node[i]/10%10;
v_search[++cnt]=node[i]%10;
}
int delta=0;
for(int i=head[h];i;i=nxt[i])
{
int flag=0;
if(num[i]!=cnt)
continue;
else
{
for(int j=1;j<=cnt;j++)
{
if(v_search[j]!=v[j][i])
{
flag=1;
break;
}
}
}
if(flag==0)
delta=i;
}
return delta;
}
void push(int h,int n,int point)//point为点的编号
{
int cnt=0;
tot++;
for(int i=1;i<=n;i++)
{
v[++cnt][tot]=node[i]/100;
v[++cnt][tot]=(node[i]%100)/10;
v[++cnt][tot]=node[i]%10;
}
p[tot]=point;
nxt[tot]=head[h];
head[h]=tot;
num[tot]=cnt;
}
注意:在用边表示点时要有一个固定的顺序,如升序等 如边7 3 2就存为002003007
建图后跑floyd求最小环
代码如下
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define inf 10000001
int head[110];
char v[30][110];
char v_search[30];
int num[110];
int nxt[110];
int node[10];
int h[110];
int tot=0;
int f[110][110];
int p[110];
int d;
int mp[110][110];
int min(int x,int y)
{
return x<y?x:y;
}
int hash1(int n)
{
int x=0;
for(int i=1;i<n;i++)
x+=node[i];
x*=node[n];
return ((x+1231)%101+101)%101;
}
int search(int h,int n)
{
int cnt=0;
for(int i=1;i<=n;i++)
{
v_search[++cnt]=node[i]/100;
v_search[++cnt]=node[i]/10%10;
v_search[++cnt]=node[i]%10;
}
int delta=0;
for(int i=head[h];i;i=nxt[i])
{
int flag=0;
if(num[i]!=cnt)
continue;
else
{
for(int j=1;j<=cnt;j++)
{
if(v_search[j]!=v[j][i])
{
flag=1;
break;
}
}
}
if(flag==0)
delta=i;
}
return delta;
}
void push(int h,int n,int point)
{
int cnt=0;
tot++;
for(int i=1;i<=n;i++)
{
v[++cnt][tot]=node[i]/100;
v[++cnt][tot]=(node[i]%100)/10;
v[++cnt][tot]=node[i]%10;
}
p[tot]=point;
nxt[tot]=head[h];
head[h]=tot;
num[tot]=cnt;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
if(i!=j)f[i][j]=inf;
}
int point=0;
for(int i=1;i<=n;i++)
{
int s,l,n1,n2;
scanf("%d%d%d%d",&s,&l,&n1,&n2);
n1++,n2++;
int p1,p2;
node[1]=s;
for(int j=2;j<=n1;j++)
scanf("%d",&node[j]);
std::sort(node+1,node+n1+1);
int h1=hash1(n1);
d=search(h1,n1);
if(d!=0)
p1=p[d];
else
p1=++point,push(h1,n1,point);
node[1]=s;
for(int j=2;j<=n2;j++)
scanf("%d",&node[j]);
std::sort(node+1,node+n2+1);
int h2=hash1(n2);
d=search(h2,n2);
if(d!=0)
p2=p[d];
else
p2=++point,push(h2,n2,point);
f[p1][p2]=l;
f[p2][p1]=l;
}
n=tot;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
mp[i][j]=f[i][j];
}
int ans=inf;
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(j==i||k==i||k==j)
continue;
ans=min(f[i][j]+mp[i][k]+mp[k][j],ans);
f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
}
}
}
printf("%d",ans);
}