Editorial for VOI 10 Bài 2 - Ổn định
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
const oo=100000000; var m,n,s,re,num,cr:longint; a:array[0..51000] of longint; b:array[0..51000,0..1] of longint; pos,sl,cur,d,e,q:array[0..10100] of longint; free:array[0..10100] of boolean; procedure sort(l,r:longint); var i,j,x,y,t:longint; begin i:=l; j:=r; x:=b[(i+j) div 2,0]; y:=b[(i+j) div 2,1]; repeat while (b[i,0]<x) or ((b[i,0]=x) and (b[i,1]<y)) do i:=i+1; while (b[j,0]>x) or ((b[j,0]=x) and (b[j,1]>y)) do j:=j-1; if i<=j then begin t:=b[i,0]; b[i,0]:=b[j,0]; b[j,0]:=t; t:=b[i,1]; b[i,1]:=b[j,1]; b[j,1]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure rf; var i:longint; begin read(n,m,s); for i:=1 to m do read(b[i,0],b[i,1]); sort(1,m); for i:=1 to m do if (b[i,0]<>b[i-1,0]) or (b[i,1]<>b[i-1,1]) then inc(sl[b[i,0]]); pos[1]:=1; cur[1]:=1; for i:=2 to n+1 do begin pos[i]:=pos[i-1]+sl[i-1]; cur[i]:=pos[i]; end; for i:=1 to m do if (b[i,0]<>b[i-1,0]) or (b[i,1]<>b[i-1,1]) then begin a[cur[b[i,0]]]:=b[i,1]; inc(cur[b[i,0]]); end; end; procedure init; var i:longint; begin for i:=1 to n do begin d[i]:=oo; free[i]:=true; e[i]:=0; end; end; procedure pr; var i,x,y:longint; begin init; cr:=1; num:=1; q[1]:=s; d[s]:=0; e[s]:=1; repeat x:=q[cr]; free[x]:=false; for i:=pos[x] to pos[x+1]-1 do begin y:=a[i]; if free[y] then begin if d[y]=oo then begin inc(num); q[num]:=y; end; if d[y]=d[x]+1 then e[y]:=2 else begin if d[y]>d[x]+1 then begin d[y]:=d[x]+1; e[y]:=e[x]; end; end; end; end; inc(cr); until cr>num; re:=0; for i:=1 to n do if e[i]>1 then inc(re); writeln(re); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 10000 + 2; typedef pair<int, int> ii; #define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i) int n, m, s, d[N]; unsigned long long c[N]; vector<vector<int> > g; void enter() { scanf("%d%d%d",&n,&m,&s); g.resize(n); --s; for(int i = 0, u, v; i < m; ++i) { scanf("%d%d", &u, &v); g[--u].push_back(--v); } } void editGraph() { TR(g, u) { sort(u->begin(), u->end()); u->resize(distance(u->begin(), unique(u->begin(), u->end()))); } } void solve() { //Dijkstra memset(d, 0x3f, sizeof d); d[s] = 0; c[s] = 1; priority_queue<ii, vector<ii>, greater<ii> > q; q.push(ii(0, s)); while(!q.empty()) { int u = q.top().second, du = q.top().first; q.pop(); if(du > d[u]) continue; TR(g[u], v) { if(d[*v] > du + 1) q.push(ii(d[*v] = du + 1, *v)), c[*v] = c[u]; else if(d[*v] == du + 1) c[*v] += c[u]; } } int res = 0; for(int u = 0; u < n; ++u) if(d[u] < 0x3f3f3f3f && c[u] >= 2) ++res; printf("%d\n", res); } int main() { enter(); editGraph(); solve(); return 0; }
Code mẫu của ladpro98
program stable; uses math; type e=record x,y:longint; end; const maxm=55555; maxn=10005; fi=''; var head,d,way:array[1..maxn] of longint; check,done:array[1..maxn] of boolean; q,adj,link,st:array[1..maxm] of longint; n,m,s:longint; procedure input; var inp:text; i,x,y:longint; begin assign(inp,fi); reset(inp); readln(inp,n,m,s); for i:=1 to m do begin readln(inp,x,y); adj[i]:=y; link[i]:=head[x]; head[x]:=i; end; close(inp); end; procedure bfs; var i,l,r,u,top,v:longint; begin l:=1;r:=1; q[1]:=s; check[s]:=true; way[s]:=1; while l<=r do begin u:=q[l];inc(l); i:=head[u]; top:=0; while i>0 do begin v:=adj[i]; if not done[v] then begin inc(top); st[top]:=v; done[v]:=true; if not check[v] then begin check[v]:=true; inc(r); q[r]:=v; d[v]:=d[u]+1; way[v]:=way[u]; end else begin if d[u]+1=d[v] then inc(way[v],way[u]); if way[v]>1 then way[v]:=2; end; end; i:=link[i]; end; for i:=1 to top do done[st[i]]:=false; end; end; procedure output; var i,res:longint; begin res:=0; for i:=1 to n do if way[i]>1 then inc(res); write(res); end; begin input; bfs; output; end.
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #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 MAXN 10111 #define V vector<long> #define PB push_back using namespace std; long n,m,s,cnt[MAXN],trace[MAXN],l[MAXN],q[2][MAXN],top[2]; V ke[MAXN]; void inp() { scanf("%ld %ld %ld",&n,&m,&s); FOR(i,1,m) { long u,v; scanf("%ld %ld",&u,&v); ke[u].PB(v); } } void solve() { top[0]=1; q[0][1]=s; cnt[s]=1; l[s]=1; long now=0; while (top[now]) { while (top[now]) { long u=q[now][top[now]--]; FORV(v,ke[u]) if (trace[*v]!=u) if (!l[*v]) { trace[*v]=u; cnt[*v]=cnt[u]; l[*v]=l[u]+1; q[1-now][++top[1-now]]=*v; } else if (l[*v]==l[u]+1) { trace[*v]=u; cnt[*v]=min(2L,cnt[*v]+cnt[u]); } } now=1-now; } long res=0; FOR(i,1,n) if (cnt[i]==2) res++; cout<<res<<endl; } 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 <cmath> #include <cstring> #include <iostream> #include <map> #include <set> #include <sstream> #include <stack> #include <queue> #include <vector> using namespace std; vector<int> v[10001]; vector< pair<int,int> > e; queue<int> q; int way[10001],len[10001]; bool fr[10001]; int main() { int n,m,x,y,s; // freopen("stable.in","r",stdin); // freopen("stable.out","w",stdout); scanf("%d%d%d", &n, &m, &s); for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); e.push_back(make_pair(x,y)); }; sort(e.begin(),e.end()); v[e[0].first].push_back(e[0].second); for (int i = 1; i < m; i++) if (e[i] != e[i - 1]) v[e[i].first].push_back(e[i].second); memset(len, 0, sizeof(len)); memset(way, 0, sizeof(way)); memset(fr, true, sizeof(fr)); fr[s] = false; way[s] = 1; q.push(s); while (!q.empty()) { int a = q.front(); q.pop(); for (int i = 0; i < v[a].size(); i++) { int b = v[a][i]; if (fr[b]) { fr[b] = false; len[b] = len[a] + 1; way[b] = way[a]; q.push(b); } else if (len[b] == len[a] + 1) way[b] = min(200,way[b] + way[a]); }; }; // for (int i = 1; i <= n; i++) cout << len[i] << ' ' << way[i] << endl; int ret = 0; for (int i = 1; i <= n; i++) if (way[i] >= 2) ret++; printf("%d\n", ret); };
Code mẫu của skyvn97
#include<stdio.h> #include<queue> #include<vector> #define MAX 11111 using namespace std; typedef pair<int,int> ii; typedef vector<int> vi; const int INF=1e7; bool a[MAX][MAX]; vi g[MAX]; int n,m,s,r; int d[MAX]; int c[MAX]; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); scanf("%d",&s); int i,u,v; for (i=1;i<=n;i=i+1) { d[i]=INF; c[i]=0; } for (i=1;i<=m;i=i+1) { scanf("%d",&u); scanf("%d",&v); if (a[u][v]) continue; g[u].push_back(v); a[u][v]=true; } c[s]=1; d[s]=0; } void dijkstra(void) { priority_queue<ii,vector<ii>,greater<ii> > q; q.push(ii(0,s)); while (!q.empty()) { ii x=q.top(); q.pop(); int i; int w=x.first; int u=x.second; for (i=0;i<g[u].size();i=i+1) { if (d[u]+1==d[g[u][i]]) { c[g[u][i]]+=c[u]; if (c[g[u][i]]>17) c[g[u][i]]=17; } else if (d[u]+1<d[g[u][i]]) { d[g[u][i]]=d[u]+1; c[g[u][i]]=c[u]; if (c[g[u][i]]>17) c[g[u][i]]=17; q.push(ii(d[u]+1,g[u][i])); } } } int cnt=0; int i; for (i=1;i<=n;i=i+1) if (c[i]>1) cnt++; printf("%d",cnt); } int main(void) { loadgraph(); dijkstra(); }
Code mẫu của khuc_tuan
#include <cstdio> #include <set> #include <queue> using namespace std; int n, m, s, res; vector<int> ke[10010]; int d[10010], f[10010]; int main() { set<pair<int,int> > se; scanf("%d%d%d", &n, &m, &s); for(int i=0;i<m;++i) { int u, v; scanf("%d%d", &u, &v); if(!se.count(make_pair(u,v))) { se.insert(make_pair(u,v)); ke[u].push_back(v); } } queue<int> q; q.push(s); d[s] = f[s] = 1; while(!q.empty()) { int u = q.front(); q.pop(); for(int k=0;k<ke[u].size();++k) { int v = ke[u][k]; if(d[v] == 0) { d[v] = d[u] + 1; f[v] = f[u]; q.push(v); } else if(d[v] == d[u] + 1) { f[v] += f[u]; if(f[v] > 2) f[v] = 2; } } } for(int i=1;i<=n;++i) if(f[i] >= 2) ++res; printf("%d\n", res); return 0; }
Comments