在线阅读小说网站怎么建设,有网站吗给一个,微信营销微网站建设,下载中国建设银行官网站前言
走远了走远了… 一直在想翻转一条链的奇偶性怎么做#xff0c;但没有意识到最后一定是个菊花。
解析
一状态就是走一个欧拉回路#xff0c;合法性更容易刻画#xff0c;所以考虑反过来想#xff0c;如何用状态二的走法删去一些边#xff0c;使得剩下的图存在欧拉路…前言
走远了走远了… 一直在想翻转一条链的奇偶性怎么做但没有意识到最后一定是个菊花。
解析
一状态就是走一个欧拉回路合法性更容易刻画所以考虑反过来想如何用状态二的走法删去一些边使得剩下的图存在欧拉路径。
那么状态二的走法是啥勒 由于最后必须把边删空感性理解一下状态二走出的图必然是一个菊花。
所以直接对每个点作为菊花中心讨论一下就行了。由于可能剩下的图不联通还需要暴力跑欧拉路判合法。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(ok\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N6050;
const int mod998244353;
ll n,m,k;
inline ll ksm(ll x,ll k,int mod){ll res(1);while(k){if(k1) resx*res%mod;xx*x%mod;k1;}return res;
}struct node{int to,nxt,id;
}p[N1];
int fi[N],cur[N],ecnt;
inline void addline(int x,int y,int id){p[ecnt](node){y,fi[x],id};fi[x]ecnt;return;
}
int zhan[N],top;
int du[N];
bool vis[N];
void dfs(int x){//debug(x%d\n,x);for(int icur[x];~i;icur[x]){cur[x]p[i].nxt;if(vis[p[i].id]) continue;vis[p[i].id]1;dfs(p[i].to);}zhan[top]x;
}
void init(){for(int i1;in;i) cur[i]fi[i];memset(vis,0,sizeof(vis));top0;
}int cnt,rt;
inline void calc(int x,int ban,int e){init();--e;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!(du[to]1)) continue;if(toban) continue;vis[p[i].id]1; }dfs(x);if(top-1em){printf(%d\n,top12*e);for(int i1;itop;i) printf(%d ,zhan[i]);printf(-1 );for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(toban) continue;if(du[to]1) printf(%d %d ,to,x);}exit(0);}
}
inline void work(int x){int numdu[x]1,e(0);for(int ifi[x];~i;ip[i].nxt){int top[i].to;num(du[to]1);e(du[to]1);}if(numcnt){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(du[to]1) calc(x,to,e);}}if(numcnt-1){init();//ok;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(du[to]1) vis[p[i].id]1;}dfs(x);if(top-1em){//printf(top%d e%d\n,top,e);printf(%d\n,top12*e);for(int i1;itop;i) printf(%d ,zhan[i]);printf(-1 );for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(du[to]1) printf(%d %d ,to,x);}exit(0);}}return;
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifmemset(fi,-1,sizeof(fi));ecnt-1;cnt-1;nread();mread();for(int i1;im;i){int xread(),yread();addline(x,y,i);addline(y,x,i);du[x];du[y];}cnt0,rt1;for(int i1;in;i){if(du[i]1){cnt;rti;}}if(cnt2){init();dfs(rt);printf(%d\n,top);while(top) printf(%d ,zhan[top--]);return 0;}for(int i1;in;i) work(i);puts(0);return 0;
}
/*
*/
