Editorial for Thành phố trọng 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
const fi=''; maxn=20010; maxm=200010; var m,n,dem,s,sm:longint; a:array[1..maxm*2] of longint; sl,cur,pos,num,low,cha,d,mien:array[1..maxn] of longint; b:array[1..maxm,0..1] of longint; free:array[1..maxn] of boolean; re:real; procedure rf; var i:longint; begin read(n,m); for i:=1 to m do begin read(b[i,0],b[i,1]); inc(sl[b[i,0]]); inc(sl[b[i,1]]); end; 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 begin a[cur[b[i,0]]]:=b[i,1]; inc(cur[b[i,0]]); a[cur[b[i,1]]]:=b[i,0]; inc(cur[b[i,1]]); end; end; function min(u,v:longint):longint; begin if u<v then min:=u else min:=v; end; procedure visit(x,y:longint;var s:longint); var i,t,nm,sum,sq,u:longint; begin inc(dem); num[x]:=dem; low[x]:=n+1; s:=0; nm:=0; sum:=0; sq:=0;t:=0; u:=0; for i:=pos[x] to pos[x+1]-1 do if a[i]<>y then begin if cha[a[i]]<>0 then low[x]:=min(low[x],num[a[i]]) else begin cha[a[i]]:=x; visit(a[i],x,t); low[x]:=min(low[x],low[a[i]]); s:=s+t; if low[a[i]]>=num[x] then begin sum:=sum+t; sq:=sq+t*t; end else u:=u+t; end; end; s:=s+1; t:=mien[d[x]]-s+u; sum:=sum+t; sq:=sq+t*t; re:=re+(sum*sum-sq) div 2; end; procedure dfs(x,y:longint); var i:longint; begin d[x]:=sm; inc(mien[sm]); free[x]:=true; for i:=pos[x] to pos[x+1]-1 do if not free[a[i]] and (a[i]<>y) then dfs(a[i],x); end; procedure pr; var i,j:longint; begin dem:=0; sm:=0; for i:=1 to n do if not free[i] then begin inc(sm); dfs(i,0); end; for i:=1 to n do if num[i]=0 then begin cha[i]:=-1; visit(i,0,s); end; writeln(re/n:0:2); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<vector> #include<queue> using namespace std; #define TR(v,i) for(typeof((v).begin()) i=(v).begin();i!=(v).end();++i) const int N = 20000 + 5, INF = 1000000000; vector<vector<int> > g; int n, m, d[N], low[N], r[N], timed; bool vst[N]; void enter() { scanf("%d%d",&n,&m); g.resize(n); for(int i = 0; i < m; ++i) { int u, v; scanf("%d%d",&u,&v); g[--u].push_back(--v); g[v].push_back(u); } } int sqr(const int &x) { return x * x; } long long res; void dfs(int u, int p, int nnode) { d[u] = ++timed; r[u] = 1; low[u] = INF; int rem = nnode - 1, add = sqr(nnode - 1), nchild = 0; TR(g[u], it) { int v = *it; if(d[v]) { if(v != p) low[u] = min(low[u], d[v]); } else { dfs(v, u, nnode); low[u] = min(low[u], low[v]); r[u] += r[v]; ++nchild; if((p == -1 && nchild > 1 || p != -1) && low[v] >= d[u]) rem -= r[v], add -= sqr(r[v]); } } if(p == -1 && nchild > 1) rem -= r[g[u][0]], add -= sqr(r[g[u][0]]); res += add - sqr(rem); } int bfs(int u) { int res = 0; queue<int> q; q.push(u); vst[u] = 1; while(!q.empty()) { int u = q.front(); q.pop(); ++res; TR(g[u], v) if(vst[*v] == 0) vst[*v] = 1, q.push(*v); } return res; } void solve() { for(int u = 0; u < n; ++u) if(vst[u] == 0) dfs(u, -1, bfs(u)); printf("%.2lf\n", (double) res / (2*n)); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, m, cc; int Time; int was[N]; int par[N]; int root[N]; int num[N], low[N]; int Size[N]; long long ans[N]; vector<int> a[N]; void dfs(int u) { was[u] = cc; num[u] = ++Time; low[u] = N; Size[u] = 1; for (int v : a[u]) if (v != par[u]) { if (was[v]) { low[u] = min(low[u], num[v]); } else { par[v] = u; dfs(v); low[u] = min(low[u], low[v]); Size[u] += Size[v]; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; a[u].push_back(v); a[v].push_back(u); } for (int u = 1; u <= n; ++u) { sort(a[u].begin(), a[u].end()); a[u].resize(unique(a[u].begin(), a[u].end()) - a[u].begin()); } for (int i = 1; i <= n; ++i) if (!was[i]) { ++cc; root[cc] = i; dfs(i); } for (int u = 1; u <= n; ++u) { long long cur = 0, sizePar = Size[root[was[u]]] - 1; for (int v : a[u]) if (par[v] == u && low[v] >= num[u]) { ans[u] += cur * Size[v]; cur += Size[v]; sizePar -= Size[v]; } if (sizePar) { ans[u] += cur * sizePar; } } long long sum = 0; for (int u = 1; u <= n; ++u) sum += ans[u]; cout << setprecision(2) << fixed << (long double)sum / n << endl; return 0; }
Code mẫu của RR
uses math; const MAXN=20111; type list=^node; node=record u:longint; next:list; end; procedure add(u:longint; var a:list); var p:list; begin new(p); p^.u:=u; p^.next:=a; a:=p; end; var n,m,u,v,cnt,sl:longint; ke:array[1..MAXN] of list; res:int64; w,low,num,reg,father,count:array[1..MAXN] of longint; procedure dfs1(u:longint); var v:longint; p:list; begin reg[u]:=sl; w[u]:=1; inc(cnt); low[u]:=cnt; num[u]:=cnt; p:=ke[u]; while p<>nil do begin v:=p^.u; p:=p^.next; if v=father[u] then continue; if num[v]=0 then begin father[v]:=u; dfs1(v); low[u]:=min(low[u],low[v]); inc(w[u],w[v]); end else low[u]:=min(low[u],num[v]); end; end; procedure dfs2(u:longint); var v,tmp:longint; p:list; begin p:=ke[u]; tmp:=count[reg[u]]-1; while p<>nil do begin v:=p^.u; p:=p^.next; if father[v]<>u then continue; dfs2(v); //Cac dinh thuoc cay con goc v khong di duoc len tren dinh u if low[v]>=num[u] then begin tmp:=tmp-w[v]; res:=res+int64(w[v])*tmp; end; end; end; begin read(n,m); for m:=1 to m do begin read(u,v); add(u,ke[v]); add(v,ke[u]); end; sl:=0; for u:=1 to n do if num[u]=0 then begin cnt:=0; inc(sl); dfs1(u); end; for u:=1 to n do inc(count[reg[u]]); for u:=1 to n do if father[u]=0 then dfs2(u); writeln(res/n:0:2); end.
Code mẫu của skyvn97
#include<cstdio> #include<iostream> #include<queue> #include<vector> #define MAX 20020 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) using namespace std; typedef long long ll; vector<int> g[MAX]; int low[MAX]; int num[MAX]; int ncp[MAX]; int nc[MAX]; int sz[MAX]; int n,m,cnt; ll sp; void minimize(int &x,const int &y) { if (x>y) x=y; } void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); REP(i,m) { int u,v; scanf("%d",&u); scanf("%d",&v); g[u].push_back(v); g[v].push_back(u); } } ll sumproduct(const vector<int> &v) { int sumall=0; ll sumsqr=0LL; FORE(it,v) { sumall+=*it; sumsqr+=1LL*(*it)*(*it); } return (1LL*sumall*sumall-sumsqr)/2; } int BFS(int s,int id) { queue<int> q; while (!q.empty()) q.pop(); ncp[s]=id; q.push(s); int ret=1; while (!q.empty()) { int u=q.front();q.pop(); FORE(it,g[u]) if (ncp[*it]==0) { ncp[*it]=id; q.push(*it); ret++; } } return (ret); } void visit(int u) { vector<int> nchild=vector<int>(); int nrest=0; cnt++; low[u]=n+7; num[u]=cnt; FORE(it,g[u]) { int v=*it; if (num[v]==0) { visit(v); nc[u]+=nc[v]; if (low[v]>=num[u]) nchild.push_back(nc[v]); else nrest+=nc[v]; minimize(low[u],low[v]); } else minimize(low[u],num[v]); } nc[u]++; nrest+=sz[ncp[u]]-nc[u]; nchild.push_back(nrest); sp+=sumproduct(nchild); } void process(void) { int tmp=0; FOR(i,1,n) if (ncp[i]==0) { tmp++; sz[tmp]=BFS(i,tmp); } FOR(i,1,n) if (num[i]==0) visit(i); printf("%.2lf",1.0*sp/n); } int main(void) { loadgraph(); process(); return 0; }
Comments