【题解】BZOJ4883: [Lydsy1705月赛]棋盘上的守卫(最小生成基环森林)
2024-09-06 15:50:20
【题解】BZOJ4883: [Lydsy1705月赛]棋盘上的守卫(最小生成基环森林)
神题
我的想法是,每行每列都要有匹配且一个点只能匹配一个,于是就把格点和每行每列建点出来做一个最小生成树,但是不幸的是,这样子无法控制一个点是否选择多次,并且无法控制那些不需要变成守卫的点的情况
然后我看了题解..
一个元素的两种状态可以对应上一条边的方向,现在问题就变成了要选出一些边使得所有点的入度为1。也就是一个外向基环森林,直接类似克鲁斯卡尔做就行了。
这貌似可以抽象成一种模型,也就是有待选点,匹配点,待选点匹配点只能选择且必须选择一个待选点,一个待选点只能选择一个匹配点,同一个点任意选择匹配代价一样。若可以接受\(O(\prod P_i)\)的复杂度其中\(P\)代表一种匹配点的个数,那么就可以这样考虑给边定向构成外向基环森林来做。
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; typedef long long ll;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(!isdigit(c))f|=c==45,c=getchar();
while(isdigit(c)) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
const int maxn=1e6+5;
struct E{
int u,v,w;
inline bool operator <(const E&a){return w<a.w;}
};
vector<E> e;
int n,m,cnt;
ll w;
inline void add(const int&fr,const int&to,const int&w){e.push_back({fr,to,w});}
int r[maxn*3],siz[maxn*3],c[maxn*3];
inline int q(const int&x){
int t=x,i=x,temp;
while(t^r[t]) t=r[t];
while(i^r[i]) temp=r[i],r[i]=t,siz[t]+=siz[i],siz[i]=0,c[t]|=c[i],c[i]=0,i=temp;
return t;
}
inline void J(int x,int y){
if(siz[q(x)]>siz[q(y)])swap(x,y);
r[q(x)]=q(y); q(x);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("cpp.in","r",stdin);
freopen("cpp.out","w",stdout);
#endif
n=qr(); m=qr();
cnt=n+m;
for(int t=1;t<=n;++t)
for(int i=1,u;i<=m;++i)
u=qr(),add(t,i+n,u);
for(int t=1;t<=cnt;++t) r[t]=t,siz[t]=1;
sort(e.begin(),e.end());
for(int t=0,ed=e.size();t<ed;++t){
int u=q(e[t].v),v=q(e[t].u);
if(!c[u]||!c[v]){
//printf("%d %d\n",u,v);
if(u==v) c[u]=c[v]=1;
J(u,v),w=w+e[t].w;
}
}
printf("%lld\n",w);
cerr<<"w = "<<w<<endl;
return 0;
}
最新文章
- iOS 开发总结(下)
- c语言数据结构复习
- Bootstrap<;基础十三>; 按钮组
- android自定义view仿照MIUI中音量控制效果
- android studio ndk使用openMP
- js网页换肤
- Cppcheck代码分析(2)
- BZOJ 1034: [ZJOI2008]泡泡堂BNB( 贪心 )
- 用C语言怎么实现复制自己
- Java Tread多线程(0)一个简单的多线程实例
- 微信小程序登录数据解密以及状态维持
- Python 并发编程(一)之线程
- angular2 学习笔记 ( translate, i18n 翻译 )
- Android 在Fragment中执行onActivityResult不被调用的简单解决方法
- day26 Python 改变对象的字符串显示
- linux系统调用之网络管理2
- [luogu3258][JLOI2014]松鼠的新家
- js 锚点定位【转】
- 【生产问题】记还原一个很小的BAK文件,但却花了很长时间,分析过程
- Python通过LDAP验证、查找用户(class,logging)
热门文章
- deepin golang微服务搭建go-micro环境
- css实现简单的页面自适应宽度
- h5 的canvas绘制基本图形
- H3C HDLC协议使用限制
- Java 参数的值传递和引用传递
- python基础十四之匿名函数
- SpringBoot 上传文件到linux服务器 异常java.io.FileNotFoundException: /tmp/tomcat.50898……解决方案
- 一道非常棘手的 Java 面试题:i++ 是线程安全的吗
- vue-learning:40 - Vuex - 第一篇:概念和基本使用
- CodeForces - 617E XOR and Favorite Number (莫队+前缀和)