社区讨论
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 条回复,欢迎继续交流。
正在加载回复...