您的位置: 首页  >  IT文章  >  【欧拉回路专题】解题报告

【欧拉回路专题】解题报告

分类: IT文章 • 2024-01-01 09:23:24

HDU 1878 欧拉回路

　　最简单的欧拉回路了，如果结点的出度入度之和不是2的倍数，那么就不是欧拉回路。注意要判断图是否连通。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int g[MAXN];
int n, m;
int f[MAXN];
int h[MAXN];
int r[MAXN];
vector<int> vs[MAXN];

void init()
{
    clr(g); clr(h);
    rep(i,0,n)
        f[i] = i, vs[i].clear();
}

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int a, int b)
{
    int x = find(a);
    int y = find(b);
    f[x] = y;
}

int main()
{
    int a, b;
    while(RII(n, m) != EOF)
    {
        init();
        rep(i,1,m)
        {
            RII(a, b);
            g[a]++; g[b]++;
            union_set(a, b);
        }
        rep(i,1,n) find(i);
        int k = 0;
        rep(i,1,n)
        {
            if(!h[f[i]])
            {
                h[f[i]] = ++k;
                r[k] = f[i];
                vs[k].PB(i);
            }
            else
                vs[h[f[i]]].PB(i);
        }
        int cnt = 0;
        rep(i,1,k)
        {
            int tmp = 0;
            int num = vs[i].size();
            rep(j,0,num-1)
                tmp += g[vs[i][j]]&1;
            
            if(tmp == 0 && num != 1) cnt++;
            else cnt += tmp / 2;
        }
        printf("%d
", cnt);
    }
    return 0;
}
View Code

HDU 3018 Ant Trip

　　对于本题的图，可能存在多个连通分量，那么对于每个连通分量，如果不存在奇数度的点，那么该分量是构成欧拉回路，只需要一个队伍就能走遍；如果奇数度的点有n个，那么需要n/2个队伍才能走遍，画一下图就很明了了。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int g[MAXN];
int n, m;
int f[MAXN];
int h[MAXN];
int r[MAXN];
vector<int> vs[MAXN];

void init()
{
    clr(g); clr(h);
    rep(i,0,n)
        f[i] = i, vs[i].clear();
}

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int a, int b)
{
    int x = find(a);
    int y = find(b);
    f[x] = y;
}

int main()
{
    int a, b;
    while(RII(n, m) != EOF)
    {
        init();
        rep(i,1,m)
        {
            RII(a, b);
            g[a]++; g[b]++;
            union_set(a, b);
        }
        rep(i,1,n) find(i);
        int k = 0;
        rep(i,1,n)
        {
            if(!h[f[i]])
            {
                h[f[i]] = ++k;
                r[k] = f[i];
                vs[k].PB(i);
            }
            else
                vs[h[f[i]]].PB(i);
        }
        int cnt = 0;
        rep(i,1,k)
        {
            int tmp = 0;
            int num = vs[i].size();
            rep(j,0,num-1)
                tmp += g[vs[i][j]]&1;
            
            if(tmp == 0 && num != 1) cnt++;
            else cnt += tmp / 2;
        }
        printf("%d
", cnt);
    }
    return 0;
}
View Code

HDU 1116 Play on Words

　　对每个单词的首尾字母连边，看是否能构成欧拉通路或者欧拉回路，有两种做法：

　　1. 分别判断是否是欧拉通路和欧拉回路。

　　2. 如果可以构成欧拉回路，那答案是肯定的；否则设法将欧拉通路变为欧拉回路（找出欧拉通路首尾点，额外添加一条边构成欧拉回路），再计算一次，看是否能构成欧拉回路。

　　当然，两种做法都要先判断连通性，谨记欧拉回路是基于连通图的。

　　我用的第一种方法。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define    rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define    per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define    inf         0x3f3f3f3f
#define    eps         1e-6
#define    MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int n, m, f[MAXN], g[MAXN];
char s[MAXM];
bool h[MAXN];
int v[MAXN]; // 记录出现的字母

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int u, int v)
{
    int x = find(u);
    int y = find(v);
    f[x] = y;
}

int main()
{
    int t, a, b;
    RI(t);
    while(t--)
    {
        RI(n);
        clr(g); clr(h);
        rep(i,0,26) f[i] = i;
        int k = 0;
        rep(i,1,n)
        {
            scanf("%s", s);
            a = s[0] - 'a';
            b = s[strlen(s)-1] - 'a';
            g[a]++; g[b]--;
            union_set(a, b);
            if(!h[a])
                v[++k] = a, h[a] = true;
            if(!h[b])
                v[++k] = b, h[b] = true;
        }
        bool flag = true;
        rep(i,1,k-1)
            if(find(v[i]) != find(v[i+1]))
                flag = false;
        int cnt1 = 0; // 记录出现度为1的节点的个数，即起点
        int cnt2 = 0; // 记录出现度为-1的节点的个数，即终点
        rep(i,0,25)
        {
            if(abs(g[i]) > 1)
            {
                flag = false;
                break;
            }
            if(g[i] == 1)
                cnt1++;
            if(g[i] == -1)
                cnt2++;
        }
        if(!flag || cnt1 > 1 || cnt2 > 1)
            printf("The door cannot be opened.
");
        else
            printf("Ordering is possible.
");  
    }
    return 0;
}
View Code

HDU 2894 DeBruijin

　　磁鼓欧拉回路。

　　举个具体例子吧，比如k=3的情况，设当前有一个结点为“010”，那么根据欧拉回路一笔画的想法，和该结点相连的结点应该是“100”和“101”，也就是原结点向左移一位然后最低位可以是“0”或“1”，根据这个思路，从“000”开始，先访问下一个低位为0的结点，在访问为1的结点，就能保证所得答案为最小，利用栈保存过程中遇到的可行结点，最后倒序输出栈即可。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int n;
bool vis[MAXN];
int stk[MAXN], top;

void dfs(int u)
{
    rep(i,0,1)
    {
        int t = ((u<<1)&((1<<n)-1)) + i;
        if(!vis[t])
        {
            vis[t] = true;
            dfs(t);
            stk[top++] = i;
        }
    }
}

void init()
{
    clr(vis);
    top = 0;
}

int main()
{
    while(RI(n) != EOF)
    {
        init();
        printf("%d ", 1 << n);
        dfs(0);
        rep(i,1,n-1)
            printf("0");
        per(i,top-1,n-1)
            printf("%d", stk[i]);
        putchar('
');
    }
    return 0;
}
View Code

HDU 1956 Sightseeing tour

　　混合欧拉+最大流。

　　对于双向边，任意定向（至于为什么可以这样做，搞清楚求后面求最大流的过程后应该会很清楚了）。双向边用于建图（单向边不用于建图）。

　　然后是统计结点的度，计算差值 x = outg[i] - ing[i]，如果x>0，源点到 i 连一条边，权值为x/2，也就是说我们需要把与结点 i 相连的x/2条边反向，那么outg[i] == ing[i]；同理，如果x<0，连边 i 到汇点，权值为-x/2。最后，如果求出的最大流等于需要反向的总边数，也就是说该流网络满流，说明我们可以成功把想要反向的所有边都反向，那么就能符合题目要求了。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;
struct Edge
{
    int v, w, next;
}E[MAXM];

int n, m;
int head[MAXN], NE;

int ing[MAXN], outg[MAXN]; 

int d[MAXN];  
bool vis[MAXN];   
int q[MAXN];     

void add_edge (int u, int v, int w)
{
    E[NE].v = v;   
    E[NE].w = w;
    E[NE].next = head[u];
    head[u] = NE++;
    
    E[NE].v = u;   
    E[NE].w = 0;
    E[NE].next = head[v];
    head[v] = NE++;
}

int BFS (int s, int t)
{
    memset(d, 0x7f, sizeof(d));
    memset(vis, false, sizeof(vis));

    int qn = 0 ;
    d[s] = 0 ;
    vis[s] = true ;
    q[qn++] = s ;

    for (int qf = 0; qf < qn; ++qf )
    {
        int u = q[qf];
        for (int i = head[u]; i != -1; i = E[i].next)
        {
            int v = E[i].v;
            if (E[i].w > 0 && !vis[v])
            {
                d[v] = d[u] + 1 ;
                vis[v] = true ;
                q[qn++] = v ;
                if (v == t) return d[t];
            }
        }
    }
    return MAXN;
}

int DFS (int u, int df, int s, int t)
{
    if (u == t) return df ;

    if (vis[u]) return 0 ;
    vis[u] = true;

    for (int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].v ;
        if (E[i].w > 0 && d[u] + 1 == d[v])
        {
            int f = DFS (v, min(df, E[i].w), s , t);
            if ( f )
            {
                E[i].w -= f ;
                E[i ^ 1].w += f ;
                return f ;
            }
        }
    }
    return 0 ;
}

int dinic (int s, int t)
{
    int flow = 0 ;
    while (BFS (s, t) < MAXN)
        while ( true )
        {
            clr(vis);
            int f = DFS (s, inf, s, t);
            if( !f ) break;
            flow += f ;
        }
    return flow;
}

void init()
{
    clr(ing); clr(outg);
    NE = 0;
    memset(head, -1, sizeof head);
}

int main()
{
    int a, b, c, t;
    RI(t);
    while(t--)
    {
        RII(n, m);
        init();
        rep(i,1,m)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(a == b) continue;
            outg[a]++; ing[b] ++;
            if(!c) add_edge(a, b, 1);
        }
        bool flag = true;
        rep(i,1,n)
        {
            int tot = ing[i] + outg[i];
            if(tot & 1) flag = false;
            if(!flag) break;
        }
        if(!flag)
        {
            puts("impossible");
            continue;
        }
        int sum = 0;
        rep(i,1,n)
        {
            int x = outg[i] - ing[i];
            if(x > 0)
            {
                add_edge(0, i, x/2);
                sum += x/2;
            }
            if(x < 0)
                add_edge(i, n+1, -x/2);
        }
        if(dinic(0, n+1) == sum)
            puts("possible");
        else
            puts("impossible");
    }
    return 0;
}
View Code

HDU 3472 HS BDC

　　此题和上一题类似，混和欧拉+最大流，不再赘述。、

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

struct Edge
{
    int v, w, next;
}E[MAXM]; 

int n, m;
int head[MAXN], NE;

char s[MAXN];
int ing[MAXN], outg[MAXN]; 
int f[MAXN];
vector<int> vs;
bool h[MAXN];

int d[MAXN];      
bool vis[MAXN]; 
int q[MAXN];     

void add_edge (int u, int v, int w)
{
    E[NE].v = v;   
    E[NE].w = w;
    E[NE].next = head[u];
    head[u] = NE++;
    
    E[NE].v = u;   
    E[NE].w = 0;
    E[NE].next = head[v];
    head[v] = NE++;
}

int BFS (int s, int t)
{
    memset(d, 0x7f, sizeof(d));
    memset(vis, false, sizeof(vis));

    int qn = 0 ;
    d[s] = 0 ;
    vis[s] = true ;
    q[qn++] = s ;

    for (int qf = 0; qf < qn; ++qf )
    {
        int u = q[qf];
        for (int i = head[u]; i != -1; i = E[i].next)
        {
            int v = E[i].v;
            if (E[i].w > 0 && !vis[v])
            {
                d[v] = d[u] + 1 ;
                vis[v] = true ;
                q[qn++] = v ;
                if (v == t) return d[t];
            }
        }
    }
    return MAXN;
}

int DFS (int u, int df, int s, int t)
{
    if (u == t) return df ;

    if (vis[u]) return 0 ;
    vis[u] = true;

    for (int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].v ;
        if (E[i].w > 0 && d[u] + 1 == d[v])
        {
            int f = DFS (v, min(df, E[i].w), s , t);
            if ( f )
            {
                E[i].w -= f ;
                E[i ^ 1].w += f ;
                return f ;
            }
        }
    }
    return 0 ;
}

int dinic (int s, int t)
{
    int flow = 0 ;
    while (BFS (s, t) < MAXN)
        while ( true )
        {
            clr(vis);
            int f = DFS (s, inf, s, t);
            if( !f ) break;
            flow += f ;
        }
    return flow;
}

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int u, int v)
{
    int x = find(u);
    int y = find(v);
    f[x] = y;
}

void init()
{
    clr(ing); clr(h);
    clr(outg);
    vs.clear();
    NE = 0;
    memset(head, -1, sizeof head);
    rep(i,0,26) f[i] = i;
}

int main()
{
    int t, a, b, c;
    RI(t);
    rep(cas,1,t)
    {
        RI(n);
        init();
        rep(i,1,n)
        {
            scanf("%s%d", s, &c);
            a = s[0] - 'a' + 1;
            b = s[strlen(s) - 1] - 'a' + 1;
            if(!h[a]) vs.PB(a), h[a] = true;
            if(!h[b]) vs.PB(b), h[b] = true;
            if(a == b) continue;
            outg[a]++; ing[b] ++;
            union_set(a, b);
            if(c) add_edge(a, b, 1);
        }
        printf("Case %d: ", cas);
        bool flag = true;
        rep(i,0,vs.size()-2)
        {
            if(find(vs[i]) != find(vs[i+1]))
                flag = false;
            if(!flag) break;
        }
        if(!flag)
        {
            puts("Poor boy!");
            continue;
        }
        int cnt = 0, a1, a2;
        rep(i,0,vs.size()-1)
        {
            int tot = ing[vs[i]] + outg[vs[i]];
            if(tot & 1)
            {
                cnt++;
                if(cnt == 1)
                    a1 = vs[i];
                if(cnt == 2)
                    a2 = vs[i];
            }
        }
        if(cnt > 2)
        {
            puts("Poor boy!");
            continue;
        }
        if(cnt == 2)
        {
            add_edge(a1, a2, 1);
            outg[a1]++; ing[a2]++;
        } 
        int sum = 0;
        rep(i,0,vs.size()-1)
        {
            int x = outg[vs[i]] - ing[vs[i]];
            if(x > 0)
            {
                add_edge(0, vs[i], x/2);
                sum += x/2;
            }
            if(x < 0)
                add_edge(vs[i], 27, -x/2);
        }
        if(dinic(0, 27) == sum)
            puts("Well done!");
        else
            puts("Poor boy!");
    }
    return 0;
}
View Code

POJ 1041 John's trip

　　输出欧拉回路。

　　说白了就是一个dfs，代码很简单，不难理解。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int x, y, z;
int m[MAXN][MAXM];
int n, E, s, t;
int g[MAXM];
bool vis[MAXM], tag;
int stk[MAXM];
int top;

void dfs(int u)
{
    rep(i,1,E)
    {
        if(m[u][i] && !vis[i])
        {
            vis[i] = true;
            dfs(m[u][i]);
            stk[top++] = i;
        }
    }
}

void init()
{
    clr(g); 
    clr(m);
    clr(vis);
    E = -1;
    s = inf;
    t = -1;
    top = 0;
}

int main()
{
    while(RII(x, y) != EOF)
    {
        if(x == 0 && y == 0) break;
        RI(z);
        init();
        E = max(E, z);
        s = min(s, min(x, y));
        t = max(t, max(x, y));
        m[x][z] = y;
        m[y][z] = x;
        g[x]++; g[y]++;
        while(RII(x, y) != EOF)
        {
            if(x == 0 && y == 0) break;
            RI(z);
            m[x][z] = y;
            m[y][z] = x;
            E = max(E, z);
            s = min(s, min(x, y));
            t = max(t, max(x, y));
            g[x]++; g[y]++;
        }
        bool flag = false;
        rep(i,1,t)
        {
            flag = g[i] & 1;
            if(flag) break;
        }
        if(flag)
        {
            puts("Round trip does not exist.");
            continue;
        }
        dfs(s);
        per(i,top-1,0)
            printf("%d%c", stk[i], i == 0 ? '
' : ' ');
    }
    return 0;
}
View Code

POJ 2230 Watchcow

　　还是输出欧拉回路，不过和POJ 1041有一点儿不同就是输出的是点，代码稍微有一点儿不同，需仔细体会。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;
struct Node
{
    int v, next;
}E[MAXM];

int n, m;
int NE, head[MAXN];
bool vis[MAXM];

void add_edge(int u, int v)
{
    E[NE].v = v;
    E[NE].next = head[u];
    head[u] = NE++;
}

void dfs(int u)
{
    for(int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].v;
        if(!vis[i])
        {
            vis[i] = true;
            dfs(v);
        }
    }
    printf("%d
", u);
}

void init()
{
    NE = 0; clr(vis);
    memset(head, -1, sizeof head);
}

int main()
{
    int a, b;
    RII(n, m);
    init();
    rep(i,1,m)
    {
        RII(a, b);
        add_edge(a, b);
        add_edge(b, a);
    }
    dfs(1);
    return 0;
}
View Code

POJ 2513 Colored Sticks

　　字典树+欧拉路径。

　　一开始用map存单词，爆了内存。后来才想起用字典树来标记单词，然后判断一下能否构成欧拉回路或欧拉通路即可。（以下代码采用泽阳师兄的字典树写法，比我原来的指针型动态分配内存写法快了一个数量级，此字典树写法才是标准的）。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;
int g[MAXN];
int n, m, k;
int f[MAXN];

struct Tree
{
    int v;
    int next[26];
}P[1000005], root;

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int u, int v)
{
    int x = find(u);
    int y = find(v);
    f[x] = y;
}

int trie(char *s)
{
    int h = 0;
    for(int i = 0; s[i]; i++)
    {
        int a = s[i] - 'a';
        if(!P[h].next[a])
            P[h].next[a] = ++k;
        h = P[h].next[a];
        
    }
    if(P[h].v == 0)
        P[h].v = ++n;
    return P[h].v;
}

int main()
{
    int a, b;
    char u[12], v[12];
    clr(g);
    n = 0; k = 0;
    rep(i,0,MAXN) f[i] = i;
    while(scanf("%s%s", u, v) != EOF)
    {
        a = trie(u); b = trie(v);
        if(a == b) continue;
        g[a]++; g[b]++;
        union_set(a, b);
    }
    bool flag = true;
    rep(i,1,n-1)
    {
        if(find(i) != find(i+1))
        {
            flag = false;
            break;
        }
    }
    if(!flag)
    {
        puts("Impossible");
        return 0;
    }
    int cnt = 0;
    rep(i,1,n)
        cnt += g[i] & 1;
    if(cnt > 2)
        puts("Impossible");
    else
        puts("Possible");
    
    return 0;
}
View Code

POJ 2337 Catenyms

　　因为要保证字典序最小，所以要先从大到小排一下序（没写错，是从大到小，因为到深搜递归的时候越小的字符串保存离栈顶越近），然后依然是打印出欧拉回路。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

struct Edge
{
    int v, next;
}E[MAXM]; 

int n, m;
int head[MAXN], NE;

string s[MAXM];
int ing[MAXN], outg[MAXN]; 
int f[MAXN];
vector<int> vs;
int h[MAXM];
int stk[MAXM], top;
bool vis[MAXM];

void add_edge (int u, int v)
{
    E[NE].v = v;   
    E[NE].next = head[u];
    head[u] = NE++;
}

int find(int x)
{
    return f[x] == x ? x : (f[x] = find(f[x]));
}

void union_set(int u, int v)
{
    int x = find(u);
    int y = find(v);
    f[x] = y;
}

void init()
{
    clr(h);
    clr(ing); 
    clr(vis);
    clr(outg);
    vs.clear();
    NE = 1;
    top = 0;
    memset(head, -1, sizeof head);
    rep(i,0,26) f[i] = i;
}

void dfs(int u, int d)
{
    for(int i = head[u]; i != -1; i = E[i].next)
    {
        int v = E[i].v;
        if(!vis[i])
        {
            vis[i] = true;
            dfs(v, i);
        }
    }
    if(d != -1)
        stk[top++] = d;
}

bool cmp(string u, string v)
{
    return u >= v;
}

int check()
{
    int num=0,cnt1=0,cnt2=0,id=-1;
    rep(j,0,vs.size()-1)
    {
        int i = vs[j];
        if(find(i) == i)
            num++;
        if(ing[i]!=outg[i])
        {
            if(ing[i]-outg[i]==1)
                cnt1++;
            else if(outg[i]-ing[i]==1)
            {
                cnt2++;
                id=i;
            }
            else 
                return -1;
        }
    }
    if(num!=1)
        return -1;
       if(!((cnt1==1&&cnt2==1)||(cnt1==0&&cnt2==0)))
           return -1;
    if(id==-1)
    {
        for(int i=0;i<26;i++)
        {
            if(outg[i]>0)
            {
                id=i;
                break;
            }
        }
    }
    return id;
}

int main()
{
    int t, a, b;
    cin >> t;
    while(t--)
    {
        RI(n);
        init();
        rep(i,1,n)
            cin >> s[i];
        sort(s + 1, s + 1 + n, cmp);
        rep(i,1,n)    
        {
            a = s[i][0] - 'a' + 1;
            b = s[i][s[i].length() - 1] - 'a' + 1;
            if(!h[a]) vs.PB(a), h[a] = true;
            if(!h[b]) vs.PB(b), h[b] = true;
            outg[a]++; ing[b]++;
            union_set(a, b);
            add_edge(a, b);
        }
        int st = check();
        if(st == -1)
        {
            cout << "***" << endl;
            continue;
        }
        dfs(st, -1);
        per(i,top-1,0)
        {
            cout << s[stk[i]];
            if(i != 0) cout << '.';
        }
        cout << endl;
    }
    return 0;
}
View Code

POJ 1392 Ouroboros Snake

　　磁鼓欧拉回路，和前面HDU 2894类似。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        1<<20
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int n, k, cnt;
bool vis[MAXN];
int stk[MAXN], top;
int ans[MAXN];

void dfs(int u)
{
    rep(i,0,1)
    {
        int t = ((u<<1)&((1<<n)-1)) + i;
        if(!vis[t])
        {
            vis[t] = true;
            dfs(t);
            stk[top++] = i;
        }
    }
}

void init()
{
    clr(vis);
    top = 0;
    cnt = 0;
}

int main()
{
    while(RII(n, k) != EOF)
    {
        if(n == 0 && k == 0) break;
        init();
        dfs(0);
        rep(i,1,n-1)
            ans[cnt++] = 0;
        per(i,top-1,0)
            ans[cnt++] = stk[i];
        int sum = 0;
        rep(i,k,k+n-1)
            sum = (sum<<1) | ans[i];
        printf("%d
", sum);
    }
    return 0;
}
View Code

POJ 1780 Code

　　这道题很蛋痛啊，要写非递归的磁鼓欧拉回路，不然要RE的。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
//#pragma comment(linker, "/STACK:102400000,102400000")
#define pii         pair<int,int>
#define clr(a)      memset((a),0,sizeof (a))
#define rep(i,a,b)  for(int i=(a);i<=(int)(b);i++)
#define per(i,a,b)  for(int i=(a);i>=(int)(b);i--)
#define inf         0x3f3f3f3f
#define eps         1e-6
#define MAXN        10000007
#define MAXM        100000007
#define MOD         1000000007
#define debug       puts("reach here")
#define MP          make_pair
#define PB          push_back
#define RI(x)       scanf("%d",&x)
#define RII(x,y)    scanf("%d%d",&x,&y)
#define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
typedef long long LL;

int n, k, cnt, p;
int stk[MAXN], top;
int ans[MAXN];
int num[MAXN];

void solve()
{
    stk[top++] = 0;
    num[0]++;
    while(top)
    {
        int u = stk[--top];
        ans[cnt++] = u % 10;
        u /= 10;
        while(num[u] < 10)
        {
            int w = u * 10 + num[u];
            num[u]++;
            stk[top++] = w;
            u = w % p;
        }
    }
}

void init()
{
    top = 0;
    cnt = 0;
    p = 1;
    rep(i,1,n-1) p *= 10;
    clr(num);
}

int main()
{
    while(RI(n) != EOF)
    {
        if(n == 0) break;
        if(n == 1) {puts("0123456789"); continue;}
        init();
        solve();
        rep(i,1,n) printf("0");
        per(i,cnt-1,n-1)
            printf("%d", ans[i]);
        rep(i,1,n-2) printf("0");
        putchar('
');
    }
    return 0;
}
View Code

相关推荐