夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

#1567. [2020提高组十连测day5]藤原千花

2020-09-27 8 min read # 分类讨论 # 比赛题 # 图论

马耀华的比赛题A

太重要了所以这场比赛题我将拆成三篇博客讲述

http://www.zhengruioi.com/problem/1567

线图....QAQ他的点数是按照组合数级别上涨的...

真的来说是图中多少条长为k的路径...

详情请见zjoi 线图那道题

考场时没有判断一个点然后挂掉了QAQ

现在来看是什么我都没有判断就挂掉了....

暴力

k=0,判断是否连通&&是否是每个点度数都为偶数

k=1,你会发现新图中一个点是原图中两个点的度数和-2

那么我们就可以把所有新图中的点度数算出来然后和k=0一样了

然鹅...不严谨的我没有想到这样一个可爱的情况:

1孤零零的站在那里,第一次线图他消失了

所以要特殊判断一个点...

正解:

k>=2k>=2

首先k=0的判据:所有点度数为偶数一定还成立

然后根据k=1我们可以发现:如果所有点度数奇偶性相同也可以

那....所有点度数都为奇数的图能否由线图导出?

你会发现可以,此时只需要所有边两侧的点度数奇偶性不同

那...这样好像可以递归下去,这样的图又能否由线图导出?

然后你又会发现这样的图好像一定是一个二分图...

也就是说我们不存在奇环,至少三元环

再一想,一旦一个图中某个点度数为3就会出现这样一个三元环!就暴毙了

不过好像左边一个点右边两个点的完全二分图也满足这个性质而且能够导出??.....QAQ

但是至少这种情况是特殊的

即,它属于那种能够越变越小的特殊线图:链

每进行一次,链的长度会缩短1

判No判据

存在长度大于k的链

缩不完

存在长度等于k的链,而且有其他剩下的连通块

长度等于k的链会变成一个点

至少剩下两个连通块

存在多个长度等于k的链

QAQ这个其实和上面一样

但是判断起来可不一样啊

不存在点

QAQ这个卡了我一会..

题目定义

存在不止一个连通块

QAQ这个又卡了我一会....

注意有些链可能缩没了

上面都没触犯,结果三个图性质都没满足

这个最好判断qwq

判Yes判据

最后只剩下存在长为k的链

一个点也行

满足一个图性质

显然

于是我们大胆实践

就用2h完成了这道题!!!

附赠第一发AC的代码/se

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 7;
int n, m, k;
struct rec {
	int x, y;
} e[MAXN];
int f[MAXN], in[MAXN];
inline int getf(int x) {
	return f[x] == x ? x : f[x] = getf(f[x]);
}

inline void pd1() {
	for(int i = 1; i <= n; ++i)f[i] = i;
	for(int i = 1; i <= m; ++i) {
		in[e[i].x]++;
		in[e[i].y]++;
		f[getf(e[i].x)] = getf(e[i].y);
	}
	for(int i = 1; i <= n; ++i) {
		if(getf(i) != getf(1))return (void)puts("No");
	}
	for(int i = 1; i <= n; ++i) {
		//		printf("%d %d?\n",i,in[i]);
		if(in[i] & 1)return (void)puts("No");
	}
	return (void)puts("Yes");
}//k equal 0

//one node
inline void pd2() {
	static int siz[MAXN];
	for(int i = 1; i <= n; ++i)f[i] = i;
	for(int i = 1; i <= m; ++i) {
		in[e[i].x]++;
		in[e[i].y]++;
		f[getf(e[i].x)] = getf(e[i].y);
	}
	for(int i = 1; i <= n; ++i) {
		siz[getf(i)]++;
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i) {
		if(siz[i] > 1) {
			++cnt;
		}
	}
	if(cnt > 1)return (void)puts("No");
	if(cnt == 0)return (void)puts("No");
	for(int i = 1; i <= m; ++i) {
		if((in[e[i].x] + in[e[i].y]) & 1)return (void)puts("No");
	}
	puts("Yes");
	return ;
}

int home[MAXN], nxt[MAXN], to[MAXN], ccnt;

inline void ct(int x, int y) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
}

int flg, mx;
int dep[MAXN], vis[MAXN];
//du shu is 2
//with out circle
//lian tong kuai!
inline void dfs(int u, int F) {
	if(!flg)return ;
	vis[u] = 1;
	mx = max(mx, dep[u]);
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		//		printf("%d-> %d %d in? %d\n",u,v,vis[v],in[v]);
		if(vis[v])flg = 0;
		else {
			if(in[v] != 1 && in[v] != 2)flg = 0;
			dep[v] = dep[u] + 1;
			dfs(v, u);
		}
	}
}

int visp[MAXN];
inline void dfs2(int u, int F) {
	visp[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		if(to[i] == F)continue;
		dfs2(to[i], u);
	}
}

//if k > maxlen lian ,can1
//if graph is jishu or graph is jioutu,can2
inline void pd3() {
	for(int i = 1; i <= n; ++i)f[i] = i;
	for(int i = 1; i <= m; ++i) {
		in[e[i].x]++;
		in[e[i].y]++;
		f[getf(e[i].x)] = getf(e[i].y);
		ct(e[i].x, e[i].y);
		ct(e[i].y, e[i].x);
	}
	int cnt = 0;
	int flg2 = 1;
	for(int i = 1; i <= n; ++i) {
		if(in[i] == 0) {
			visp[i] = 1;
			continue;
		}
		if(!vis[getf(i)] && in[i] == 1) { //is himself
			// printf("%d?%d\n", i, in[i]);
			flg = 1;
			mx = 0;
			dfs(i, 0);
			if(!flg) continue;
			if(mx > k)return (void)puts("No");
			else if(mx == k) {
				if(!flg2)return (void)puts("No");
				flg2 = 0; //cunzai!
				dfs2(i, 0);
			} else dfs2(i, 0);
		}
	}
	// puts("qwq");
	for(int i = 1; i <= n; ++i) {
		if(!visp[i] && i == getf(i)) {
			cnt++;
			//				printf("%d \n",i);
		}
	}
	// printf("%d %d\n", cnt, flg2);

	if(flg2 && cnt == 0)return (void)puts("No");
	// printf("%d %d\n", flg2, cnt);
	if(!flg2 && cnt == 0) {
		// if(n == 890000 && m == 269874)puts("qwq");
		return (void)puts("Yes");
	} else if(!flg2) {//too....
		return (void)puts("No");
	}
	if(cnt > 1)return (void)puts("No");
	flg = 1;
	for(int i = 1; i <= n; ++i) {
		if(visp[i])continue;
		if(!(in[i] & 1)) {
			flg = 0;
			break;
		}
	}
	if(flg)return (void)puts("Yes");
	flg = 1;
	for(int i = 1; i <= n; ++i) {
		if(visp[i])continue;
		if((in[i] & 1)) {
			flg = 0;
			break;
		}
	}
	if(flg) {
		// if(n == 890000 && m == 269874)puts("QAq");
		return (void)puts("Yes");
	}
	flg = 1;
	for(int i = 1; i <= m; ++i) {
		if(visp[e[i].x] || visp[e[i].y])continue;
		if(!((in[e[i].x] & 1) ^ (in[e[i].y] & 1))) {
			flg = 0;
			break;
		}
	}
	if(flg) {
		// if(n == 890000 && m == 269874)puts("qAq");
		return (void)puts("Yes");
	}
	return (void)puts("No");
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &e[i].x, &e[i].y);
	}
	if(k == 0) {
		return pd1(), 0;
	}//qaq
	if(k == 1) {
		return pd2(), 0;
	}//qwq
	pd3();//QAQAQAQ
	return 0;
}

/*

12 10 2
1 2
3 4

5 6
6 7
7 8
8 5

9 10
10 11
11 12
12 9

*/
Powered by Gridea RSS