80求助
查看原帖
80求助
800499
suzhikz楼主2024/11/13 22:29
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define db double
#define il inline
using namespace std;
void read(int &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
void read(ll &x){x=0;int f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}x*=f;}
const int N=2055;
int head[N],to[N*N*2],nex[N*N*2],w[N*N*2],cnt=1;
void add(int u,int v,int ww){
//	if(ww)cout<<u<<' '<<v<<endl;
	cnt++;to[cnt]=v;w[cnt]=ww;nex[cnt]=head[u];head[u]=cnt;
}
int n;
int f[N],a[N],b[N],c[N],d[N];
int deep[N],noww[N];
int s=0,t=N-2;
bool bfs(){
	queue<int>q;q.push(s);
	memset(deep,0,sizeof(deep));deep[0]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		noww[x]=head[x];
		for(int i=head[x];i;i=nex[i]){
			int y=to[i];
			if(w[i]==0||deep[y]!=0)continue;
			deep[y]=deep[x]+1;q.push(y);
		}
	}
	return deep[t]!=0;
}
int dfs(int x,int summ){
	if(x==t)return summ;
	int tmp,us=0;
	for(int i=noww[x];i;i=nex[i]){
		noww[x]=i;
		int y=to[i];
		if(w[i]==0||deep[y]!=deep[x]+1)continue;
		tmp=dfs(y,min(summ,w[i]));
		w[i]-=tmp;w[i^1]+=tmp;
		summ-=tmp;us+=tmp;
		if(summ==0)break;
	}
	return us;
}
int ans;
int main(){
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);read(b[i]);read(c[i]);read(d[i]);
		if(a[i]!=c[i]){
			f[i]=0;
			if(a[i]>c[i])swap(a[i],c[i]); 
		}else{
			f[i]=1;
			if(b[i]>d[i])swap(b[i],d[i]);
		}
	}
	for(int i=1;i<=n;i++){
		add(i*2-1,i*2,1);add(i*2,i*2-1,0);
		if(f[i]){
			add(s,i*2-1,1);add(i*2-1,s,0);
		}
		else {
			add(i*2,t,1);add(t,i*2,0);
		}
		for(int j=i+1;j<=n;j++){
			if(i==j)continue;
			if(f[i]!=f[j]){
				if(f[i]==0){
					if(b[j]<=b[i]&&d[j]>=b[i]&&a[j]>=a[i]&&a[j]<=c[i]){
						add(i*2,j*2-1,1);
						add(j*2-1,i*2,1);
					}
				}else{
					swap(i,j);
					if(b[j]<=b[i]&&d[j]>=b[i]&&a[j]>=a[i]&&a[j]<=c[i]){
						add(i*2,j*2-1,1);
						add(j*2-1,i*2,1);
					}
					swap(i,j);
				}
			}
		}
	}
	while(bfs())ans+=dfs(s,123456);
	cout<<n-ans;
	return 0;
}

2024/11/13 22:29
加载中...