社区讨论
蒟蒻问一个小问题,我为什么赋值不过去(太奇怪了QAQ)
P2296[NOIP 2014 提高组] 寻找道路参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @loctuk6u
- 此快照首次捕获于
- 2023/10/30 19:39 2 年前
- 此快照最后确认于
- 2023/11/05 06:16 2 年前
84-86行,ans[z]+1怎么就赋给不了ans[p]呢,百思不得其解555
CPP#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
#define maxn 200005
int ltp, LTP, lk[maxn], LK[maxn], n, m, w, u, v, s, t, cnt[maxn], a[maxn];
bool f[maxn], vis[maxn], b, bl[maxn], ans[maxn];
struct edg {
int y, nxt;
} e[maxn];
edg E[maxn];
void ist(int x, int y) {
e[++ltp] = {y, lk[x]};
lk[x] = ltp;
}
void IST(int X, int Y) {
E[++LTP] = {Y, LK[X]};
LK[X] = LTP;
}
void DFS(int X) {
if(vis[X]) return;
vis[X] = 1;
for(int i = LK[X]; i; i = E[i].nxt)
DFS(E[i].y);
}
void bfs_(int x) {
queue<int> q;
q.push(x);
f[x] = 1;
while(!q.empty()) {
int z = q.front();
q.pop();
for(int i = lk[z]; i; i = e[i].nxt) {
if(!f[e[i].y]) {
int p = e[i].y;
for(int j = lk[p]; j; j = e[j].nxt) {
if(!vis[e[j].y]) {
b = 1;
f[e[i].y] = 1;
bl[e[i].y] = 0;
break;
}
}
if(!b) {
q.push(e[i].y);
f[e[i].y] = 1;
}
}
}
}
}
void bfs__(int x) {
queue<int> q;
q.push(x);
bl[x] = 1;
while(!q.empty()) {
int z = q.front();
if(z == t) return;
q.pop();
for(int i = lk[z]; i; i = e[i].nxt) {
int p = e[i].y;
if(bl[p]) {
q.push(p);
printf("p = %d, ans[%d] = %d, z = %d, ans[%d] = %d\n", p, p, ans[p], z, z, ans[z]);
ans[p] = ans[z]+1;
printf("p = %d, ans[%d] = %d, z = %d, ans[%d] = %d\n", p, p, ans[p], z, z, ans[z]);
}
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
scanf("%d %d", &u, &v);
IST(v, u);
ist(u, v);
}
cin >> s >> t;
DFS(t);
for(int i = 1; i < maxn; ++i)
bl[i] = vis[i];
for(int i = 1; i <= n; ++i) {
for(int j = lk[i]; j; j = e[j].nxt) {
int p = e[j].y;
if(!vis[p]) {
bl[i] = 0;
break;
}
}
}
for(int i = 1; i <= n; ++i)
printf("bl[%d] = %d\n", i, bl[i]);
memset(f, 0, sizeof(f));
bfs__(s);
if(ans[t] == 0) ans[t] = -1;
cout << ans[t];
return 0;
}
回复
共 7 条回复,欢迎继续交流。
正在加载回复...