CF1152E Neko and Flashback——欧拉路径

Bertha 。 2021-12-02 00:14 212阅读 0赞

[RemoteJudge][]  
第一次见到欧拉路径的题  
注意到\\(b\\)和\\(c\\)的构造方法很特殊，即对于一个位置（经过\\(p\\)作用后）\\(i\\)，若两个数分别为\\(b\_i\\)和\\(c\_i\\)，那么在\\(a\\)中\\(b\_i\\)与\\(c\_i\\)相邻  
其实\\(p\\)并没有什么用  
从每一个\\(b\_i\\)向\\(c\_i\\)连边，那么问题转化为是否存在一条长度为\\(n\\)的欧拉路径，直接\\(dfs\\)就行了  
几个\\(-1\\)的情况：  
1.存在\\(i\\)，使得\\(b\_i> c\_i\\)  
2.不存在欧拉路径  
3.求出来的路径长度不为\\(n\\)  
上代码：

// // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \\| |// `. // / \\||| : |||// \ // / _||||| -:- |||||- \ // | | \\\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // 佛祖保佑 全是BUG #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <cmath> #include <ctime> #include <queue> #include <map> #include <set> using namespace std; #define ull unsigned long long #define pii pair<int, int> #define uint unsigned int #define mii map<int, int> #define lbd lower_bound #define ubd upper_bound #define ll long long #define mp make_pair #define pb push_back #define re register #define il inline #define N 100000 int n, m, tot; mii id; multiset<int> to[2*N+5]; int ans[10*N+5], tp, d[2*N+5], cnt, p[10*N+5]; int b[N+5], c[N+5], val[2*N+5]; void dfs(int u) { for(auto i = to[u].begin(); i != to[u].end(); i = to[u].begin()) { auto v = *i; to[u].erase(i), to[v].erase(to[v].lbd(u)); dfs(v); } ans[++tp] = u; } int main() { scanf("%d", &n); for(int i = 1; i < n; ++i) { scanf("%d", &b[i]); if(!id.count(b[i])) id[b[i]] = ++tot, val[tot] = b[i]; } for(int i = 1; i < n; ++i) { scanf("%d", &c[i]); if(b[i] > c[i]) { printf("-1\n"); return 0; } if(!id.count(c[i])) id[c[i]] = ++tot, val[tot] = c[i]; to[id[c[i]]].insert(id[b[i]]), to[id[b[i]]].insert(id[c[i]]); d[id[c[i]]]++, d[id[b[i]]]++; } for(int i = 1; i <= tot; ++i) if(d[i]&1) p[++cnt] = i; if(cnt != 0 && cnt != 2) printf("-1\n"); else { if(cnt == 0) dfs(1); else dfs(p[1]); if(tp != n) printf("-1\n"); else { while(tp) printf("%d ", val[ans[tp--]]); printf("\n"); } } return 0; }

转载于:https://www.cnblogs.com/dummyummy/p/10770876.html

[RemoteJudge]: https://www.luogu.org/problemnew/show/CF1152E