求助,加虚拟点拓扑排序的方法思路是怎么样的

P1983 [NOIP2013 普及组] 车站分级

@[x17875487211](/user/490694) 你的感觉是正确的,我也在这个地方错了inf次。我的解决办法是先出队虚点,再出队实点,这样保证在队内的都是实点: ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; ll vis[3005],in[3005]; vector<ll> to[3005]; int main() { ll n,m; cin >> n >> m; for (ll i=1; i<=m; i++) { ll s; cin >> s; ll st,ed; cin >> st; memset(vis,0,sizeof(vis)); for (ll j=2; j<s; j++) { ll x; cin >> x; vis[x]=1; } cin >> ed; vis[st]=1,vis[ed]=1; for (ll j=st; j<=ed; j++) { if (vis[j]) { in[j]++; to[i+n].push_back(j); } } for (ll j=st; j<=ed; j++) { if (!vis[j]) { in[i+n]++; to[j].push_back(i+n); } } } ll cnt=0; queue<ll> q; for (ll i=1; i<=m; i++) { if (in[i+n]==0) { in[i+n]--; for (ll j:to[i+n]) { in[j]--; } } } for (ll i=1; i<=n; i++) { if (in[i]==0)q.push(i),in[i]--; } while (!q.empty()) { while (!q.empty()) { ll tp=q.front(); // cout << tp << endl; q.pop(); for (ll i:to[tp]) { in[i]--; } } cnt++; for (ll i=1; i<=m; i++) { if (in[i+n]==0) { in[i+n]--; for (ll j:to[i+n]) { in[j]--; } } } for (ll i=1; i<=n; i++) { if (in[i]==0) { q.push(i),in[i]--; } } } cout << cnt; return 0; } ```
by piggy123 @ 2022-03-16 10:07:25


请问有没有具体的例子,什么情况虚点和实点在同一层
by x17875487211 @ 2022-03-16 13:27:10


|