2019 ICPC Asia Xuzhou Regional J. Loli, Yen-Jen, and a graph problem(欧拉回路+构造)
题目
输入一个n(n<=1e3)，代表n个点的完全无向图，
你需要输出n-1行，分别代表长度为1,2，...，n-1的链上经过的点，
使得每条链在原图中都是连续的，且任意两条链之间没有交边
思路来源
题解
①n是奇数，欧拉回路，注意弧优化
②n是偶数，考虑长为n-2和n-1的两条链如何构造，
令a=n-1，b=n，使a和b交替穿插在[1,n-2]个点里，并最后回到b，
最终构成a-1-b-2-...-b-(n-2)-a-b的一个长为2*n-3的链，然后拆成n-2和n-1的两条链
然后删掉a和b两个点，递归解决n-2的子问题即可
代码
#include
#include
#include
#include
#include
#include
using namespace std;
#define pb push_back
typedef pair P;
const int N=1e3+10,M=1e6+10;
vectore[N];
bool vis[M],used[N];
int now[N],ans[M],cnt,c;
int op,n,m,u,v;
void dfs(int u){used[u]=1;while(now[u]ans;int a=n-1,b=n;for(int i=1;i<=n-2;i+=2){ans.pb(a);ans.pb(i);ans.pb(b);ans.pb(i+1);}ans.pb(a);ans.pb(b);int sz=ans.size(),mid=sz/2-1; for(int i=0;i<=mid;++i){printf("%d%c",ans[i]," \n"[i==mid]);}for(int i=mid;i<=sz-1;++i){printf("%d%c",ans[i]," \n"[i==sz-1]);}
}
int main(){scanf("%d",&n);n&1?odd(n):even(n);return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！