Editorial for VOI 11 Bài 6 - Nâng cấp mạng
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> #define fr(a,b,c) for(a=b;a<=c;a++) #define frr(a,b,c) for(a=b;a>=c;a--) #define maxn 100100 #define oo 1000000 using namespace std; struct rec{ int x,y,z; }; int n,m,lab[maxn],ok[maxn],sl,p[maxn],e[maxn][18],f[maxn][18],next[maxn]; int a[maxn*2],c[maxn*2],h[maxn],d[maxn],hh; rec b[maxn]; long long re; void sort(int l,int r) { int i=l,j=r,x=b[(i+j)/2].z,y; do { while (b[i].z>x) i++; while (b[j].z<x) j--; if (i<=j) { swap(b[i],b[j]); i++; j--; } } while (i<=j); if (i<r) sort(i,r); if (l<j) sort(l,j); } int get(int x) { if (lab[x]!=x) lab[x]=get(lab[x]); return lab[x]; } void visit(int x,int y) { e[x][0]=y; hh=max(hh,h[x]); int i; fr(i,p[x]+1,p[x+1]) if (a[i]!=y) { h[a[i]]=h[x]+1; d[a[i]]=c[i]; visit(a[i],x); } } int calc(int x,int y) { int i,lg,res=oo; if (h[x]<h[y]) swap(x,y); for (lg=0;1<<lg<=h[x];lg++); lg--; frr(i,lg,0) if (h[x]-(1<<i)>=h[y]) { res=min(res,f[x][i]); x=e[x][i]; } if (x==y) return res; frr(i,lg,0) if (e[x][i] && e[x][i]!=e[y][i]) { res=min(res,min(f[x][i],f[y][i])); x=e[x][i]; y=e[y][i]; } res=min(res,min(d[x],d[y])); return res; } int main() { int i,x,y,j,v=0,w=100001; cin >> n >> m; fr(i,1,m) scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z); sort(1,m); fr(i,1,n) lab[i]=i; fr(i,1,m) { if (sl<n-1) { x=get(b[i].x); y=get(b[i].y); if (x!=y) { ok[i]=1; lab[y]=x; p[b[i].x]++; p[b[i].y]++; next[v]=i; v=i; ++sl; } else { next[w]=i; w=i; } } else { next[w]=i; w=i; } } fr(i,2,n+1) p[i]+=p[i-1]; i=next[0]; while (i) { a[p[b[i].x]]=b[i].y; c[p[b[i].x]--]=b[i].z; a[p[b[i].y]]=b[i].x; c[p[b[i].y]--]=b[i].z; i=next[i]; } visit(1,0); d[1]=oo; fr(i,1,n) f[i][0]=d[i]; for (j=1;1<<j<=hh;j++) fr(i,1,n) if (e[i][j-1]) { e[i][j]=e[e[i][j-1]][j-1]; f[i][j]=min(f[i][j-1],f[e[i][j-1]][j-1]); } else f[i][j]=oo; i=next[100001]; while (i) { re+=calc(b[i].x,b[i].y)-b[i].z; i=next[i]; } cout << re << endl; return 0; }
Code mẫu của happyboy99x
#include<iostream> #include<cstring> #include<vector> #include<algorithm> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 1e5, LOG = 17, INF = 1e9; vector<vector<pair<int, int> > > mst; vector<pair<int, pair<int, int> > > edge; int n, m, mindist[N][LOG], par[N][LOG], sett[N], h[N], logn; void initSet() { for(int i = 0; i < n; ++i) sett[i] = i; } int getSet(int u) { return u == sett[u] ? u : sett[u] = getSet(sett[u]); } void enter() { cin >> n >> m; mst.resize(n); for(int i = 0; i < m; ++i) { int u, v, c; cin >> u >> v >> c; edge.push_back(make_pair(-c, make_pair(--u, --v))); } } void findMST() { initSet(); sort(edge.begin(), edge.end()); TR(edge, it) { int u = it->second.first, v = it->second.second, w = -it->first; if(getSet(u) != getSet(v)) { mst[u].push_back(make_pair(v, w)); mst[v].push_back(make_pair(u, w)); sett[sett[u]] = sett[v]; } } } void dfs(int u) { TR(mst[u], it) { int v = it->first, w = it->second; if(v != par[u][0]) { h[v] = h[u] + 1; par[v][0] = u; mindist[v][0] = w; dfs(v); } } } void initLCA() { logn = 0; while(1 << logn <= n) ++logn; --logn; for(int j = 1; 1 << j < n; ++j) for(int i = 0; i < n; ++i) if(par[i][j-1] != -1) { par[i][j] = par[par[i][j-1]][j-1]; mindist[i][j] = min(mindist[i][j-1], mindist[par[i][j-1]][j-1]); } } int getmin(int u, int v) { if(h[u] < h[v]) swap(u, v); int res = INF; for(int j = logn; j >= 0; --j) if(h[u] - (1 << j) >= h[v]) { res = min(res, mindist[u][j]); u = par[u][j]; } if(u == v) return res; for(int j = logn; j >= 0; --j) if(par[u][j] != par[v][j]) { res = min(res, min(mindist[u][j], mindist[v][j])); u = par[u][j]; v = par[v][j]; } return min(res, min(mindist[u][0], mindist[v][0])); } void solve() { long long res = 0; TR(edge, it) { int u = it->second.first, v = it->second.second, w = it->first; res += getmin(u, v) + w; } cout << res << "\n"; } int main() { ios::sync_with_stdio(false); enter(); findMST(); memset(par, -1, sizeof par); h[0] = 0; dfs(0); initLCA(); solve(); return 0; }
Code mẫu của ladpro98
{$MODE OBJFPC} program upgranet; uses math; type e=record x,y,w:longint; end; e2=record v,w:longint; end; const fi=''; maxn=100005; maxm=200005; maxL=trunc(ln(maxn)/ln(2))+1; var n,m,log,me:longint; a:array[1..maxm] of e; adj:array[1..maxm] of e2; link:array[1..maxm] of longint; lab,head,par,w,d:array[0..maxn] of longint; b,mi:array[0..maxn,0..maxL] of longint; choose,check:array[1..maxn] of boolean; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,n,m); for i:=1 to m do readln(inp,a[i].x,a[i].y,a[i].w); close(inp); end; procedure sort(l,r:longint); var p,i,j:longint; t:e; begin if l>=r then exit; i:=l;j:=r; p:=a[random(r-l+1)+l].w; repeat while a[i].w>p do inc(i); while a[j].w<p do dec(j); if i<=j then begin if i<j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; function root(u:longint):longint; begin if lab[u]<=0 then exit(u); result:=root(lab[u]); lab[u]:=result; end; procedure union(u,v:longint); begin if lab[u]<lab[v] then lab[v]:=u else begin if lab[u]=lab[v] then dec(lab[v]); lab[u]:=v; end; end; procedure kruskal; var i,x,y,c:longint; begin sort(1,m); for i:=1 to m do begin x:=root(a[i].x); y:=root(a[i].y); if x<>y then begin union(x,y); inc(c); choose[i]:=true; inc(me); adj[me].v:=y; adj[me].w:=a[i].w; link[me]:=head[x]; head[x]:=me; inc(me); adj[me].v:=x; adj[me].w:=a[i].w; link[me]:=head[y]; head[y]:=me; end; if c=n-1 then break; end; end; procedure dfs(i,p,c:longint); var j:longint; begin par[i]:=p; d[i]:=d[p]+1; w[i]:=c; check[i]:=true; j:=head[i]; while j>0 do begin if not check[adj[j].v] then dfs(adj[j].v,i,adj[j].w); j:=link[j]; end; end; procedure initLCA; var i,j:longint; begin log:=trunc(ln(n)/ln(2))+1; for i:=0 to n do begin b[i,0]:=par[i]; mi[i,0]:=w[i]; end; for j:=1 to log do for i:=0 to n do begin b[i,j]:=b[b[i,j-1],j-1]; mi[i,j]:=min(mi[i,j-1],mi[b[i,j-1],j-1]); end; end; function getbit(i,j:longint):longint; begin exit(i shr (j-1) and 1); end; function lca(u,v:longint):longint; var i,res,t:longint; begin res:=high(longint); if d[u]>=d[v] then begin if d[u]>d[v] then begin t:=d[u]-d[v]; for i:=log downto 1 do if getbit(t,i)=1 then begin res:=min(res,mi[u,i-1]); u:=b[u,i-1]; end; end; if u=v then exit(res); for i:=log downto 0 do begin if b[u,i]<>b[v,i] then begin res:=min(res,mi[u,i]); res:=min(res,mi[v,i]); u:=b[u,i]; v:=b[v,i]; end; if b[u,0]=b[v,0] then res:=min(res,min(mi[u,0],mi[v,0])); end; exit(res); end else exit(lca(v,u)); end; procedure output; var i:longint; res:int64; begin res:=0; for i:=1 to m do if not choose[i] then inc(res,lca(a[i].x,a[i].y)-a[i].w); write(res); end; begin input; kruskal; dfs(1,0,0); initLCA; output; end.
Code mẫu của RR
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair using namespace std; const double PI = acos(-1.0); //Buffer reading int INP,AM; #define BUFSIZE (1<<10) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ fread(BUF,1,BUFSIZE,stdin); \ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading int n, m, lab[100111]; pair< int, pair<int,int> > e[100111]; vector<pair<int,int> > ke[100111]; int getRoot(int u) { if (lab[u] < 0) return u; return lab[u] = getRoot(lab[u]); } void merge(int u, int v) { int x = lab[u] + lab[v]; if (lab[u] < lab[v]) { lab[u] = x; lab[v] = u; } else { lab[v] = x; lab[u] = v; } } int father[22][100111], nn[22][100111], d[100111]; void dfs(int u, int fu) { REP(i,ke[u].size()) { int v = ke[u][i].F; if (v == fu) continue; father[0][v] = u; nn[0][v] = ke[u][i].S; d[v] = d[u] + 1; dfs(v, u); } } void init() { FOR(i,1,20) FOR(u,1,n) { int v = father[i-1][u]; if (v != -1) { father[i][u] = father[i-1][v]; nn[i][u] = min(nn[i-1][u], nn[i-1][v]); } } } int get(int u, int v) { if (u == v) return 0; if (d[u] < d[v]) swap(u,v); int res = 1000111000; FORD(i,20,0) if (father[i][u] >= 0 && d[father[i][u]] >= d[v]) { res = min(res, nn[i][u]); u = father[i][u]; } if (u == v) return res; FORD(i,20,0) if (father[i][u] != father[i][v]) { res = min(res, nn[i][u]); res = min(res, nn[i][v]); u = father[i][u]; v = father[i][v]; } res = min(res, nn[0][u]); res = min(res, nn[0][v]); return res; } bool mst[100111]; int main() { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); GN(n); GN(m); REP(i,m) { GN(e[i].S.F); GN(e[i].S.S); GN(e[i].F); } sort(e, e+m); memset(lab, -1, sizeof lab); FORD(i,m-1,0) { int u = e[i].S.F, v = e[i].S.S, c = e[i].F; u = getRoot(u); v = getRoot(v); if (u == v) continue; merge(u, v); u = e[i].S.F, v = e[i].S.S; ke[u].PB(MP(v,c)); ke[v].PB(MP(u,c)); mst[i] = true; } // cout << endl; memset(father, -1, sizeof father); dfs(1, -1); init(); ll res = 0; FORD(i,m-1,0) if (!mst[i]) { int u = e[i].S.F, v = e[i].S.S; // cout << u << ' ' << v << ' ' << get(u,v) << endl; res += get(u, v) - e[i].F; } cout << res << endl; return 0; }
Code mẫu của skyvn97
#include<algorithm> #include<cstdio> #include<iostream> #include<queue> #include<vector> #define MAX 100100 #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define FORD(i,b,a) for (int i=(b);i>=(a);i=i-1) #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++) #define fi first #define se second using namespace std; typedef pair<int,int> ii; typedef pair<int,ii> pii; const int INF=(int)1e9+7; pii e[MAX]; bool mst[MAX]; vector<ii> g[MAX]; ii p[MAX][19]; int h[MAX]; class DSU { private: vector<int> lab; int find(int x) { if (lab[x]<0) return (x); lab[x]=find(lab[x]); return (lab[x]); } public: DSU() { lab=vector<int>(); } DSU(int _n) { lab=vector<int>(_n+7,-1); } bool join(int a,int b) { int x=find(a); int y=find(b); if (x==y) return (false); lab[y]=x; return (true); } }; DSU dsu; int m,n; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); FOR(i,1,m) { int u,v,w; scanf("%d",&u); scanf("%d",&v); scanf("%d",&w); e[i]=pii(w,ii(u,v)); } dsu=DSU(n); h[0]=-1; } void loadtree(void) { sort(e+1,e+m+1,greater<pii>()); FOR(i,1,m) { if (dsu.join(e[i].se.fi,e[i].se.se)) { int u=e[i].se.fi; int v=e[i].se.se; int w=e[i].fi; g[u].push_back(ii(v,w)); g[v].push_back(ii(u,w)); } else (mst[i]=true); } } void visit(int u) { FORE(it,g[u]) if (it->fi!=p[u][0].fi) { int v=it->fi; p[v][0]=ii(u,it->se); h[v]=h[u]+1; visit(v); } } void setupLCA(void) { visit(1); FOR(j,1,18) FOR(i,1,n) p[i][j]=ii(p[p[i][j-1].fi][j-1].fi,min(p[i][j-1].se,p[p[i][j-1].fi][j-1].se)); } int mindis(int u,int v) { if (h[u]<h[v]) return (mindis(v,u)); int ret=INF; FORD(j,18,0) if (h[p[u][j].fi]>=h[v]) { ret=min(ret,p[u][j].se); u=p[u][j].fi; } if (u==v) return (ret); FORD(j,18,0) if (p[u][j].fi!=p[v][j].fi) { ret=min(ret,p[u][j].se); ret=min(ret,p[v][j].se); u=p[u][j].fi; v=p[v][j].fi; } ret=min(ret,p[u][0].se); ret=min(ret,p[v][0].se); return (ret); } void process(void) { long long res=0; FOR(i,1,m) if (mst[i]) { int u=e[i].se.fi; int v=e[i].se.se; int w=e[i].fi; res+=mindis(u,v)-w; } cout << res; } int main(void) { loadgraph(); loadtree(); setupLCA(); process(); return 0; }
Comments