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>
#include <cstdio>
#include <vector>
using namespace std;

struct BipartiteGraph
{
    vector <int> leftMatch, rightMatch, seen;
    vector < vector <int> > a;
    int m, n;

    BipartiteGraph() {}
    BipartiteGraph(int _m, int _n)
    {
        m = _m; n = _n;
        a = vector < vector <int> >(m);
        leftMatch = vector <int>(n, -1);
        rightMatch = vector <int>(m, -1);
        seen = vector <int>(m, 0);
    }

    void addEdge(int x, int y)
    {
        a[x].push_back(y);
    }

    int findMatch(int x)
    {
        if (x < 0) return 1;
        if (seen[x]) return 0;
        seen[x] = 1;
        for (int i = 0; i < int(a[x].size()); i++)
        {
            int y = a[x][i];
            if (findMatch(leftMatch[y]))
            {
                leftMatch[y] = x; rightMatch[x] = y;
                return 1;
            }
        }
        return 0;
    }

    int maxMatching()
    {
        int match = 0;
        for (int i = 0; i < m; i++) 
        {
            for (int j = 0; j < m; j++) seen[j] = 0;
            match += findMatch(i);
        }
        return match;
    }

    int vertexCover()
    {
        maxMatching();
        for (int i = 0; i < m; i++) seen[i] = 0;
        for (int i = 0; i < m; i++)
            if (rightMatch[i] < 0 && !seen[i]) findMatch(i);

        vector <int> visited(n, 0);
        for (int i = 0; i < m; i++)
            if (seen[i])
                for (int j = 0; j < int(a[i].size()); j++)
                    visited[a[i][j]] = 1;

        int res = 0;
        for (int i = 0; i < n; i++) res += visited[i] || leftMatch[i] >= 0;
        return res;
    }
};

int n, x[333], y[333], xx[333], yy[333];
vector <int> v, h;

int intersect(int i, int j)
{
    return 1LL * (x[i] - x[j]) * (x[i] - xx[j]) <= 0 && 1LL * (y[j] - y[i]) * (y[j] - yy[i]) <= 0;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i] >> xx[i] >> yy[i];
        if (x[i] == xx[i]) v.push_back(i);
        else h.push_back(i);
    }

    BipartiteGraph G(v.size(), h.size());
    for (int i = 0; i < int(v.size()); i++)
        for (int j = 0; j < int(h.size()); j++)
            if (intersect(v[i], h[j]))
                G.addEdge(i, j);

    cout << G.m + G.n - G.vertexCover() << endl;
}

Code mẫu của happyboy99x

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 250;

struct Segment {
    int x, y1, y2;

    Segment(int x = 0, int y1 = 0, int y2 = 0):
        x (x), y1 (y1), y2 (y2) {}
};

vector<int> g[N];
vector<Segment> ver, hor;
int my[N], m, n;
bool vy[N];

void enter() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int x, y, u, v; cin >> x >> y >> u >> v;
        if(x > u) swap(x, u);
        if(y > v) swap(y, v);
        if(x == u) ver.push_back(Segment(x, y, v));
        else hor.push_back(Segment(y, x, u));
    }
}

void build() {
    m = ver.size(); n = hor.size();
    for(int i = 0; i < m; ++i)
        for(int j = 0; j < n; ++j) {
            if(hor[j].y1 > ver[i].x) continue;
            if(hor[j].y2 < ver[i].x) continue;
            if(ver[i].y1 > hor[j].x) continue;
            if(ver[i].y2 < hor[j].x) continue;
            g[i].push_back(j);
        }
}

bool dfs(int u) {
    TR(g[u], v) if(!vy[*v]) {
        vy[*v] = true;
        if(my[*v] == -1 || dfs(my[*v]))
            return my[*v] = u, true;
    }
    return false;
}

void solve() {
    memset(my, -1, sizeof my);
    int res = m + n;
    for(int i = 0; i < m; ++i) {
        memset(vy, 0, sizeof vy);
        if(dfs(i)) --res;
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    build();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;

typedef pair<int, int> II;

const int N = 255;

vector<pair<II, II> > H, V;
vector<int> a[N];

int n, Size;
int node[N];
int match[N];
bool was[N];
bool found;

bool intersect(pair<II, II> &a, pair<II, II> &b) {
    assert(b.X.Y == b.Y.Y);
    return a.X.Y <= b.X.Y && b.X.Y <= a.Y.Y && b.X.X <= a.X.X && a.X.X <= b.Y.X;
}

void dfs(int u) {
    for (int v: a[u]) if (!was[v]) {
        was[v] = 1;
        if (match[v] == 0)
            found = 1;
        else
            dfs(match[v]);
        if (found) {
            match[v] = u;
            return;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    II X, Y;
    for (int i = 1; i <= n; ++i) {
        cin >> X.X >> X.Y >> Y.X >> Y.Y;
        if (X > Y) swap(X, Y);
        if (X.X == Y.X)
            V.push_back(make_pair(X, Y));
        else
            H.push_back(make_pair(X, Y));
    }
    for (int i = 0; i < V.size(); ++i) for (int j = 0; j < H.size(); ++j)
        if (intersect(V[i], H[j])) a[i + 1].push_back(j + 1);
    Size = V.size();
    for (int i = 1; i <= Size; ++i) node[i] = i;
    bool stop = 0;
    int ans = n;
    while (!stop) {
        stop = 1;
        for (int i = 1; i <= H.size(); ++i) was[i] = 0;
        for (int i = Size; i > 0; --i) {
            found = 0;
            dfs(node[i]);
            if (found) {
                --ans;
                stop = 0;
                node[i] = node[Size--];
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#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 REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

struct Vertical {
    int x, y1, y2;
    Vertical() {}
    Vertical(int x, int y1, int y2) : x(x), y1(y1), y2(y2) {}
} ver[255];

struct Horizontal {
    int y, x1, x2;
    Horizontal() {}
    Horizontal(int y, int x1, int x2) : y(y), x1(x1), x2(x2) {}
} hor[255];

vector<int> ke[255];
int n[2], mx[255], my[255], trace[255];

bool dfs(int u) {
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (trace[v]) continue;
        trace[v] = u;
        if (!my[v] || dfs(my[v])) {
            my[v] = u;
            mx[u] = v;
            return true;
        }
    }
    return false;
}

int main() {
    int t; scanf("%d", &t);
    int x1, y1, x2, y2;
    while (t--) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if (x1 == x2) {
            ver[++n[0]] = Vertical(x1, min(y1, y2), max(y1, y2));
        }
        else {
            hor[++n[1]] = Horizontal(y1, min(x1, x2), max(x1, x2));
        }
    }
    FOR(i,1,n[0]) FOR(j,1,n[1]) {
        if (ver[i].x >= hor[j].x1 && ver[i].x <= hor[j].x2
                && hor[j].y >= ver[i].y1 && hor[j].y <= ver[i].y2)
            ke[i].PB(j);
    }
    FOR(i,1,n[0]) {
        memset(trace, 0, sizeof trace);
        dfs(i);
    }
    int res = 0;
    FOR(i,1,n[0]) if (mx[i]) ++res;
    cout << n[0] + n[1] - res << endl;
    return 0;
}

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.00000001
#define oo 1111111111
#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 MS(a, x) memset(a, x, sizeof(a))
#define sz(a) (int)(a.size())
//#include <conio.h>
//#define g 9.81

double const PI=4*atan(1.0);

const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0;
char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; }
void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); }
int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; }
template<class T> bool gi(T &v) {
    v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc();
    while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true;
}

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

#define eps 1e-6

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

#define maxn 255
#define maxe 100005

struct HopcroftKarp{
    int nx, ny, E, adj[maxe], next[maxe], last[maxn],
    matx[maxn], maty[maxn], que[maxn], run[maxn], level[maxn];

    void init(int _nx, int _ny){
        E = 0; nx = _nx; ny = _ny;
        FOR(x, 1, nx) last[x] = -1, matx[x] = -1;
        FOR(y, 1, ny) maty[y] = -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;

struct Point{
    int x, y;
    Point(){};
    Point(int _x, int _y){
        x = _x; y = _y;
    }
};

struct Line{
    Point P1, P2;
    Line(){};
    Line(Point _P1, Point _P2){
        P1 = _P1; P2 = _P2;
    }
};

vector<Line> V1, V2;
Point A, B;
int n;

int main(){    
    //OPEN();
    scanf("%d", &n);
    rep(i, n){
        scanf("%d %d %d %d", &A.x, &A.y, &B.x, &B.y);
        if(A.x == B.x){
            if(A.y > B.y) swap(A, B);
            V2.PB(Line(A, B));
        }

        else{
            if(A.x > B.x) swap(A, B);
            V1.PB(Line(A, B));
        }
    }

    hopkarp.init(sz(V1), sz(V2));
    rep(i, sz(V1)) rep(j, sz(V2)){
        if(V1[i].P1.x <= V2[j].P1.x && V1[i].P2.x >= V2[j].P1.x &&
           V2[j].P1.y <= V1[i].P1.y && V2[j].P2.y >= V1[i].P1.y) {
            hopkarp.add(i + 1, j + 1);
        }
    }

    printf("%d", n - hopkarp.maxMatching());
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define maxn 255
using namespace std;

int cap[maxn][maxn];
int trace[maxn];
int xa[maxn],ya[maxn],xb[maxn],yb[maxn];
int n,start,finish;

bool intersect(int p1,int p2) {
    return (ya[p1] <= ya[p2] && yb[p2] <= yb[p1] && xa[p2] <= xa[p1] && xb[p1] <= xb[p2]);
}

int maxFlow() {
    int ans = 0;
    while (1) {
        memset(trace,-1,sizeof(trace));
        trace[start] = -2;

        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v = 0; v <= finish; v++) if (cap[u][v] > 0 && trace[v] == -1) {
                trace[v] = u;
                q.push(v);
            }
        }
        if (trace[finish] == -1) return ans;

        for (int i = 0; i <= finish; i++) if (trace[i] != -1 && cap[i][finish] > 0) {
            int add = cap[i][finish];
            for (int v = i,u = trace[v]; v != start; v = u,u = trace[v]) add = min(add,cap[u][v]);
            if (!add) continue;
            ans += add;
            cap[i][finish] -= add;
            cap[finish][i] += add;
            for (int v = i,u = trace[v]; v != start; v = u,u = trace[v]) {
                cap[u][v] -= add;
                cap[v][u] += add;
            }
        }
    }
}

int main() {
   // freopen("I.10","r",stdin);
    //freopen("steeple.out","w",stdout);

    scanf("%d", &n);
    start = 0;  finish = n + 1;
    memset(cap,0,sizeof(cap));
    for (int i = 1; i <= n; i++) {
        scanf("%d %d %d %d", &xa[i], &ya[i], &xb[i], &yb[i]);
        if (xa[i] > xb[i]) swap(xa[i],xb[i]);
        if (ya[i] > yb[i]) swap(ya[i],yb[i]);
        if (xa[i] == xb[i]) cap[start][i] = 1; else cap[i][finish] = 1;
    }
    for (int i = 1; i <= n; i++) if (cap[start][i])
      for (int j = 1; j <= n; j++) if (cap[j][finish] && intersect(i,j)) cap[i][j] = 1;
    printf("%d\n", n - maxFlow());
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define MAX   259
#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;
typedef pair<int,int> ii;
typedef pair<ii,int> pii;
vector<pii> hor,ver;
vector<int> g[MAX];
int t[MAX];
int matx[MAX];
int maty[MAX];
int n;
void init(void) {
    scanf("%d",&n);
    int x1,y1,x2,y2;
    REP(i,n) {
        scanf("%d",&x1);
        scanf("%d",&y1);
        scanf("%d",&x2);
        scanf("%d",&y2);
        if (x1==x2) hor.push_back(pii(ii(min(y1,y2),max(y1,y2)),x1));
        else ver.push_back(pii(ii(min(x1,x2),max(x1,x2)),y1));
    }
}
bool intersect(const pii &a,const pii &b) {
    if (b.se<a.fi.fi || b.se>a.fi.se) return (false);
    if (b.fi.se<a.se || b.fi.fi>a.se) return (false);
    return (true);
}
void loadgraph(void) {
    REP(i,hor.size()) REP(j,ver.size())
        if (intersect(hor[i],ver[j])) g[i+1].push_back(j+1);
}
int findway(int s) {
    queue<int> q;
    while (!q.empty()) q.pop();
    memset(t,0,sizeof t);
    q.push(s);
    int u;
    while (!q.empty()) {
        u=q.front();q.pop();
        FORE(it,g[u]) if (t[*it]==0) {
            t[*it]=u;
            if (maty[*it]==0) return (*it);
            else q.push(maty[*it]);
        }
    }
    return (0);
}
void enlarge(int f) {
    int cur,next;
    cur=f;
    do {
        next=matx[t[cur]];
        matx[t[cur]]=cur;
        maty[cur]=t[cur];
        cur=next;
    }
    while (cur>0);
}
void maxmatching(void) {
    memset(matx,0,sizeof matx);
    memset(maty,0,sizeof maty);
    FOR(i,1,hor.size()) {
        int t=findway(i);
        if (t>0) enlarge(t);
    }
    int res=0;
    FOR(i,1,hor.size()) if (matx[i]>0) res++;
    printf("%d",n-res);
}
int main(void) {
    init();
    loadgraph();
    maxmatching();
    return 0;
}