题解 CF24A 【Ring road】

· · 题解

不是很懂楼上大佬的链式前向星，所以这里写一发常规的大法师

题意：

给我们一个图 ：一共n个点，然后给出n条路，
每个路正向的边权是0，反向的边权是v
（正向的路已经建好，v是建反方向路的代价）
让我们找出一个边权最小且经过所有点的环
因为需要两两之间可达且费用最低

思路：

正常的DFS肯定是超时的，所以我们需要必要的剪枝，用记忆化搜索来找环，如果这个点被访问过了，我们不需要在搜索这个点

（因为环上面的点最多只出现一次）

CODE：

#include<bits/stdc++.h>
#define maxn 233
using namespace std;
int edge[maxn][maxn];
int vis[maxn];
int minn,n,e,v,s;
void dfs(int st,int en,int sum,int step)
{
    if(st==en&&step==n)//如果起点终点一样，且一共经过了n个点那么更新最小值
    {
        minn=min(minn,sum);
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==1)//如果访问过就跳过
            continue;
        if(edge[en][i]!=0&&edge[i][en]==0)//如果i这个点没访问过且这条边存在且是边权不为零的边，那将en调整成i继续往下走
        {
            vis[i]=1;//记忆化搜索的步骤
            dfs(st,i,sum+edge[en][i],step+1);
            vis[i]=0;//记忆化搜索的步骤
        }
        else if(edge[en][i]==0&&edge[i][en]!=0)//如果i这个点没访问过且这条边存在且是边权为零的边，那将en调整成i继续往下走
        {
            vis[i]=1;
            dfs(st,i,sum,step+1);
            vis[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s>>e>>v;
        edge[s][e]=0;
        edge[e][s]=v;
    }
    minn=100000000;
    dfs(1,1,0,0);
    cout<<minn<<endl;//输出经过所有点的最小环
    return 0;
}