题解 P1793 【跑步】

游戏的人 · 2020-04-03 10:27:02 · 题解

难道就没人想到暴力吗

刚开始以为是割点题，发现其实从起点到终点的必经之路就算没了，图也可能还是联通的，所以便可以想到暴力。

思路

可以用邻接链表把图存起来，再枚举2到N-1的点为必经之路，再沿着路径搜索，判断没有这个点能不能到达终点，能的话就说明这个点不是必经之路，直接退出。如果不能到终点就说明必须要走这个点，就存到答案里。

每次经过这个点都要打上标记。本题不需要回溯，只需要判断这个点有没有走过，因为只需要判断搜到这个点有没有路径，不用判断是怎么走的，所以只需要判断有没有重复搜点就行了。每次枚举时记得标记数组清零。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n,m,f[8001],k,num,sum=0,ans[8001],s[8001];
bool flag;
struct edge 
{
    int f,t;
}a[4000001];//定义边长 
void add(int x1,int y1)
{
    a[++num].f=s[x1];
    a[num].t=y1;
    s[x1]=num;
}//邻接链表存图 
void dfs(int x,int k)
{
    if(x==n){flag=1;return;}//判断如果能到终点就标记不是必经之路 
    if(f[x]==1||x==k||flag==1)return;//如果这个点搜过，或者到了切断的必经之路，或者已到达终点就返回 
    f[x]=1;//走过标记 
    for(int i=s[x];i;i=a[i].f)dfs(a[i].t,k);//邻接链表搜索 
} 
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int xi,yi;
        cin>>xi>>yi;
        if(xi==yi)continue;//判断自环 
        add(xi,yi);add(yi,xi);//无向图正反存 
    }
    for(int i=2;i<=n-1;i++)
    {
        for(int j=1;j<=n;j++)f[j]=0;//开始标记数组清零 
        flag=0;//终点标记初始化 
        dfs(1,i);//起点1,枚举的必经之路是i 
        if(flag==0)sum++,ans[sum]=i;//答案+1，存入数组，两者并列 
    }
    cout<<sum<<endl; 
    for(int i=1;i<=sum;i++)cout<<ans[i]<<" ";//输出 
}

完结撒花

留个赞吧