求助60分
查看原帖
求助60分
362238
mattinas楼主2021/5/10 20:32

匈牙利做的,调不动了qwq

#include<bits/stdc++.h>
using namespace std;
#define maxn 260
int n;
struct node{int x,y,next;}e[maxn*2];
int len=0;
int last[maxn];
bool v[maxn];
int f[maxn];
struct edge{int a1,b1,a2,b2;}q[maxn];
void ins(int x,int y)
{
	len++;
	e[len]={x,y,last[x]};
	last[x]=len;
}
bool pd(int x,int y)
{
	if(q[x].a1==q[x].a2)
	{
		if(q[x].a1>=min(q[y].a1,q[y].a2)&&q[x].a1<=max(q[y].a1,q[y].a2)&&q[y].b1>=min(q[x].b1,q[x].b2)&&q[y].b1<=max(q[x].b1,q[x].b2))
		return true;
		return false;
	}
	else if(q[y].a1==q[y].a2)
	{
		swap(x,y);
		if(q[x].a1>=min(q[y].a1,q[y].a2)&&q[x].a1<=max(q[y].a1,q[y].a2)&&q[y].b1>=min(q[x].b1,q[x].b2)&&q[y].b1<=max(q[x].b1,q[x].b2))
		return true;
		return false;
	}
	else return false;
}
bool dfs(int x)
{
	for(int i=last[x];i!=-1;i=e[i].next)
	{
		int y=e[i].y;
		if(!v[y])
		{
			v[y]=true;
			if(!f[y]||dfs(f[y]))
			{
				f[y]=x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
//	freopen("text.in","r",stdin);
//	freopen("text.out","w",stdout);
	scanf("%d",&n);
	int x,c,y,a,b;
	memset(last,-1,sizeof(last)); 
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&x,&y,&a,&b);
		q[i]={x,y,a,b};
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j&&pd(i,j))ins(i,j);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		memset(v,false,sizeof(v));
		if(dfs(i))ans++;
	}
	printf("%d",n-ans/2);
	return 0;
}
2021/5/10 20:32
加载中...