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;
}

最后

以上就是等待大雁为你收集整理的codeforces1391E Pairs of Pairs的全部内容，希望文章能够帮你解决codeforces1391E Pairs of Pairs所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。