萌新求助 40分代码 匈牙利最大独立集
查看原帖
萌新求助 40分代码 匈牙利最大独立集
648772
Liyuqiao11楼主2023/6/17 21:57
#include<bits/stdc++.h>
using namespace std;
const int N = 300;
int n,vis[N],match[N],ans;
vector<int> G[N];
struct P{
	int x;
	int y;
	int x_2;
	int y_2;
}a[N]; 
bool check(int u,int v){
	if(a[u].x==a[u].x_2&&a[v].x==a[v].x_2){
		return false;
	}
	if(a[u].y==a[u].y_2&&a[v].y==a[v].y_2){
		return false;
	}
	if(a[u].x==a[u].x_2&&a[v].y==a[v].y_2){
		if(a[u].x>=a[v].x&&a[u].x<=a[v].x_2&&a[v].y>=a[u].y&&a[v].y<=a[u].y_2){
			return true;
		}
		else return false;
	}
	if(a[u].y==a[u].y_2&&a[v].x==a[v].x_2){
		if(a[u].y>=a[v].y&&a[u].y<=a[v].y_2&&a[v].x>=a[u].x&&a[v].x<=a[u].x_2){
			return true;
		}
		else return false;
	}
}
bool dfs(int x,int t){
	if(vis[x]==t){
		return false;
	}
	vis[x]=t;
	for(int i=0;i<G[x].size();i++){
		int v=G[x][i];
		if(match[v]==0||dfs(match[v],t)){
			match[v]=x;
			return true;
		}
	}
	return false;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x,y,x_2,y_2;
		cin>>x>>y>>x_2>>y_2;
		if(x>x_2){
			swap(x,x_2);
		}
		if(y>y_2){
			swap(y,y_2);
		}
		a[i].x=x;
		a[i].y=y;
		a[i].x_2=x_2;
		a[i].y_2=y_2;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(check(i,j)){
				G[i].push_back(j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dfs(i,i)){
			ans++;
		}
	}
	cout<<n-ans<<endl;
	return 0;
}
2023/6/17 21:57
加载中...