Editorial for Cặp ghép không trọng số
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
var n,m,x,y,re,nq,i:longint; c,f:array[1..111,1..111] of longint; a,b,d,q:array[1..111] of longint; function find(var u:longint):boolean; var i:longint; begin fillchar(d,sizeof(d),0); nq:=0; for i:=1 to m do if a[i]=0 then begin inc(nq); q[nq]:=i; end; i:=1; while i<=nq do begin x:=q[i]; inc(i); for y:=1 to n do if (d[y]=0) and (c[x][y]=1) then begin d[y]:=x; if b[y]=0 then begin u:=y; exit(true); end; inc(nq); q[nq]:=b[y]; end; end; find:=false; end; procedure incflow(y:longint); var x,t:longint; begin while y>0 do begin x:=d[y]; t:=y; y:=a[x]; b[t]:=x; a[x]:=t; end; end; begin read(m,n); while not eof do begin read(x); if x<=0 then break; read(y); c[x][y]:=1; end; while find(i) do incflow(i); for i:=1 to m do if a[i]>0 then inc(re); writeln(re); for i:=1 to m do if a[i]>0 then writeln(i,' ',a[i]); end.
Code mẫu của happyboy99x
#include<bits/stdc++.h> using namespace std; #define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i) const int N = 100; int nx, ny; vector<int> g[N]; void enter() { cin >> nx >> ny; for(int u, v; cin >> u >> v; ) g[u-1].push_back(v-1); } void maxmatch() { vector<int> matchX (nx, -1); vector<int> matchY (ny, -1); int mxmatch = 0; while(true) { vector<int> trace (ny, -1); queue<int> q; for(int i = 0; i < nx; ++i) if(matchX[i] == -1) q.push(i); int f = -1; for(bool stop = false; !stop && !q.empty(); ) { int u = q.front(); q.pop(); TR(g[u], v) if(trace[*v] == -1) { trace[*v] = u; if(matchY[*v] == -1) { stop = true; f = *v; break; } else q.push(matchY[*v]); } } if(f == -1) break; do { int x = trace[f], next = matchX[x]; matchX[x] = f; matchY[f] = x; f = next; } while(f != -1); ++mxmatch; } cout << mxmatch << '\n'; for(int i = 0; i < nx; ++i) if(matchX[i] != -1) cout << i+1 << ' ' << matchX[i]+1 << '\n'; } int main() { ios::sync_with_stdio(false); enter(); maxmatch(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; struct BipartiteGraph { vector<vector<int> > E; vector<vector<pair<int, int> > > a; vector<int> match; vector<int> edgeMatch; vector<bool> was; int m, n; BipartiteGraph(int m, int n) { this->m = m; this->n = n; E.clear(); a.clear(); a.resize(m); match.assign(n, -1); edgeMatch.assign(n, -1); was.assign(n, false); } void addEdge(int u, int v, vector<int> expression) { int index = E.size(); a[u].push_back(make_pair(v, index)); E.push_back(expression); } bool dfs(int u) { for (int i = 0; i < a[u].size(); ++i) { int v = a[u][i].first; if (was[v]) continue; was[v] = true; if (match[v] == -1 || dfs(match[v])) { match[v] = u; edgeMatch[v] = a[u][i].second; return true; } } return false; } int fastMatch() { vector<int> buffer; for (int i = 0; i < m; ++i) buffer.push_back(i); bool stop = false; int ans = 0; do { stop = true; for (int i = 0; i < n; ++i) was[i] = false; for (int i = (int)buffer.size() - 1; i >= 0; --i) { int u = buffer[i]; if (dfs(u)) { ++ans; stop = false; buffer[i] = buffer.back(); buffer.pop_back(); } } } while (!stop); return ans; } }; int main() { ios::sync_with_stdio(false); int n, m; cin >> m >> n; BipartiteGraph G(m, n); int u, v; while (cin >> u >> v) G.addEdge(--u, --v, vector<int>()); cout << G.fastMatch() << endl; for (int i = 0; i < n; ++i) if (G.match[i] != -1) cout << G.match[i] + 1 << ' ' << i + 1 << '\n'; return 0; }
Code mẫu của RR
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <complex> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> #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 EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) using namespace std; // Index from 0 // Assume 2 sides have same number of vertices struct Matching { int n; vector< vector<int> > ke; vector< bool > seen; vector< int > matchL, matchR; Matching(int n) : n(n), ke(n), seen(n, false), matchL(n, -1), matchR(n, -1) { } void addEdge(int u, int v) { ke[u].push_back(v); } bool bpm(int u) { for(__typeof(ke[u].begin()) v = ke[u].begin(); v != ke[u].end(); ++v) { if (seen[*v]) continue; seen[*v] = true; if (matchR[*v] < 0 || bpm(matchR[*v])) { matchL[u] = *v; matchR[*v] = u; return true; } } return false; } int match() { int res = 0; for(int i = 0; i < n; ++i) { for(int i = 0; i < n; ++i) seen[i] = false; if (bpm(i)) ++res; } return res; } }; int main() { ios :: sync_with_stdio(false); cin.tie(NULL); int m, n; while (cin >> m >> n) { Matching match(max(m, n)); int u, v; while (cin >> u >> v) { --u; --v; match.addEdge(u, v); } cout << match.match() << endl; for(int i = 0; i < m; ++i) if (match.matchL[i] >= 0) cout << i+1 << ' ' << match.matchL[i] + 1 << "\n"; } }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.00001 #define oo 111111111 #define mod 1000000007 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } // Dinic #define maxn 50011 #define maxe 150111 struct HopcroftKarp{ int nx, ny, E, adj[maxe], next[maxe], last[maxn], matx[maxn], maty[maxn], que[maxn], level[maxn], run[maxn]; void init(int _nx, int _ny){ nx = _nx; ny = _ny; E = 0; FOR(i, 1, nx) matx[i] = -1, last[i] = -1; FOR(i, 1, ny) maty[i] = -1; } void add(int x, int y){ adj[E] = y; next[E] = last[x]; last[x] = E++; } bool bfs(){ bool found = false; int size = 0; FOR(x, 1, nx){ if(matx[x] != -1) level[x] = -1; else{ level[x] = 0; que[size++] = x; } } rep(i, size){ for(int x = que[i], e = last[x]; e != -1; e = next[e]){ int y = adj[e]; if(maty[y] == -1) found = true; else if(level[maty[y]] == -1){ level[maty[y]] = level[x] + 1; que[size++] = maty[y]; } } } return found; } int dfs(int x){ for(int &e = run[x]; e != -1; e = next[e]){ int y = adj[e]; if(maty[y] == -1 || ( level[maty[y]] == level[x] + 1 && dfs(maty[y]))){ maty[y] = x; matx[x] = y; return 1; } } return 0; } int maxMatching(){ int total = 0; while(bfs()){ FOR(x, 1, nx) run[x] = last[x]; FOR(x, 1, nx) if(matx[x] == -1) total += dfs(x); } return total; } } hopkarp; int main(){ // OPEN(); int n, m, x, y; scanf("%d %d",&n, &m); hopkarp.init(n, m); while(scanf("%d %d", &x, &y) > 0){ hopkarp.add(x, y); } printf("%d\n",hopkarp.maxMatching()); FOR(x, 1, n){ y = hopkarp.matx[x]; if(y != -1) printf("%d %d\n",x,y); } }
Code mẫu của ll931110
program MATCH1; const input = ''; output = ''; maxn = 1000; var a: array[1..maxn,1..maxn] of boolean; mx,my: array[1..maxn] of integer; trace,queue: array[1..maxn] of integer; front,rear: integer; m,n: integer; procedure init; var f: text; i,u,v: integer; begin fillchar(a, sizeof(a), false); assign(f, input); reset(f); readln(f, m, n); while not eof(f) do begin readln(f, u, v); a[u,v] := true; end; close(f); end; procedure push(x: integer); begin inc(rear); queue[rear] := x; end; function FindPath: integer; var i,j: integer; begin fillchar(trace, sizeof(trace), 0); front := 1; rear := 0; for i := 1 to m do if mx[i] = 0 then push(i); while front <= rear do begin i := queue[front]; inc(front); for j := 1 to n do if (trace[j] = 0) and a[i,j] and (mx[i] <> j) then begin trace[j] := i; if my[j] = 0 then exit(j); push(my[j]); end; end; FindPath := 0; end; procedure Enlarge(x: integer); var y,z: integer; begin repeat y := trace[x]; z := mx[y]; mx[y] := x; my[x] := y; x := z; until x = 0; end; procedure solve; var fin: integer; begin repeat fin := FindPath; if fin <> 0 then Enlarge(fin); until fin = 0; end; procedure printresult; var f: text; i,c: integer; begin c := 0; for i := 1 to m do if mx[i] <> 0 then inc(c); assign(f, output); rewrite(f); writeln(f, c); for i := 1 to m do if mx[i] <> 0 then writeln(f, i, ' ', mx[i]); close(f); end; begin init; solve; printresult; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 111 using namespace std; vector<int> gx[MAX]; int matx[MAX]; int maty[MAX]; int tx[MAX]; int ty[MAX]; int m,n; queue<int> q; void loadgraph(void) { int i,u,v; scanf("%d",&m); scanf("%d",&n); while (scanf("%d%d",&u,&v)==2) { gx[u].push_back(v); // gy[v].push_back(u); } } int findway(const int &s) { memset(tx,0,sizeof tx); memset(ty,0,sizeof ty); while (!q.empty()) q.pop(); q.push(s); int i,p,v; while (!q.empty()) { p=q.front();q.pop(); for (i=0;i<gx[p].size();i=i+1) { v=gx[p][i]; if (ty[v]==0 && matx[p]!=v) { ty[v]=p; if (maty[v]==0) return (v); else { tx[maty[v]]=v; q.push(maty[v]); } } } } return (0); } void enlarge(const int &f) { int u,v; u=ty[f]; while (u!=0) { v=tx[u]; matx[u]=0; maty[v]=0; u=ty[v]; } v=f; u=ty[f]; while (u!=0) { matx[u]=v; maty[v]=u; v=tx[u]; u=ty[v]; } } void maxmatching(void) { memset(matx,0,sizeof matx); memset(maty,0,sizeof maty); int i,t; bool cont; for (i=1;i<=m;i=i+1) { t=findway(i); if (t>0) enlarge(t); } } void print(void) { int i,c=0; for (i=1;i<=m;i=i+1) c=c+(matx[i]!=0); printf("%d\n",c); for (i=1;i<=m;i=i+1) if (matx[i]>0) printf("%d %d\n",i,matx[i]); } int main(void) { //freopen("tmp.txt","r",stdin); loadgraph(); maxmatching(); print(); return 0; }
Comments