To_Heart—题解——P6234 [eJOI2019] T形覆盖

link.

突然很想写这篇题解。虽然题目不算难。

考场只有30分是为什么呢？看来是我没有完全理解这道题目吧！

首先很明显的转换是，把 T 型覆盖看成十字形，再考虑最后减去某一块的贡献。

然后然后直接往原图上面放十字形!对于每一个十字的中心来说，实际上它只需要三个相邻的方块就可以了。而我们发现两个十字重合的部分不会超过两个方块，也就是说把这两个方块任意分配给两个人，就能保证这两个每个人都只会舍弃一个方块。

因为每次两个十字的重合最多只能让每个点丢弃一个方块，并且每次重合至少有一个十字会丢弃掉一个方块，所以惊天的结论是我们可以直接计算整个十字连通块的中心点和非中心点的个数。如果非中心点的个数大于等于中心点的个数的三倍，那么当前连通块一定合法，否则不能保证每个十字的中心点都能分配到刚好三个非中心点，即无解。

但是可能有非中心点的个数大于中心点的个数的三倍。这种情况说明所有的十字都只重合了一个点，那么必须要丢掉一个非中心点。因为要权值最大所以丢掉最小权值的就好了。

其实这个的实现方式有很多，但是我使用了并查集。为什么呢？因为其他题解就是用的并查集啊！

然后并查集需要注意的点就是不能选择中心点啊。中心点的权值设为最大值好不好。

#include<bits/stdc++.h>
using namespace std;int n,m,k;
int a[1000005];
int ID(int x,int y){return (x-1)*m+y;
}
int pre[1000005],dp[1000005];
int sz[1000005][2];
long long sum[1000005];bool vis[1000005];struct zz{int x,y;
}t[1000005];int Find(int x){if(pre[x]!=x) pre[x]=Find(pre[x]);return pre[x];
}
void Join(int x,int y){int fx=Find(x),fy=Find(y);if(fx==fy) return ;pre[fy]=fx,sum[fx]+=sum[fy],dp[fx]=min(dp[fx],dp[fy]),sz[fx][0]+=sz[fy][0],sz[fx][1]+=sz[fy][1];
}int fx[5]={0,1,-1,0,0};
int fy[5]={0,0,0,1,-1};int main(){
//	freopen("t-covering.in","r",stdin);
//	freopen("t-covering.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[ID(i,j)]);cin>>k;for(int i=1,x,y;i<=k;i++) scanf("%d%d",&x,&y),t[i]=(zz){x+1,y+1};for(int i=1;i<=k;i++) vis[ID(t[i].x,t[i].y)]=1;for(int i=1;i<=n*m;i++){pre[i]=i,sum[i]=a[i],dp[i]=a[i],sz[i][vis[i]]=1;if(vis[i]) dp[i]=0x3f3f3f3f; }for(int i=1;i<=k;i++) for(int j=1;j<=4;j++){int x=t[i].x,y=t[i].y;int dx=x+fx[j],dy=y+fy[j];if(dx<=0||dx>n||dy<=0||dy>m) continue;Join(ID(x,y),ID(dx,dy)); }long long ans=0;memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){int x=(ID(i,j));int fx=Find(x);if(vis[fx]) continue; vis[fx]=1;if(sz[fx][0]<sz[fx][1]*3) return printf("No\n"),0;else if(sz[fx][0]==sz[fx][1]*3) ans+=sum[fx];else ans+=sum[fx]-dp[fx];}cout<<ans<<endl;return 0;
}