1 条题解
-
0
根据闭矩形坐标建立二分图,先找完整匹配,再依次禁用每条匹配边重求匹配;存在替代完整匹配即不唯一,输出None。只有唯一完美匹配时按字母顺序输出。
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;vector<array<int,4>>a(n);for(auto&row:a)for(int&x:row)cin>>x;vector<vector<int>>g(n);for(int i=0;i<n;i++){int x,y;cin>>x>>y;for(int j=0;j<n;j++)if(a[j][0]<=x&&x<=a[j][1]&&a[j][2]<=y&&y<=a[j][3])g[j].push_back(i);}auto match=[&](int blocku,int blockv,vector<int>&mate){mate.assign(n,-1);function<bool(int,vector<bool>&)>dfs=[&](int u,vector<bool>&used){for(int v:g[u])if(!(u==blocku&&v==blockv)&&!used[v]){used[v]=true;if(mate[v]<0||dfs(mate[v],used)){mate[v]=u;return true;}}return false;};for(int u=0;u<n;u++){vector<bool>used(n);if(!dfs(u,used))return false;}return true;};vector<int>mate,result(n),test;if(!match(-1,-1,mate)){cout<<"None\n";return 0;}for(int v=0;v<n;v++)result[mate[v]]=v;for(int u=0;u<n;u++)if(match(u,result[u],test)){cout<<"None\n";return 0;}for(int u=0;u<n;u++)cout<<char('A'+u)<<" "<<result[u]+1<<"\n"; return 0; }
- 1
信息
- ID
- 4070
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者