首页 > 其他分享 >P11093 [ROI 2021 Day 2] 树制游戏 题解

P11093 [ROI 2021 Day 2] 树制游戏 题解

时间:2024-09-30 15:12:37浏览次数:7  
标签:ROI 树制 int 题解 tot mxn fa 权值 hd

考虑对于一个解,将每对 \((e_1,e_2)\) 中 \(e_1\) 的终点权值 \(+1\),\(e_2\) 的起点权值 \(-1\),那么最终每个点的权值一定是 \(0\)。

考虑先将每条边的终点权值都 \(+1\),那么现在要做的就是选一些点将其起点和终点的权值都 \(-1\),使得最终每个点的权值为 \(0\),于是边的方向就不重要了。

因为是一颗树,考虑随便取一个点位根,从叶子节点开始贪心选。每次如果当前考虑的点权值 \(>0\),就从它连到父亲的边中随便选出若干个使其权值减到 \(0\),如果 \(<0\) 则无解。记录下选出的边,最终和没选择的边匹配即可。

参考代码:

#include<bits/stdc++.h>
#define mxn 300003
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rept(i,a,b) for(int i=a;i<b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
struct edge{
	int x,y;
}e[mxn];
int n,m,c[mxn];
int tot,hd[mxn],vr[mxn<<1],ed[mxn<<1],nx[mxn<<1];
bool v[mxn],b[mxn];
vector<int>s1[mxn],s2[mxn];
inline void add(int x,int y,int z){
	vr[++tot]=y,ed[tot]=z,nx[tot]=hd[x],hd[x]=tot;
}
void dfs(int x,int fa){
	v[x]=1;
	for(int i=hd[x],y;i;i=nx[i])if(!v[y=vr[i]]){
		dfs(y,x);
	}
	if(c[x]<0||c[x]>2){
		puts("No");
		exit(0);
	}
	if(!c[x])return;
	if(!fa){
		puts("No");
		exit(0);
	}
	vector<int>s;
	for(int i=hd[x],y;i;i=nx[i])if(vr[i]==fa){
		s.pb(ed[i]);
	}
	if(c[x]>s.size()){
		puts("No");
		exit(0);
	}
	rept(i,0,c[x]){
		c[fa]--,b[s[i]]=1;
	}
}
inline void out(int x,int y){
	cout<<e[x].x<<" "<<e[x].y<<" "<<e[y].x<<" "<<e[y].y<<'\n';
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		e[i]={x,y},c[x]++;
		add(x,y,i),add(y,x,i);
	}
	rep(i,1,n)if(!v[i])dfs(i,0);
	rep(i,1,m){
		if(b[i])s2[e[i].y].pb(i);
		else s1[e[i].x].pb(i);
	}
	puts("Yes");
	rep(i,1,n){
		rept(j,0,s1[i].size())out(s2[i][j],s1[i][j]);
	}
	return 0;
}

标签:ROI,树制,int,题解,tot,mxn,fa,权值,hd
From: https://www.cnblogs.com/zifanoi/p/18441884

相关文章

  • CF582D Number of Binominal Coefficients 题解
    CF582DNumberofBinominalCoefficients题解纪念一下自己第一道独立A掉的黑题/CF3300。题目大意给定质数\(p\)和整数\(\alpha,A\),求满足\(0\lek\len\leA\)且\(p^{\alpha}|\binomnk\)的数对\((n,k)\)的个数。Solve首先,我们引入Kummer定理,即:\(p\)在......
  • [ARC061E] すぬけ君の地下鉄旅行 题解
    题目传送门一些废话今天登洛谷的时候发现主页少了一道紫题。???怎么降绿了(建议升蓝)???AND这是蒟蒻的第一篇题解简介很容易地想到,这是一道最短路问题,要求在一个有\(N\)个站点和\(M\)条地铁线路的图中,从站点\(1\)到站点\(N\)的最小花费。每条线路由一个公司运营,乘坐同一......
  • 题解:AT_arc071_c [ARC071E] TrBBnsformBBtion
    首先看到这个奇特的转化方式和常规的数据范围,我们不难想到一定有什么规律。我们可以先想一个转化后的问题:每次询问的两个字符串都可以按照题目要求进行转化,问它们最后能不能转化成同一个字符串。这个问题很简单,我们只需要把两个字符串中的A全都换成BB,最后对\(3\)取模,看看此......
  • Android开发启动页隐私政策弹框
    Android开发启动页隐私政策弹框现在每个app启动页都需要隐私政策弹框了,没有隐私政策弹框,都是不能过平台审核的一、思路:用本地sp存是否同意过,TextView用span连接不同颜色的字符串二、效果图:三、关键代码://联系:893151960objectDialogUtils{funagreementPoli......
  • 【题解】【模拟,字符串】—— [NOIP2011 普及组] 统计单词数
    【题解】【字符串】——[NOIP2011普及组]统计单词数[NOIP2011普及组]统计单词数题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#2提示1.思路解析2.AC代码[NOIP2011普及组]统计单词数通往洛谷的传送门题目描述一般的文本编辑器都有查找......
  • 【题解】【子集枚举】—— PERKET
    【题解】【子集枚举】——PERKET[COCI2008-2009#2]PERKET题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#2输入#3输出#3提示数据规模与约定说明1.思路解析2.AC代码[COCI2008-2009#2]PERKET通往洛谷的传送门题目描述Perket是一种流行......
  • Luogu P5663 CSP-J2019 加工零件 题解 [ 绿 ] [ 同余最短路 ]
    加工零件:非常好的一道图论题。CCF普及组的题目大概也只有图论出的比较巧妙了。题意简述:给你一张无向图,\(q\)次询问,判断是否存在一条从\(a\)到\(1\)且长度为\(L\)的路径。看到\(L\)很大,我们立刻想到了要撇开\(L\)的限制思考问题。首先,对于一条路径,我们肯定能找到从......
  • Hetao P2071 打字游戏 题解 [ 绿 ] [ 最小生成树 ] [ 动态规划 ] [ 编辑距离 ]
    打字游戏:MST套dp好题。首先看这个数据范围,\(O(n^4)\)把每两个字符串之前的编辑距离求一下很显然吧。然后我们观察一下每一个node的性质,发现他要么自己打完,要么从别人那里复制过来。这个就很像一棵树。建完树之后,我们就得到了一个森林。那么题目就转化为,求出一个边权之和......
  • Windows 笔记本 WiFi 功能消失问题解决
    背景说明许多Windows笔记本用户可能会遇到WiFi功能突然消失的问题。虽然网上有各种说法,但实际上,这个问题通常并非由病毒引起。大多数情况下,问题的根源是驱动程序丢失或笔记本静电干扰导致无线网卡无法正常工作。临时联网在解决WiFi问题期间,需要联网,可以尝试以下方法:使......
  • 题解:P11132 【MX-X5-T4】「GFOI Round 1」epitaxy
    1.做法及证明因为\(n\)一定会被包含在某一区间内,所以最后答案肯定是\(n\)的因数。先给出结论:对于\(n\)的因数\(d\),其合法的充要条件为\(d\lem\),所以我们只需要找到第一个小于等于\(m\)的\(d\)即可。接下来我们来证明。下文用\(i'\)表示以第\(i\)位开头的长度......