利用二分图匹配求最大独立集

本题的边一定平行于坐标轴，且同向的线段一定不重合，这是经典的二分图建图方法，本题要求的是最大不重合的线段数，那就是求二分图的最大独立集，最大独立集=总点数-最大匹配数。

本题有一个坑点，就是输入的数据不一定有序，也就是x1不一定比x2小

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return rv*fh;

}

int n,x,y,g[300][300],match[300];

bool f[300];

struct line{

	int a,b,c;

}col[300],row[300];

bool hungarian(int u){

	for(int i=1;i<=g[u][0];i++){

		int v=g[u][i];

		if(!f[v]){

			f[v]=1;

			if(!match[v]||hungarian(match[v])){

				match[v]=u;

				return 1;

			}

		}

	}

	return 0;

}

int main(){

	n=init();

	for(int i=1;i<=n;i++){

		int a=init(),b=init(),c=init(),d=init();

		if(a==c){

			col[++x].a=a;

			col[x].b=min(b,d);

			col[x].c=max(b,d);

		}else{

			row[++y].a=b;

			row[y].b=min(a,c);

			row[y].c=max(a,c);

		}

	}

	for(int i=1;i<=x;i++){

		for(int j=1;j<=y;j++){

			if(col[i].b<=row[j].a&&col[i].c>=row[j].a&&row[j].b<=col[i].a&&row[j].c>=col[i].a){

				g[i][++g[i][0]]=j;

			}

		}

	}

	int ans=0;

	for(int i=1;i<=x;i++){

		memset(f,0,sizeof(f));

		if(hungarian(i)) ans++;

	}

	cout<<n-ans<<endl;

	return 0;

}