codeforces1391E Pairs of Pairs

95 阅读 0 评论 63 点赞

我是靠谱客的博主等待大雁，这篇文章主要介绍codeforces1391E Pairs of Pairs，现在分享给大家，希望可以做个参考。

https://codeforces.com/contest/1391/problem/E

本来以为写完D题下班了，结果队友给我讲课E题卧槽这不是标准dfs树题？现场没写完，艹，血亏100分，5月份的时候补了两道这种dfs树的题，就是建一棵dfs树出来，要么满足一种情况，要么满足另一种情况。

这题就是建dfs树，如果有深度>=(n+1)/2，那么直接输出，否则则每一层分别匹配，由于深度<(n+1)/2，每层最多浪费一个，那么至少还剩(n+1)/2个点可以匹配上

复制代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;

const int maxl=5e5+10;

int n,m,cas,k,cnt,tot,ans,mx,ed;
int a[maxl],frm[maxl],dis[maxl];
int pth[maxl],son[maxl],len[maxl];
vector<int> e[maxl],b[maxl];
bool in[maxl],vis[maxl];
typedef pair<int,int> p;
p pr[maxl]; 
set<p> s;

inline void prework()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		e[i].clear(),b[i].clear();
		frm[i]=son[i]=0;
	}
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
}

inline void dfs(int u)
{
	b[dis[u]].push_back(u);
	vis[u]=true;
	for(int v:e[u])
	{
		if(vis[v]) continue;
		dis[v]=dis[u]+1;frm[v]=u;
		if(dis[v]>mx)
			ed=v,mx=dis[v];
		dfs(v);
	}
}

inline void mainwork()
{
	if(n==2)
	{
		ans=0;cnt=1;pth[1]=1;
		return;
	}
	for(int i=1;i<=n;i++) vis[i]=false;
	int u=1,v;mx=0;
	dis[1]=1;
	dfs(1);
	if(mx>=(n+1)/2)
	{
		ans=0;cnt=0;
		while(ed!=1)
			pth[++cnt]=ed,ed=frm[ed];
		pth[++cnt]=1;
		return;
	}
	ans=0;
	for(int i=2;i<=mx;i++)
	{
		len[i]=b[i].size();
		for(int j=0;j+1<len[i];j+=2)
			pr[++ans]={b[i][j],b[i][j+1]};
	}
}

inline void print()
{
	if(!ans)
	{
		puts("PATH");
		printf("%dn",cnt); 
		for(int i=1;i<=cnt;i++)
			printf("%d%c",pth[i]," n"[i==cnt]);
	}
	else
	{
		puts("PAIRING");
		printf("%dn",ans);
		for(int i=1;i<=ans;i++)
			printf("%d %dn",pr[i].first,pr[i].second);
	}
}

int main()
{
	int t=1;
	scanf("%d",&t);
	for(cas=1;cas<=t;cas++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;

const int maxl=5e5+10;

int n,m,cas,k,cnt,tot,ans,mx,ed;
int a[maxl],frm[maxl],dis[maxl];
int pth[maxl],son[maxl],len[maxl];
vector<int> e[maxl],b[maxl];
bool in[maxl],vis[maxl];
typedef pair<int,int> p;
p pr[maxl]; 
set<p> s;

inline void prework()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		e[i].clear(),b[i].clear();
		frm[i]=son[i]=0;
	}
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
} 

inline void dfs(int u)
{
	b[dis[u]].push_back(u);
	vis[u]=true;
	for(int v:e[u])
	{
		if(vis[v]) continue;
		dis[v]=dis[u]+1;frm[v]=u;
		if(dis[v]>mx)
			ed=v,mx=dis[v];
		dfs(v);
	}
}

inline void mainwork()
{
	if(n==2)
	{
		ans=0;cnt=1;pth[1]=1;
		return;
	}
	for(int i=1;i<=n;i++) vis[i]=false;
	int u=1,v;mx=0;
	dis[1]=1;
	dfs(1);
	if(mx>=(n+1)/2)
	{
		ans=0;cnt=0;
		while(ed!=1)
			pth[++cnt]=ed,ed=frm[ed];
		pth[++cnt]=1;
		return;
	}
	ans=0;
	for(int i=2;i<=mx;i++)
	{
		len[i]=b[i].size();
		for(int j=0;j+1<len[i];j+=2)
			pr[++ans]={b[i][j],b[i][j+1]};
	}
}

inline void print()
{
	if(!ans)
	{
		puts("PATH");
		printf("%dn",cnt); 
		for(int i=1;i<=cnt;i++)
			printf("%d%c",pth[i]," n"[i==cnt]);
	}
	else
	{
		puts("PAIRING");
		printf("%dn",ans);
		for(int i=1;i<=ans;i++)
			printf("%d %dn",pr[i].first,pr[i].second);
	}
}

int main()
{
	int t=1;
	scanf("%d",&t);
	for(cas=1;cas<=t;cas++)
	{
		prework();
		mainwork();
		print();
	}
	return 0;
}