首页 > 其他分享 >高一下三调模拟赛5.13(附关于二分图匈牙利建边的详细思考)

高一下三调模拟赛5.13(附关于二分图匈牙利建边的详细思考)

时间:2024-05-13 21:55:13浏览次数:28  
标签:二分 个点 int 5.13 建边 三调 now 部分 addedge

前言注:本篇为知识性内容,A题附详解关于匈牙利算法求最大独立子集难以理解的建边问题的思考,若有不当之处感谢指出。暂时只写了A篇题解,以供帮助大家理解相关问题,剩余题解会进行补充。

又是小集训的一周,总要伴随着模拟赛...

还是五道题目:

A. 攻击装置
B. 循环
C. 漫步
D. 穿越
E. 结队

赛时拿了230...太菜了,本来预料中ABC全 $ AC $ 的,结果出乎意料地windows + dev给了我当头一棒,我不管,就是他俩的锅, 谁让dev开了O2也不给我报错, 导致我C题

$ Compile  Error$
(重载运算符operator 前没加bool类型)

  

  • A. 攻击装置

题目

赛前huge就已经告诉过我们考题有二分图,再看到这个题“装置互不攻击”,明显了,直接开打,但因为建边问题调了一个小时才搓出来,有点慢了。可能昨天做的二分图专题对于这种求最大独立子集为什么建双边不是很明白,这个题虽说用时长了点,但却让我明白了建双边的意义。就这个题叙述一下。

建边操作如下:

void con(int i, int j){
	int now = a[i][j];
	if(a[i-1][j-2]) addedge(now, a[i-1][j-2]);
	if(a[i-2][j-1]) addedge(now, a[i-2][j-1]);
	if(a[i+1][j-2]) addedge(now, a[i+1][j-2]);
	if(a[i+2][j-1]) addedge(now, a[i+2][j-1]);
	if(a[i-1][j+2]) addedge(now, a[i-1][j+2]);
	if(a[i-2][j+1]) addedge(now, a[i-2][j+1]);
	if(a[i+1][j+2]) addedge(now, a[i+1][j+2]);
	if(a[i+2][j+1]) addedge(now, a[i+2][j+1]);
}

即对于每一个点,将其所可以攻击到的点建上单向边,不过当然,now点遍历到现在连向的点后,还会再连回来一条边。
赛时就一直在想能不能只建单向边,

像这样:
void con(int i, int j){
	int now = a[i][j];
	if(a[i-1][j-2]) addedge(now, a[i-1][j-2]);
	if(a[i-2][j-1]) addedge(now, a[i-2][j-1]);
	if(a[i+1][j-2]) addedge(now, a[i+1][j-2]);
	if(a[i+2][j-1]) addedge(now, a[i+2][j-1]);
	// if(a[i-1][j+2]) addedge(now, a[i-1][j+2]);
	// if(a[i-2][j+1]) addedge(now, a[i-2][j+1]);
	// if(a[i+1][j+2]) addedge(now, a[i+1][j+2]);
	// if(a[i+2][j+1]) addedge(now, a[i+2][j+1]);
}
即对于每一个点,我们只连它到下方可攻击到的点:


如图红色为now点可攻击点,但我只连它下方的。
赛时就这么想,可是调半天怎么样也不对,然后思考...突然想明白,
因为这是二分图,我们知道,二分图中点分为两部分,匈牙利算法是把第一部分点连向第二部分,假设我now点为二分图中的第一部分,那么它所攻击的8个点都是第二部分,那么同时这8个点所分别能攻击的64个点也应该是第一部分点。这样的话,按照二分图匈牙利算法建单向边的思路,我需要把这64个点连向上述的那8个点,那么想要这样做的话,把图中的点分为两部分,保证我所有的边都是有第一部分点连向第二部分,这样一来就会很麻烦。
所以呢,我们就有了建双向边的操作。让第一部分点连向第二部分,同时也让第二部分点反向连回第一部分。那么这样我们可以理解为把所有点分为A, B $ 两个部分 $,并建了两个二分图,一个是A作第一部分,其中的点连向B部分中的点,另一个则相反,是B中的点连向A中的点。举个例子:

假定 A 部分有编号为$ 1,3,4 $的三个点, B 部分有$ 2,5,6,7 $四个点,两部分相对应的点建双向边,如图:


我们理解为形成了这样两个二分图,那么跑匈牙利算法的时候等同于又把这两个二分图合二为一,得到了总二分图的最小点覆盖数,且显然两个二分图的最小点覆盖值是相等的,所以我们想要的符合题目的最小点覆盖数即为匈牙利所求的一半,所以最后输出的时候要$ tot-Hun()/2 $

代码如下:

#include<bits/stdc++.h>
using namespace std;

const int N = 4e4 + 10;
const int M = 1e7 + 10;

int n, a[210][210], tot;
bool flag[N];
int match[N]; bool vis[N];

int head[M], to[M], nxt[M], cnt;
void addedge(int x, int y){
	flag[x] = flag[y] = true;
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

bool find(int x){
	for(int i=head[x]; i; i=nxt[i]){
		int y = to[i];
		if(!vis[y]){
			vis[y] = true;
			
			if(!match[y] or find(match[y])){
				match[y] = x;
				return true;	
			}
		}
	}
	return false;
}

int Hun(){
	int ans = 0;
	for(int i=1; i<=tot; i++){
		memset(vis, 0, sizeof(vis));
		if(find(i)) ans++;
	}
	return ans;
}

void con(int i, int j){
	int now = a[i][j];
	if(a[i-1][j-2]) addedge(now, a[i-1][j-2]);
	if(a[i-2][j-1]) addedge(now, a[i-2][j-1]);
	if(a[i+1][j-2]) addedge(now, a[i+1][j-2]);
	if(a[i+2][j-1]) addedge(now, a[i+2][j-1]);
	if(a[i-1][j+2]) addedge(now, a[i-1][j+2]);
	if(a[i-2][j+1]) addedge(now, a[i-2][j+1]);
	if(a[i+1][j+2]) addedge(now, a[i+1][j+2]);
	if(a[i+2][j+1]) addedge(now, a[i+2][j+1]);
}

int main(){
	freopen("attack.in", "r", stdin);
	freopen("attack.out", "w", stdout);
	
	scanf("%d", &n);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			char in; cin>>in;
			if(in == '0') a[i][j] = ++tot;
		}
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			if(a[i][j])	con(i, j);
		}
	}
	
	printf("%d", tot - Hun() / 2);
	
	return 0;
}
  • B. 循环
  • C. 漫步
  • D. 穿越
  • E. 结队

标签:二分,个点,int,5.13,建边,三调,now,部分,addedge
From: https://www.cnblogs.com/YuenYouth/p/18190115

相关文章

  • 5.13 模拟赛题解(没写完)
    T1P4304[TJOI2013]攻击装置快进到HZOI2023超越HZOI2020(人均场切了紫)考虑将棋盘黑白染色成这个样子容易发现相同颜色的点直接一定没有冲突,满足二分图的性质,需要求出最小点覆盖,所以直接按冲突建好双向边,从\(1\)到\(n^2\)节点跑最大匹配即可。设求出的最大匹配为\(......
  • 高一下三调2
    T1攻击装置题目脑瘫了,考场上连边时\((i-1)*n+j\)写成\(i*n+j\),连边直接错位点击查看代码#include<bits/stdc++.h>constintmaxn=4e4+10;usingnamespacestd;intn,head[maxn<<3],nxt[maxn<<4],to[maxn<<4],vis[maxn],match[maxn],tot;inta[500][500],sum,......
  • 云原生周刊:Kubernetes Grafana 看板更新 | 2024.5.13
    开源项目推荐ChartTestingChartTesting是用于测试Helm图表的工具。它旨在用于对拉取请求进行lint和测试。它会自动检测针对目标分支更改的图表。ClusterpediaClusterpedia是一个多集群的百科全书,用于同步、搜索和简单控制多集群资源。Clusterpedia可以与多个集群同......
  • 【比赛】高一下三调2
    T1[TJOI2013]攻击装置题目描述给定一个01矩阵,其中你可以在0的位置放置攻击装置。每一个攻击装置\((x,y)\)都可以按照“日”字攻击其周围的\(8\)个位置\((x-1,y-2)\),\((x-2,y-1)\),\((x+1,y-2)\),\((x+2,y-1)\),\((x-1,y+2)\),\((x-2,y+1)\),\((x+1,y+2)\),\((x+2,y+1)\)。......
  • 力扣1553 2024.5.13
    原题网址:此处为链接个人难度评价:1700分析:虽然不知道为什么贪心不对,但总之贪心不对。数据如此大也难以DP,那么只有搜索了。显然有一眼可得的搜索记忆化:记忆当只剩下k个果时还需要几天。值得一提的是,本代码实际上可能并不是一个正解代码,其可能无法在整数域上保证所有答案正确,但在......
  • 高一下三调|ssy的队列|hash dp|题解
    SSY的队列题目链接解析:考场上看到这个题第一眼是绝望的,毕竟数论咱是一窍不通.但是往下细看了看这个数据范围,N是很小的,就想了想模拟.然而只骗到10分.这个题绩效较高的解法是状压dp,在N<15的范围之内均可薄纱(ppllxx_9G也是成功拿到这70rank1了orz),可得70,但是一到后......
  • 【比赛】高一下三调
    A.李时珍的皮肤衣看不出规律就打表点击查看代码#include<bits/stdc++.h>#definell__int128usingnamespacestd;longlongn;voidp(llx){ if(!x)return; p(x/10); cout<<int(x%10);}llqpow(lla,llb){ llans=1; while(b) { if(b&1)ans=ans*a%n; a=......
  • 2024.5.3【比赛】高一下三调
    为了拓宽自己的英雄池,还是要写一下。分数&排名:理想:会牵挂的叫亲人,回不去的是故乡。现实:神虎一跃,威震天地!A.李时珍的皮肤衣今天输了,明天也要卷土重来。赛后加点卡赛时是不理解的。为啥这次就加点,上次数据范围错了都不把数据范围错的删了给我重测。自己手动模......
  • 三调“快乐”记
    三调了,嗯,浅说一下自己6科T了5科的经历吧数学:被向量背刺了,30分钟写了4.5道大题,当时只有将近半小时,我还没动大题。。。有一道向量,没写,最后半文,3分钟没想出来,所以只有4.5题,倒数第二题第二问本来用初中知识写出来了,却算错了,导致过程分也没了(但方法是对的,我还因为这个在数学课上小......
  • Proxmox VE 8.1 Kernel 6.5.13-5-pve ,无法支持核显 SR-IOV 的问题
    我的之前的博客《利用显卡的SR-IOV虚拟GPU技术,实现一台电脑当七台用》介绍了ProxmoxVE7.x上启用核显虚拟化的方法。并给出了两个脚本,快速启用核显的SR-IOV。该脚本在PromoxVE7.x和8.x都做了测试。近期重新在ProxmoxVE8.1上部署,发现无法正常工作。 经过检查发现......