Editorial for VOI 09 Bài 2 - Nút st - xung yếu
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> #include <queue> using namespace std; int n, S, T, onPath[10010], prev[10010], flag[10010], mark[10010]; vector <int> a[10010], path; int bfs() { queue <int> q; prev[S] = -1; q.push(S); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < int(a[x].size()); i++) { int y = a[x][i]; if (!prev[y]) q.push(y), prev[y] = x; } } if (!prev[T]) return 0; int x = T; path.push_back(T); while (x != S) x = prev[x], path.push_back(x); path.push_back(0); reverse(path.begin(), path.end()); for (int i = 1; i < int(path.size()); i++) onPath[path[i]] = i; return 1; } int findFurthestOnPath(int x, int z) { if (onPath[x] && onPath[x] != z) return onPath[x]; flag[x] = z; int res = 0; for (int i = 0; i < int(a[x].size()); i++) { int y = a[x][i]; if (flag[y] != z) res = max(res, findFurthestOnPath(y, z)); } return res; } int main() { int m, x, y; cin >> n >> m >> S >> T; while (m--) scanf("%d%d", &x, &y), a[x].push_back(y); if (!bfs()) { puts("0"); return 0; } for (int i = 1; i < int(path.size()); i++) { int j = findFurthestOnPath(path[i], i); if (i + 1 < j) mark[i + 1]++, mark[j]--; } int ans = 0; for (int i = 2; i + 1 < int(path.size()); i++) { mark[i] += mark[i - 1]; ans += !mark[i]; } cout << ans << endl; }
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 10005; const int M = 100005; using namespace std; VI super[N], adj[N], a[N]; int num[N], low[N], f[N], lab[N], T[N]; bool was[N], deleted[M]; int n, m, s, t, timer, scc; void readInput() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m >> s >> t; int u, v; FOR(i, 0, m) { cin >> u >> v; a[u].PB(v); } } void bfsFindPath() { queue<int> Q; Q.push(s); T[s] = -1; while (!Q.empty()) { int u = Q.front(); Q.pop(); TR(it, a[u]) if (T[*it] == 0) { T[*it] = u; if (*it == t) return; Q.push(*it); } } } VI path; bool inPath[N]; int id[N]; void buildPath() { for(int v = t; v != s; v = T[v]) path.PB(v); path.PB(s); reverse(ALL(path)); FOR(i, 0, SZ(path)) inPath[path[i]] = 1, id[path[i]] = i; } stack<int> S; void dfsTarjan(int u) { num[u] = low[u] = ++timer; S.push(u); TR(it, a[u]) { int v = *it; if (was[v] || inPath[v]) continue; if (num[v]) low[u] = min(low[u], num[v]); else { dfsTarjan(v); low[u] = min(low[u], low[v]); } } if (low[u] >= num[u]) { int v; do { v = S.top(); S.pop(); was[v] = 1; lab[v] = scc; super[scc].PB(v); } while (v != u); scc++; } } void buildDAG() { REP(i, 1, n) if (!was[i]) dfsTarjan(i); FOR(i, 0, scc) TR(u, super[i]) TR(it, a[*u]) if (!inPath[*it]) adj[i].PB(lab[*it]); } void dpOnDAG() { FOR(i, 0, scc) { TR(u, super[i]) TR(it, a[*u]) if (inPath[*it]) f[i] = max(f[i], id[*it]); TR(u, adj[i]) f[i] = max(f[i], f[*u]); } } int in[N], out[N]; void solve() { FOR(i, 0, SZ(path)) { int right = f[lab[path[i]]] - 1; if (right > i) { in[i + 1]++; out[right]++; } } int cnt = 0, ans = SZ(path) - 2; FOR(i, 0, SZ(path)) { cnt += in[i]; if (cnt) ans--; cnt -= out[i]; } cout << ans; } int main() { readInput(); bfsFindPath(); buildPath(); buildDAG(); dpOnDAG(); solve(); return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #define MAXN 10111 #define FOR(i,a,b) for(long i=a; i<=b; i++) #define FORD(i,a,b) for(long i=a; i>=b; i--) #define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++) #define V vector<long> #define PB push_back using namespace std; long n,m,s,t,k,queue[MAXN],trace[MAXN],next[MAXN],x[MAXN],lab[MAXN],f[MAXN]; V ke[MAXN]; void inp() { scanf("%ld %ld %ld %ld",&n,&m,&s,&t); FOR(i,1,m) { long u,v; scanf("%ld %ld",&u,&v); ke[u].PB(v); } } void bfs() { long first=1,last=1; queue[1]=s; while (first<=last) { long u=queue[first++]; FORV(v,ke[u]) if (!trace[*v]) { trace[*v]=u; if (*v==t) return ; queue[++last]=*v; } } } void dfs(long u) { FORV(v,ke[u]) if (lab[*v]) f[u]=max(f[u],lab[*v]); else { if (f[*v]) f[u]=max(f[u],f[*v]); else { dfs(*v); f[u]=max(f[u],f[*v]); } } } void solve() { trace[s]=s; bfs(); if (!trace[t]) { printf("0\n"); return ; } long v=t; while (v!=s) { long u=trace[v]; next[u]=v; v=u; } long u=s; long k=0; while (u!=t) { long v=next[u]; x[++k]=u; lab[u]=k; u=v; } x[++k]=t; lab[t]=k; FOR(i,1,k) dfs(x[i]); long res=0,ln=f[x[1]]; FOR(i,2,k-1) { if (lab[x[i]]>=ln) res++; ln=max(ln,f[x[i]]); } printf("%ld",res); } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); inp(); solve(); return 0; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> #include <cstring> #define maxn 100005 using namespace std; bool mark[maxn],next[maxn]; int d[maxn],trace[maxn]; vector<int> adj[maxn]; int n,m,s,t; void BFS(int start) { memset(d,-1,sizeof(d)); d[start] = 0; deque<int> q; q.push_back(start); while (!q.empty()) { int u = q.front(); q.pop_front(); for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (d[v] < 0 || d[v] > d[u] + mark[v]) { d[v] = d[u] + mark[v]; trace[v] = u; if (mark[v]) q.push_back(v); else q.push_front(v); } } } if (d[t] < 0) d[t] = 0; } void track(int u) { next[u] = true; if (u == s) return; track(trace[u]); } void printAnswer() { vector<int> answer; for (int i = 1; i <= n; i++) if (i != s && i != t && mark[i]) answer.push_back(i); printf("%d\n", answer.size()); // for (int i = 0; i < answer.size(); i++) printf("%d ", answer[i]); } int main() { // freopen("assassination.in","r",stdin); scanf("%d %d %d %d", &n, &m, &s, &t); for (int i = 0; i < m; i++) { int x,y; scanf("%d %d", &x, &y); adj[x].push_back(y); } memset(mark,true,sizeof(mark)); while (1) { int temp = d[t]; BFS(s); if (d[t] == temp) break; memset(next,false,sizeof(next)); track(t); for (int i = 1; i <= n; i++) mark[i] &= next[i]; } printAnswer(); }
Code mẫu của skyvn97
#ifndef graph_h #define graph_h int calculate(int N, int M, int S, int T, int U[], int V[]); #endif #include<bits/stdc++.h> #define MAX 100100 #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1) #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) #define ALL(v) (v).begin(),(v).end() using namespace std; class SegmentTree { private: int n; vector<bool> lazy; void update(int i,int l,int r,int u,int v) { if (l>v || r<u || l>r || v<u) return; if (u<=l && r<=v) { lazy[i]=true; return; } int m=(l+r)>>1; update(2*i,l,m,u,v); update(2*i+1,m+1,r,u,v); } public: SegmentTree() { n=0; } SegmentTree(int n) { this->n=n; lazy.assign(4*n+7,false); } void update(int l,int r) { update(1,1,n,l,r); } bool get(int x) const { int i=1; int l=1; int r=n; while (true) { if (lazy[i]) return (true); if (l==r) return (false); int m=(l+r)>>1; if (x>m) { i=2*i+1; l=m+1; } else { i=2*i; r=m; } } } }; vector<int> adj[MAX]; vector<int> path; int trace[MAX]; int pathPos[MAX]; int n,m,s,t,nComp,cnt; int low[MAX],num[MAX],compID[MAX]; vector<int> comp[MAX]; stack<int> st; int storedMaxNode[MAX]; bool bfs(void) { memset(trace,-1,sizeof trace); queue<int> q; trace[s]=0; q.push(s); while (!q.empty()) { int u=q.front();q.pop(); FORE(it,adj[u]) if (trace[*it]<0) { int v=*it; trace[v]=u; q.push(v); } } return (trace[t]>0); } void findPath(void) { memset(pathPos,-1,sizeof pathPos); for (int u=t;u!=s;u=trace[u]) path.push_back(u); path.push_back(s); reverse(ALL(path)); REP(i,path.size()) pathPos[path[i]]=i; } void dfs(int u) { low[u]=num[u]=++cnt; st.push(u); FORE(it,adj[u]) if (pathPos[*it]<0 && compID[*it]==0) { int v=*it; if (num[v]==0) { dfs(v); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],num[v]); } if (low[u]==num[u]) { nComp++; int v; do { v=st.top();st.pop(); compID[v]=nComp; comp[nComp].push_back(v); } while (v!=u); } } void tarjan(void) { FOR(i,1,n) if (pathPos[i]<0 && num[i]==0) dfs(i); memset(storedMaxNode,-0x3f,sizeof storedMaxNode); } int maxNode(int u) { if (storedMaxNode[u]>=-1) return (storedMaxNode[u]); int &res=storedMaxNode[u]; res=-1; FORE(it,comp[u]) FORE(jt,adj[*it]) { if (pathPos[*jt]>=0) res=max(res,pathPos[*jt]); else if (compID[*jt]!=u) res=max(res,maxNode(compID[*jt])); } return (res); } int maxPathNode(int u) { int res=-1; FORE(it,adj[u]) if (pathPos[*it]<0) res=max(res,maxNode(compID[*it])); return (res); } int process(void) { SegmentTree myit((int)path.size()-2); REP(i,path.size()) { int j=maxPathNode(path[i]); if (i+1<=j-1) myit.update(i+1,j-1); //printf("From %d to %d\n",i,j); } int res=0; FOR(i,1,(int)path.size()-2) if (!myit.get(i)) res++; return (res); } int calculate(int N, int M, int S, int T, int U[], int V[]) { n=N;m=M;s=S+1;t=T+1; if (s==t) return (0); REP(i,m) { int u=U[i]+1; int v=V[i]+1; adj[u].push_back(v); if (u==s && v==t) return (0); } if (!bfs()) return (0); findPath(); //REP(i,path.size()) printf("%d ",path[i]); printf("\n"); tarjan(); /*FOR(i,1,nComp) { printf("Comp #%d:",i); FORE(it,comp[i]) printf(" %d",*it); printf("\n"); }*/ return (process()); } #include <stdio.h> int main() { //freopen("graph.in","r",stdin); //freopen("graph.out","w",stdout); int N,M,S,T; scanf("%d%d%d%d",&N,&M,&S,&T); S--;T--; int *U = new int[M]; int *V = new int[M]; for (int i = 0; i < M; i++) { scanf("%d%d",&U[i],&V[i]); U[i]--;V[i]--; } printf("%d\n",calculate(N,M,S,T,U,V)); return 0; }
Code mẫu của khuc_tuan
#include <iostream> #include <vector> using namespace std; int n, m, s, t, comp; vector<int> ke[10010 * 2], ds; int vs[10010 * 2], cant[10010 * 2]; bool dfs(int i) { if(i==t+n) return true; if(vs[i]) return false; vs[i] = true; for(int k=0;k<ke[i].size();++k) { int j = ke[i][k]; if(dfs(j)) { if(i+n==j) cant[i] = j; ke[j].push_back(i); ds.push_back(i); return true; } } return false; } void dfs2(int i) { vs[i] = comp; for(int k=0;k<ke[i].size();++k) if(!vs[ke[i][k]] && ke[i][k]!=cant[i]) dfs2(ke[i][k]); } int main() { scanf("%d%d%d%d", &n, &m, &s, &t); for(int i=0;i<m;++i) { int u, v; scanf("%d%d", &u, &v); ke[u+n].push_back(v); } for(int i=1;i<=n;++i) ke[i].push_back(i+n); dfs(s); memset( vs, 0, sizeof(vs)); for(int k=ds.size()-1;k>=0;--k) if(!vs[ds[k]]) { ++comp; dfs2(ds[k]); } int dem = 0; for(int i=1;i<=n;++i) if(i!=s && i!=t && vs[i] != vs[i+n]) ++dem; printf("%d\n", dem); return 0; }
Comments
This comment is hidden due to too much negative feedback. Show it anyway.