题解：P11409 西湖有雅座
简洁思路
由于数据比较小，可以先预处理出任何两个零件是否能出现在同一栋大楼上。即枚举所有的两个零件，根据题意去模拟判断条件是否满足：
\[\forall i,j \in U,f\left (i,j\right) \ge \lceil \frac{ \min \left ( S\left(i \right),S\left(j\right) \right) }{2} \rceil \]若不符合则连一条边。然后便可以直接转化为二分图染色问题求解。
关于二分图染色的简洁说明
把二分图中不能处于同一集合的点连一条边，在该边两端染上不同颜色，即 0 和 1 。若出现矛盾则说明不能成立，直接返回。（这只是笔者自己的简洁理解，若要掌握二分图染色还是要自己去找博客系统学习）
code
#include<bits/stdc++.h>
using namespace std;
int n,h,w;
const int N=1005;
int a[1000+5][10][10];
int t[N];
vector<int>g[N];
int k[N];
int s[N];
int ans;
bool dfs(int u,int c){
k[u]=c;s[c]++;
for(auto v:g[u]){
if(k[v]==k[u]) return false;
if(k[v]==-1&&!dfs(v,1-c)) return false;
}
return true;
}
int main(){
cin>>n>>h>>w;
for(int i=1;i<=n;i++){
for(int j=1;j<=h;j++)
for(int k=1;k<=w;k++){
cin>>a[i][j][k];
t[i]+=a[i][j][k];
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j) continue;
int f=0;
for(int x=1;x<=h;x++)
for(int y=1;y<=w;y++){
f+=a[i][x][y]&&a[j][x][y];
}
if(f<(min(t[i],t[j])+1)/2){
g[i].push_back(j);
g[j].push_back(i);
}
}
memset(k,-1,sizeof k);
for(int i=1;i<=n;i++){
int p0=s[0];
int p1=s[1];
if(k[i]==-1&&!dfs(i,1)){
cout<<-1<<endl;
return 0;
}
ans+=max(s[0]-p0,s[1]-p1);
}
cout<<ans<<endl;
return 0;
}
本题后记
本题为 2024 年 12 月的 [DHOI] Round 1 洛谷比赛中,数据实在过水。同机房的 QC dalao 直接写了个假贪心过了第二和第三个包（难以想象），而 FRZ dalao 则写出了第一个包，于是……
超级缝合怪。
水数据点AC_code
#ifndef ONLINE_JUDGE
#define FRZ_29
#endif
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
//using i128 = __int128;
const int N = 1005;
#define PRINT(x) cout << #x << " = " << x << "\n"
#define LF(i, l, r) for (int i = (l); i <= (r); i++)
#define RF(i, r, l) for (int i = (r); i >= (l); r++)
int n, h, w, s[N], f[N][N];
int m[N][10][10], ans;
vector<int> U;
bool vis[N];
bool check() {
LF(i, 0, U.size() - 1) {
LF(j, i + 1, U.size() - 1) {
if (f[U[i]][U[j]] < (min(s[U[i]], s[U[j]]) + 1) / 2) {
return false;
}
}
}
LF(i, 1, n) {
if (vis[i]) continue;
LF(j, i + 1, n) {
if (vis[j]) continue;
if (f[i][j] < (min(s[i], s[j]) + 1) / 2) return false;
}
}
return true;
}
void dfs(int d) {
if (d == n + 1) {
if (check()) ans = max(ans, max((int)(n - U.size()), (int)(U.size())));
return;
}
U.push_back(d);
vis[d] = 1;
dfs(d + 1);
U.pop_back();
vis[d] = 0;
dfs(d + 1);
}
int a[1005][15][15];
int sum[1005];//f[1005][1005];
int num[1005][1005];
struct node
{
int id,s;
}frz[1005];
bool cmp(node x,node y){return x.s<y.s;}
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}
while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(int)(c-'0');c=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void solve()
{
// cin>>n>>h>>w;
for(int i=1;i<=n;i++)
for(int j=1;j<=h;j++)
for(int k=1;k<=w;k++) cin>>a[i][j][k],sum[i]+=a[i][j][k];
for(int oi=1;oi<=n;oi++)
{
for(int oj=1;oj<=n;oj++)
{
if(oj==oi) continue;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++) f[oi][oj]=f[oi][oj]+(a[oi][i][j]&a[oj][i][j]);
}
}
for(int i=1;i<=n;i++)
{
frz[i].id=i;
for(int j=1;j<=n;j++)
{
// if(i==j) continue;
// cout<<f[i][j]<<" "<<((min(sum[i],sum[j])+1)/2)<<endl;
if(f[i][j]<((min(sum[i],sum[j])+1)/2))
{
num[i][j]=1;
}
frz[i].s+=num[i][j];
}
}
sort(frz+1,frz+n+1,cmp);
for(int i=1;i<=n;i++)
{
int kkk=frz[i].id;
if(vis[kkk]==0)
{
ans++;
for(int j=1;j<=n;j++)
{
if(num[kkk][j]==1)
{
vis[j]=1;
}
}
}
}
if(ans==1) cout<<-1<<endl;
else cout<<ans<<endl;
}
int main() {
//#ifdef FRZ_29
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
//#endif
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> h >> w;
if(n>20) {solve();return 0;}
LF(i, 1, n) LF(j, 1, h) LF(k, 1, w) {
cin >> m[i][j][k];
s[i] += m[i][j][k];
}
LF(i, 1, n) LF(j, i + 1, n) LF(k, 1, h) LF(p, 1, w)
f[i][j] += (m[i][k][p] & m[j][k][p]);
dfs(1);
cout << (ans == 0 ? -1 : ans);
return 0;
}
// START AT 2024 / 12 / 15 13 : 56 : 15
水完了。
yingxilin
Qian·JX のjoker
2024-12-18 于玉山一中