Editorial for Mạng truyền tin
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 ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int N = 111; const int oo = trunc(1e9); const int V = N * N; using namespace std; vector<iii> e; vector<int> a[N]; int c[N][N], f[N][N], T[N], Q[N]; int m, n, s, t, res, ans; void Enter() { //freopen("NKNET.in", "r", stdin); scanf("%d %d\n", &n, &m); int u, v, c; for(int i=1; i<=m; i++) { scanf("%d %d %d\n", &u, &v, &c); e.push_back(iii(c, ii(u, v))); a[u].push_back(v); a[v].push_back(u); } scanf("%d %d", &s, &t); } void Init(int lim) { //initialize network int i, j, u, v; for(i=1; i<=n; i++) { a[i].clear(); for(j=1; j<=n; j++) { f[i][j] = 0; c[i][j] = V; } } for(i=0; i<m; i++) if (e[i].X > lim) { u = e[i].Y.X; v = e[i].Y.Y; a[u].push_back(v); a[v].push_back(u); } } void Init2(int lim) { int i, j, u, v; for(i=1; i<=n; i++) { a[i].clear(); for(j=1; j<=n; j++) { f[i][j] = 0; c[i][j] = V; } } for(i=0; i<m; i++) { u = e[i].Y.X; v = e[i].Y.Y; a[u].push_back(v); a[v].push_back(u); if (e[i].X <= lim) c[u][v] = c[v][u] = 1; } } bool FindPath() { int l=1, r=1, u, v, i; Q[1] = s; for(i=1; i<=n; i++) T[i] = 0; while (l <= r) { u = Q[l++]; for(i=0; i<a[u].size(); i++) { v = a[u][i]; if (T[v] == 0 && c[u][v] > f[u][v]) { Q[++r] = v; T[v] = u; if (v == t) return true; } } } return false; } void IncFlow() { int u, v, delta = oo; v = t; while (v != s) { u = T[v]; delta = min(delta, c[u][v] - f[u][v]); v = u; } v = t; while (v != s) { u = T[v]; f[u][v] += delta; f[v][u] -= delta; v = u; } } int maxFlow() { while (FindPath()) IncFlow(); int flow = 0; for(int i=0; i<a[s].size(); i++) flow += f[s][a[s][i]]; return flow; } int main() { Enter(); //BinarySearch the answer int l = 0, r = V, mid; while (l <= r) { mid = (l + r) / 2; Init(mid); if (FindPath()) { l = mid + 1; } else { res = mid; r = mid - 1; } } Init2(res); ans = maxFlow(); printf("%d\n", ans); for(int i=1; i<=n; i++) if (i == s || T[i] > 0) { for(int j=0; j<a[i].size(); j++) { int v = a[i][j]; if (T[v] == 0) printf("%d %d\n", i, v); } } return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung uses math; const finp=''; fout=''; maxn=101; oo=1000000; var s,t,m,n:longint; queue,trace:array[0..maxn] of longint; c,c2,f:array[0..maxn,0..maxn] of longint; procedure readinp; var i,u,v:longint; begin assign(input,finp); reset(input); read(n,m); for i:=1 to m do begin read(u,v,c[u,v]); c[v,u]:=c[u,v]; end; read(s,t); close(input); end; function findpath:boolean; var first,last,i,j:longint; begin fillchar(trace,sizeof(trace),0); first:=0; last:=1; queue[1]:=s; trace[s]:=n+1; while first<last do begin inc(first); i:=queue[first]; for j:=1 to n do if (trace[j]=0) and (f[i,j]<c[i,j]) then begin trace[j]:=i; inc(last); queue[last]:=j; if j=t then exit(true); end; end; exit(false); end; procedure incflow; var i,j,delta:longint; begin delta:=oo; j:=t; repeat i:=trace[j]; if delta>c[i,j]-f[i,j] then delta:=c[i,j]-f[i,j]; j:=i; until j=s; j:=t; repeat i:=trace[j]; inc(f[i,j],delta); dec(f[j,i],delta); j:=i; until j=s; end; function check(val:longint):boolean; var i,j,cost:longint; ok:boolean; begin c2:=c; for i:=1 to n do for j:=1 to n do if (c[i,j]<>0) and (c[i,j]<=val) then c[i,j]:=1 else if c[i,j]>val then c[i,j]:=oo; fillchar(f,sizeof(f),0); ok:=false; repeat if not findpath then break; incflow; until ok; cost:=0; for i:=1 to n do if f[s,i]>0 then inc(cost,f[s,i]); c:=c2; if cost>=oo then exit(false) else exit(true); end; procedure printresult(val:longint); var i,j,cost:longint; ok:boolean; fo:text; begin for i:=1 to n do for j:=1 to n do if (c[i,j]<>0) and (c[i,j]<=val) then c[i,j]:=1 else if (c[i,j]<>0) then c[i,j]:=oo; fillchar(f,sizeof(f),0); ok:=false; repeat if not findpath then break; incflow; until ok; cost:=0; for i:=1 to n do if f[s,i]>0 then inc(cost,f[s,i]); assign(fo,fout); rewrite(fo); writeln(fo,cost); for i:=1 to n do for j:=1 to n do if (c[i,j]<>0) and (trace[i]<>0) and (trace[j]=0) then writeln(fo,i,' ',j); close(fo); end; procedure solve; var left,right,mid:longint; begin left:=0; right:=101; repeat mid:=(left+right) div 2; if check(mid) then right:=mid else left:=mid; until left=right-1; if check(left) then printresult(left) else printresult(right); end; begin readinp; solve; end.
Code mẫu của ll931110
program NKNET; const input = ''; output = ''; maxn = 100; maxm = 10000; maxv = 1000000; var a,c,f: array[1..maxn,1..maxn] of longint; n,m: longint; queue,trace: array[1..maxn] of longint; front,rear: longint; s,t: longint; time: longint; cc: longint; lx,ly,t1,t2: array[1..maxm] of longint; l1,l2: longint; procedure init; var fi: text; i,j,u,v: longint; begin assign(fi, input); reset(fi); read(fi, n, m); fillchar(a, sizeof(a), 0); for i := 1 to m do begin readln(fi, u, v, a[u,v]); a[v,u] := a[u,v]; end; readln(fi, s, t); close(fi); end; function ok(x: longint): boolean; var u,v: longint; begin fillchar(trace, sizeof(trace), 0); front := 1; rear := 1; queue[1] := s; trace[s] := -1; repeat u := queue[front]; inc(front); for v := 1 to n do if (trace[v] = 0) and (a[u,v] > x) then begin trace[v] := u; if v = t then exit(false); inc(rear); queue[rear] := v; end; until front > rear; ok := true; end; procedure settime; var inf,sup,med: longint; begin inf := 0; sup := maxn; repeat med := (inf + sup) div 2; if ok(med) then begin time := med; sup := med - 1; end else inf := med + 1; until inf > sup; end; function FindPath: boolean; var u,v: longint; begin fillchar(trace, sizeof(trace), 0); front := 1; rear := 1; queue[1] := s; trace[s] := -1; repeat u := queue[front]; inc(front); for v := 1 to n do if (trace[v] = 0) and (c[u,v] > f[u,v]) then begin trace[v] := u; if v = t then exit(true); inc(rear); queue[rear] := v; end; until front > rear; FindPath := false; end; procedure IncFlow; var d,u,v: longint; begin d := high(longint); v := t; repeat u := trace[v]; if c[u,v] - f[u,v] < d then d := c[u,v] - f[u,v]; v := u; until v = s; v := t; repeat u := trace[v]; f[u,v] := f[u,v] + d; f[v,u] := f[v,u] - d; v := u; until v = s; end; procedure FordFulkerson; var i,j,u,v: longint; begin fillchar(c, sizeof(c), 0); for i := 1 to n do for j := 1 to n do if a[i,j] > 0 then begin if a[i,j] <= time then c[i,j] := 1 else c[i,j] := maxv; end; fillchar(f, sizeof(f), 0); repeat if not FindPath then break; IncFlow; until false; cc := 0; l1 := 0; l2 := 0; for i := 1 to n do if trace[i] = 0 then begin inc(l2); t2[l2] := i; end else begin inc(l1); t1[l1] := i; end; for i := 1 to l1 do for j := 1 to l2 do begin u := t1[i]; v := t2[j]; if (c[u,v] = 1) and (f[u,v] = 1) then begin inc(cc); lx[cc] := u; ly[cc] := v; end; end; end; procedure printresult; var fo: text; i: longint; begin assign(fo, output); rewrite(fo); writeln(fo, cc); for i := 1 to cc do writeln(fo, lx[i], ' ', ly[i]); close(fo); end; begin init; settime; FordFulkerson; printresult; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 111 #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++) #define fi first #define se second using namespace std; const int INF=(int)1e9+7; typedef pair<int,int> ii; class DinicFlow { private: vector<int> dist,head,q,work; vector<int> capa,flow,next,point; int n,m; public: DinicFlow() { n=0;m=0; } DinicFlow(int n,int _m) { this->n=n; this->m=0; dist=vector<int>(n+7); head=vector<int>(n+7,-1); q=vector<int>(n+7); work=vector<int>(n+7); int m=2*_m; capa=vector<int>(m+7); flow=vector<int>(m+7,0); next=vector<int>(m+7); point=vector<int>(m+7); } void addedge(int u,int v,int c1,int c2) { point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++; point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++; } bool bfs(int s,int t) { FORE(it,dist) *it=-1; int sz=1; q[0]=s;dist[s]=0; REP(x,sz) { int u=q[x]; for (int i=head[u];i>=0;i=next[i]) if (dist[point[i]]<0 && flow[i]<capa[i]) { dist[point[i]]=dist[u]+1; q[sz]=point[i]; sz++; } } return (dist[t]>=0); } int dfs(int s,int t,int f) { if (s==t) return (f); for (int &i=work[s];i>=0;i=next[i]) if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) { int d=dfs(point[i],t,min(f,capa[i]-flow[i])); if (d>0) { flow[i]+=d; flow[i^1]-=d; return (d); } } return (0); } int maxflow(int s,int t,vector<int> &v) { int ret=0; while (bfs(s,t)) { FOR(i,1,n) work[i]=head[i]; while (true) { int d=dfs(s,t,INF); if (d<=0) break; ret+=d; } } v.clear(); FOR(i,1,n) if (dist[i]>=0) v.push_back(i); //printf("MaxFlow %d\n",ret); return (ret); } }; vector<ii> g[MAX]; int d[MAX]; bool src[MAX]; int n,m,s,t; void loadgraph(void) { scanf("%d",&n); scanf("%d",&m); REP(i,m) { int u,v,c; scanf("%d",&u); scanf("%d",&v); scanf("%d",&c); g[u].push_back(ii(v,c)); g[v].push_back(ii(u,c)); } scanf("%d",&s); scanf("%d",&t); } bool bfs(int s,int t,int x) { queue<int> q; while (!q.empty()) q.pop(); memset(d,-1,sizeof d); q.push(s); d[s]=0; while (!q.empty()) { int u=q.front();q.pop(); if (u==t) return (true); FORE(it,g[u]) if (it->se>x) { int v=it->fi; if (d[v]<0) { d[v]=d[u]+1; q.push(v); } } } return (false); } int findtime(void) { int l=0; int r=INF; while (true) { if (l==r) return (r); if (r-l==1) { if (!bfs(s,t,l)) return (l); else return (r); } int m=(l+r)>>1; if (!bfs(s,t,m)) r=m; else l=m+1; } } void process(void) { int ans=findtime(); DinicFlow G=DinicFlow(n,m); FOR(i,1,n) FORE(it,g[i]) { int j=it->fi; int cst; if (it->se<=ans) cst=1; else cst=INF; if (i<j) G.addedge(i,j,cst,cst); } vector<int> v; vector<ii> res; assert(G.maxflow(s,t,v)<INF); FORE(it,v) src[*it]=true; FORE(it,v) FORE(jt,g[*it]) if (!src[jt->fi]) res.push_back(ii(*it,jt->fi)); printf("%d\n",res.size()); FORE(it,res) printf("%d %d\n",it->fi,it->se); } int main(void) { #ifndef ONLINE_JUDGE freopen("tmp.txt","r",stdin); printf("START\n"); #endif loadgraph(); process(); return 0; }
Comments