题面
横的，竖的线短段，求最多能取几条没有相交的线段？
思路
学过网络流的童鞋在哪里？
是时候重整网络流雄风了！
好吧，废话不多说
这是一道最小割的题目
怎么想呢？
要取最多，那反过来不就是不能取的要尽量少吗？
深思熟虑一番后，符合网络流中的最小割，于是开码
哦，还没完！
建边是关键！
由于只有方向不同的线段才会互相影响，所以考虑在方向不同时建边
由于最小割的用途是使图不连通，所以我们把横的线段与源点相连，竖的线段与汇点相连（相反也可以），在有相交的线段之间建一条边，表示能连通，这样就变成了求最小割
但是！
要注意的是：由于题目的要求是取线段，而不是我们建的边，因此我们把一个点（线段）拆成入点和出点，在入点和出点之间建一条容量为1的边，其余边的容量都赋为INF，这样就肯定不会“割”去边，只会“割”去点
还有！
怎么判断线段香蕉相交呢？
画出来就知道了
这个小问题，就留给大家思考吧
Code：
#include<bits/stdc++.h>//虽然我不想写注释
#define INF 0x7f7f7f7f//但是不写注释的不是好孩纸？！h^ovny：谁说的！
#define M 65010
#define N 510
using namespace std;
struct Node{
int lx,ly,rx,ry,i;
Node(int a,int b,int c,int d,int e):lx(a),ly(b),rx(c),ry(d),i(e){ }
Node(){ }
}A[N>>1],B[N>>1];//这个是分开存横的和竖的线段
struct node{
int to,cap;
int nxt;
node(int a,int b):to(a),cap(b){ }
node(){ }
}b[M<<1];//边
int head[N],deep[N];
int n,Maxflow,S,T,t=1,ta,tb;
int read()
{
int s=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
s=(s<<1)+(s<<3)+c-'0';
c=getchar();
}
return s;
}
void add(int x,int y,int cap)//建边，比较冗长，别介意
{
b[++t]=node(y,cap);
b[t].nxt=head[x];
head[x]=t;
b[++t]=node(x,0);
b[t].nxt=head[y];
head[y]=t;
return;
}
bool BFS()
{
int i,cur;
int to,cap;
queue<int>p;
memset(deep,0,sizeof(deep));
deep[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;cap=b[i].cap;
if(cap&&!deep[to])
{
deep[to]=deep[cur]+1;
p.push(to);
if(to==T)
return 1;
}
}
}
return 0;
}
int Dinic(int k,int flow)
{
if(k==T)
return flow;
int 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&&deep[to]==deep[k]+1)
{
res=Dinic(to,min(rest,cap));
if(!res)
deep[to]=0;
b[i].cap-=res;
b[i^1].cap+=res;
rest-=res;
}
}
return flow-rest;
}
int main()
{
int i,j,flow;
int lx,ly,rx,ry;
n=read();T=n+n+1;//源点一般赋为0，那就先确定汇点
for(i=1;i<=n;i++)//读入，然后开始玄学建边
{
lx=read();ly=read();
rx=read();ry=read();
if(lx==rx)
{
B[++tb]=Node(min(lx,rx),min(ly,ry),max(lx,rx),max(ly,ry),i);//注意，要是两端点有序！
add(S,i,INF);
for(j=1;j<=ta;j++)//判断是否满足，然后建边
if(B[tb].ry>=A[j].ly&&B[tb].ly<=A[j].ly&&A[j].lx<=B[tb].lx&&B[tb].lx<=A[j].rx)
add(i+n,A[j].i,INF);
}
else
{
A[++ta]=Node(min(lx,rx),min(ly,ry),max(lx,rx),max(ly,ry),i);
add(i+n,T,INF);//一切同上
for(j=1;j<=tb;j++)
if(B[j].ry>=A[ta].ly&&B[j].ly<=A[ta].ly&&A[ta].lx<=B[j].lx&&B[j].lx<=A[ta].rx)
add(B[j].i+n,i,INF);
}
add(i,i+n,1);//自己的入点和出点之间建边
}
while(BFS())//Dinic模板直接搬
while((flow=Dinic(S,INF)))
Maxflow+=flow;
printf("%d",n-Maxflow);
return 0;
}