篱笆回路Fence Loops

89 阅读 0 评论 59 点赞

我是靠谱客的博主痴情唇彩，最近开发中收集的这篇文章主要介绍篱笆回路Fence Loops，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目

https://www.luogu.org/problemnew/show/P2738

思路

这一道题有3个难点：

（1）每一条边都有编号，感觉有些麻烦：

认真看题可以发现“边的标号s(1<=s<=N)”，也就是说只是把边

的顺序打乱而已，我们就不用管这么多，直接放上去边的编号，然后搜索的时候1-n

（2）这一道题的主要难点————找最小的环的大小：

这个dfs或者bfs都可以，不过bfs每一个队列都要用结构体带一个数组，但是dfs是一次搜到底，所以采用dfs来做

这里还要注意一个细节，查找只用找一边，因为环是两面想通的，所以找一边即可

首先在主函数里面for（i=1;i<=n;i++），优化一下每次搜索完

开始的那一条边就把这一条边设置为不能走，因为以后搜索

到这一条又会把以前搜过的再搜一次，浪费了很多时间

（3）边的方向：

因为这是无向边，所以得注意一下方向.

输入的时候把左边的变设置为1，右边的边设置为2

搜索的时候假如在边的左边必须到右边去，右边就必须到左边去，每次走都要加上距离

从一条边的左边走到另一条边，你还是在你现在所在的边的左边

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int MAXN=177;
ll n;
ll a[MAXN][MAXN],d[MAXN],ans=0,minn=0x3f3f3f3f3f3f3f3f;
bool v[MAXN],bk[MAXN];
void dfs(ll k,ll t,ll flag)
{
if(ans>=minn) return;
if(k==flag)
{
minn=ans;
return;
}
for(ll i=1;i<=n;i++)
{
if(v[i]==1 && bk[i]==1 && a[k][i]==3-t)
{
v[i]=0;ans=ans+d[i];
dfs(i,a[i][k],flag);
v[i]=1;ans=ans-d[i];
}
}
}
int main()
{
ll i,j,t,t1,x,y;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&t);
scanf("%lld%lld%lld",&d[t],&x,&y);
for(j=1;j<=x;j++)
{
scanf("%lld",&t1);
a[t][t1]=1;
}
for(j=1;j<=y;j++)
{
scanf("%lld",&t1);
a[t][t1]=2;
}
}
memset(bk,1,sizeof(bk));
for(i=1;i<=n;i++)
{
memset(v,1,sizeof(v));
ans=0;
for(j=i+1;j<=n;j++)
{
if(a[i][j]==1)
{
v[j]=0;ans=ans+d[j];
dfs(j,a[j][i],i);
v[j]=1;ans=ans-d[j];
}
}
bk[i]=0;
}
printf("%lldn",minn);
return 0;
}