题意:给定N个红点二维坐标N个蓝点二维坐标,如果红点横纵坐标都比蓝点小,那么它们能够构成一组。问最多能构成多少组。
题解:把满足要求的红蓝点连线,然后就是匈牙利算法(详情见,写的好棒!)
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int maxn=160; 7 int a[maxn],b[maxn],c[maxn],d[maxn]; 8 bool used[maxn]; 9 int girl[maxn],line[maxn][maxn];10 int n;11 12 bool Find(int x)13 {14 for(int j=1;j<=n;j++)15 {16 if(line[x][j]&&!used[j]){17 used[j]=1;18 if(girl[j]==0||Find(girl[j])){19 girl[j]=x;20 return true;21 }22 }23 }24 return false;25 }26 27 int main()28 {29 cin>>n;30 for(int i=1;i<=n;i++) cin>>a[i]>>b[i];31 for(int i=1;i<=n;i++) cin>>c[i]>>d[i];32 memset(line,0,sizeof(line));33 for(int i=1;i<=n;i++)34 {35 for(int j=1;j<=n;j++){36 if((a[i]