首页 > 其他分享 >【题解】洛谷P8346:最澄澈的空与海

【题解】洛谷P8346:最澄澈的空与海

时间:2024-11-12 16:08:34浏览次数:1  
标签:洛谷 澄澈 int 题解 P8346 vv

【题解】洛谷P8346:最澄澈的空与海

猜结论题,本身其实很简单,在纸上画个差不多就能想出来,我一开始想二分图最大匹配,但是还是太大了,不可以。

当一个二分图有且仅有一种解时,必定有节点的入度为 \(1\)。

我们想到有多种匹配的情况,可以想到如果这是一个环的情况,一个左边的点将他右边的点都标记后另一个点再遍历出边后没有可以连的右点了就说明有环的,我们可以用拓扑保证复杂度与正确性,具体怎么做我省略,具体看代码。

image

#include <bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1 
#define re register 
const int N=2e6+10;
const int mod=1000;
using namespace std;

int t;
int n,m;

vector<int> v[N];
int du[N];
int vis[N];
int ans=0;
queue<int> q;
int solve(){
	ans=0;
	cin>>n>>m;
	
	for(int i=1;i<=m;i++){
		int u,vv;
		cin>>u>>vv;
		v[u].push_back(vv+n);
		v[vv+n].push_back(u);
		du[u]++;
	}
	
	for(int i=1;i<=n;i++){
		if(!du[i]){
			return 0;
		}
		if(du[i]==1){
			q.push(i);
			ans++;
		}
	}
	
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i];
			if(vis[y]){
				continue;
			}
			vis[y]=1;
			
			for(int k=0;k<v[y].size();k++){
				int yy=v[y][k];
				if((--du[yy])==1){
					q.push(yy);
					ans++;
				}
			}
		}
	} 
	return ans==n;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 
	cin>>t;
	while(t--){
		if(solve()){
			cout<<"Renko\n";
		}
		else{
			cout<<"Merry\n";
		} 
		while(!q.empty()){
			q.pop();
		}
		for(int i=1;i<=2*n;i++){
			v[i].clear();
			du[i]=0;
			vis[i]=0;
		}
	} 
	return 0;
}

标签:洛谷,澄澈,int,题解,P8346,vv
From: https://www.cnblogs.com/sadlin/p/18542140

相关文章

  • MX-S5 T1~T2 题解
    MX-S5题解A.王国边缘题目链接见到循环结构,先把下标转成从\(0\)开始,以方便用同余描述位置。倍增。用二元组来表示位置:\((u,v)\)表示第\(u\)个循环节的第\(v\)个位置。设\(f(i,j)\)表示从位置\((0,i)\)开始跳\(2^j\)次以后的位置。假设已经可以初始化\(f(i,......
  • CF 705 题解
    CF705题解AHulk模拟即可.BSpiderMan打sg表可以发现,奇数个球先手必败(sg=0),偶数先手必胜(sg=1).多个组合只要把sg值异或起来就好.CThor暴力模拟就可以了,用队列模拟.DAntMan结论:按照编号由小到大加入链表,每次尽量让答案最小贪心就是对的.若原来是......
  • 题解:洛谷 P5180 【模板】支配树
    在图论模拟赛被T4的有向图必经点硬控了\(10^9+7s\),写篇题解纪念一下。其实,求有向图的必经点,通法就是支配树。一些定义:支配点:在确定起点\(S\)的情况下,对于一个点\(k\),若存在\(x\),使得删除\(x\)以及与\(x\)连接的边后,\(x\)与\(k\),不再强连通,那么就称\(k\)为\(x......
  • 【题解】洛谷P3118: Moovie Mooving G
    洛谷P3118:MoovieMoovingG看到数据范围考虑状压,题目要求看的电影最少那就维护时间最大,我们设\(f_{i}\)为\(i\)状态最多可以看多久的电影,对于不在集合的点我们枚举转移。我们每个开始时间都对应一个截至时间,问能加入这个点,每个点花费时间是固定的,我们又要不间断所以我们找......
  • CF785D 题解
    CF题目luogu题目题解似乎清一色是同一个做法,这里给一个容斥的做法。首先枚举一个位置\(i\),设\([1,i]\)的左括号个数为\(p\),\([i+1,n]\)的右括号个数为\(q\),那么以\(i\)这个位置为分界点的合法括号数有\(\sum_{i=1}^{\min(p,q)}C_p^iC_q^i\)个。通过范德蒙德卷......
  • CF 1325 题解
    CF1325题解AEhAbAnDgCd有\(\gcd(1,x)=1,\text{lcm}(1,x)=x\),因此输出\(1x\).BCopyCopyCopyCopyCopy要求严格上升子序列,那么答案的上界当然是去重后的元素个数.能否取到上界呢?当然可以,每一段内选一个你想要的就可以了.CEhabandPath-eticMEXs发现\(0,......
  • 历年CSP-J初赛真题解析 | 2020年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客(质因数分解)给出正整数n,请输出将n质因数分解的结果,结果从小到大输出。例如:输入n=120,程序应该输出22235,表示120=2×2×2×......
  • 洛谷P5744
    P5744【深基7.习9】培训-洛谷|计算机科学教育新生态【深基7.习9】培训题目描述某培训机构的学员有如下信息:-姓名(字符串)-年龄(周岁,整数)-去年NOIP成绩(整数,且保证是5 的倍数)经过为期一年的培训,所有同学的成绩都有所提高,提升了20%(当然NOIP满分是600 分,不能......
  • 洛谷P1618
    P1618三连击(升级版)-洛谷|计算机科学教育新生态三连击(升级版)题目描述将1,2,...9共9个数分成三组,分别组成三个三位数,且使这三个三位数的比例是A:B:C,试求出所有满足条件的三个三位数,若无解,输出`No!!!`。//感谢黄小U饮品完善题意输入格式三个数,A,B,C。输出格式......
  • 博弈论(零和博弈)英文版题解
    翻译:   假设我们有一个两人零和游戏,每个玩家有两种行动,行收益矩阵如下:计算行和列玩家的最小最大最优策略以及游戏的价值。      X     YA    a11   a12B    a21   a22选项:1.行玩家:第一种行动的概率为三分之二,第......