1. 题面
  2. 解题思路
  3. Code

Updata 2019.11.13 今天膜你赛做到了原题，不得不来修一下 blog

题面

有 n 条平行于坐标轴线段，取的线段要求不相交，最大化所取线段数目

解题思路

二分图匹配

分析

把平行于 x 轴和平行于 y 轴的线段分别看成两个集合，这样就和二分图有关了

从最小割的方面想，要想所选的数目尽量多，那么就是不能选的尽量少

显然，如果两条线段有相交的部分，则有一条必不能取，因此以是否相交为依据建边，再跑一个最小割，或者说就是二分图的最大匹配，答案即为 n−Maxflow

可以用 Dinic 或者匈牙利算法实现

warning

个人认为最大的坑点是所给的线段的端点不是有序的，比如平行于 x 轴的线段的两个端点可能并不是按照两点 x 坐标的大小给出，要特别判断，否则，判断相交的时候就 GG 了，当然不要忘记网络流建边开四十倍

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define M 3000003
#define N 257
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct Edge{
    int to,nxt,cap;
    Edge(int a,int b,int c):to(a),nxt(b),cap(c){}
    Edge(){}
}b[M];
struct segment{
    int lx,ly,rx,ry;
    inline void in() {
        lx=read(),ly=read(),
        rx=read(),ry=read();
        if(lx>rx) lx^=rx^=lx^=rx;//可能不是有序的
        if(ly>ry) ly^=ry^=ly^=ry;
    }
}A[N],B[N],c;
int n,la,lb,t=1,S,T,head[N],dep[N],Maxflow;
inline void add(rint x,rint y) {
    b[++t]=Edge(y,head[x],1),head[x]=t,
    b[++t]=Edge(x,head[y],0),head[y]=t;
}
inline bool cross(rgt segment a,rgt segment b) {//判断相交
    return b.lx<=a.lx&&a.lx<=b.rx&&a.ly<=b.ly&&b.ly<=a.ry;
}
inline bool BFS() {
    rint i,to,cur,cap;
    queue<int>p;
    memset(dep,0,sizeof(dep));
    dep[S]=1,p.push(S);
    while(!p.empty()) {
        cur=p.front(),p.pop();
        for(i=head[cur];i;i=b[i].nxt) {
            to=b[i].to;
            if(b[i].cap&&!dep[to]) {
                dep[to]=dep[cur]+1;
                if(to==T) return 1;
                p.push(to);
            }
        }
    }return 0;
}
inline int Dinic(rint k,rint flow) {
    if(k==T) return flow;
    rint i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt) {
        to=b[i].to,cap=b[i].cap;
        if(cap&&dep[to]==dep[k]+1) {
            res=Dinic(to,min(rest,cap));
            if(!res) dep[to]=0;
            b[i].cap-=res,
            b[i^1].cap+=res,
            rest-=res;
        }
    }
    return flow-rest;
}
int main() {
    rint i,j,flow;n=read();
    for(i=1;i<=n;i++) {
        c.in();
        if(c.lx==c.rx) A[++la]=c;//按照平行的坐标分组
        else B[++lb]=c;
    }T=n+1;
    for(i=1;i<=la;i++) add(S,i);//超源和超汇
    for(i=1;i<=lb;i++) add(i+la,T);
    for(i=1;i<=la;i++)
        for(j=1;j<=lb;j++)
            if(cross(A[i],B[j]))//相交就建边
                add(i,j+la);
    while(BFS())//Dinic大法吼
        while((flow=Dinic(S,inf)))
            Maxflow+=flow;
    printf("%d",n-Maxflow);
    return 0;
}

devil.