90分,WA#2求调,玄关
查看原帖
90分,WA#2求调,玄关
775893
OIDragon楼主2023/11/12 09:19

代码:(码风应该还行。。。)

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,cnt;
int xa[255],xb[255],ya[255],yb[255],a[255],b[255],c[255],d[255];
struct edge
{
	int p,q;
}ed[1000005];
void add(int u,int v)
{
	ed[++ans] = {v,d[u]};
	d[u] = ans;
}
int match(int u)
{
	b[u] = 1;
	for(int i = d[u];i != 0;i = ed[i].q)
	{
		int v = ed[i].p;
		if(b[c[v]] != 0)
		{
			continue;
		}
		if(c[v] == 0 || match(c[v]) != 0)
		{
			c[v] = u;
			return 1;
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&n);
	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])
		{
			a[i] = 1;
			m++;
		}
		else
		{
			a[i] = 2;
		}
	}
	for(int i = 1;i <= n - 1;i++)
	{
		for(int j = i + 1;j <= n;j++)
		{
			if(a[i] == 1 && a[j] == 2)
			{
				if(xa[i] >= xa[j] && xb[i] <= xb[j] && ya[j] >= ya[i] && yb[j] <= yb[i])
				{
					add(i,j + m);
				}
			}		
			if(a[i] == 2 && a[j] == 1)
			{
				if(xa[j] >= xa[i] && xb[j] <= xb[i] && ya[i] >= ya[j] && yb[i] <= yb[j])
				{
					add(j,i + m);
				}
			}		
		}
	}	
	for(int i = 1;i <= n;i++)
	{
		if(a[i] == 2)
		{
			continue;
		}
		memset(b,0,sizeof(b));
		if(match(i) == 1)
		{
			cnt++;
		}
	}
	printf("%d",n - cnt); 
	return 0;
}

请看见的大佬挑挑错,谢谢!

2023/11/12 09:19
加载中...