社区讨论

30分求调教

P2296[NOIP 2014 提高组] 寻找道路参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lopds62o
此快照首次捕获于
2023/11/08 14:30
2 年前
此快照最后确认于
2023/11/08 17:04
2 年前
查看原帖
rt,虽然我换跑反图bfs检查每个点与中点连通性过了,但为什么我这样dfs检查连通性就会导致错误呢?

30pts

CPP
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
#define LL long long
using namespace std;
const int N=1e4+5;

int n,m;
vector<int> G[N];
int vis[N];
int S,T;
bool ke[N];

bool dfs(int u){
    if(u==T){
        vis[u]=1;
        return true;
    }
    vis[u]=-1;
    bool flag= false;
    for(auto &v:G[u]){
        if(vis[v]==0&&dfs(v)) flag=true;
        if(vis[v]==1) flag=true;
    }
    if(flag==true){
        vis[u]=1;
        return true;
    }
    return false;
}

int bfs(){
    memset(vis,0,sizeof vis);
    queue<PII> q;
    q.push({S,0});vis[S]=1;
    while(!q.empty()){
        PII u=q.front();q.pop();
        if(u.first==T) return u.second;
        for(auto v:G[u.first]) if(ke[v]==true) {
                if(vis[v]) continue;
                q.push({v,u.second+1});
                vis[v]=1;
            }
    }
    return -1;
}

int main(){
    std::ios::sync_with_stdio(0);
    cin>>n>>m;
    rep(i,1,m){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
    }
    cin>>S>>T;
    //判断每个点与终点联通性
    rep(i,1,n){
        if(vis[i]==0) dfs(i);
    }
    //判断合法点
    rep(u,1,n){
        bool flag=true;
        for(auto &v:G[u]){
            if(vis[v]==-1){
                flag=false;
                break;
            }
        }
        ke[u]=flag;
    }
    cout<<bfs();
}

100pts

CPP
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
#define PII pair<int,int>
#define LL long long
using namespace std;
const int N=1e4+5;

int n,m;
vector<int> G[N],G2[N];
int vis[N];
int S,T;
bool ke[N];

void bfs2(){
    //bool v[N]={0};
    //memset(vis,-1,sizeof vis);
    queue<int> q;q.push(T);
    vis[T]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(auto &v:G2[u]){
            if(vis[v]==1) continue;
            q.push(v);vis[v]=1;
        }
    }
}

int bfs(){
    memset(vis,0,sizeof vis);
    queue<PII> q;
    q.push({S,0});vis[S]=1;
    while(!q.empty()){
        PII u=q.front();q.pop();
        if(u.first==T) return u.second;
        for(auto v:G[u.first]) if(ke[v]==true) {
            if(vis[v]) continue;
            q.push({v,u.second+1});
            vis[v]=1;
        }
    }
    return -1;
}

int main(){
    std::ios::sync_with_stdio(0);
    cin>>n>>m;
    rep(i,1,m){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G2[y].push_back(x);
    }
    cin>>S>>T;
    //判断每个点与终点联通性
    bfs2();
    //判断合法点
    rep(u,1,n){
        bool flag=true;
        for(auto &v:G[u]){
            if(vis[v]==0){
                flag=false;
                break;
            }
        }
        ke[u]=flag;
    }
    cout<<bfs();
}

回复

0 条回复,欢迎继续交流。

正在加载回复...