4,10630 – Millennium Ceremony,图论的压轴题吧!很多东西在里面。

关键知识点:外向树,欧拉回路的构造,完美匹配,以及改造的图存储.沿用书上的分析,加上一些自己的证明[书上有些地方没有完全写透,应该是留给写程序的人思考的].

算法分析:

  • chris 和chrit的路径必然都是一条完整的欧拉回路,换言之,我们需要构造这样的一条欧拉回路.但更重要的是要求同层rops颜色相间,所以要先设法构造出满足这个条件的欧拉回路.很容易知道chris[或者chrit]的变色边必然是连通的,且0层的入度为0,其他所有点的入度为1,那么这是一个以0层祭坛为根的外向树.假设我们能构造出这条外向树,并且在此基础上构造出含这条外向树的欧拉回路.那么,对于chris以及chrit可以求出其路径了
  • 外向树的构造法:从祭坛引出1,3,5…m-1等出边到第一层[并且将2,4,6,8…m等设置为入边,开始稀里糊涂的写程序,结果仔细一看度不平衡,俄,又迷信LRJ了],再在两个内层i,i+1之间求一次完美匹配[如何证明?每个柱子都有k个连接边到上层,换言之,X集的每个顶点出度均为k,而Y集的每个顶点入度也为k,且对于X集和Y集而言,彼此序号必然对等,m为偶数,而k个层间ropes连接的两个端点奇偶一致],X集的每一个顶点引出一个有向边到Y集的对端,由此Y集的每一个奇数点必然都被占据.OK,那么如此匹配的结果就是1…n层的所有奇数点均入度为1,然后再从n层的随机点引一条边到n+1层的圣火炬,外向树就构造完毕了.
  • 基于外向树的欧拉回路:在外向树边的基础上,添边形成全边的欧拉回路,第一类边:从2,4,m到祭坛0的入边,以及从1,3,5,…m-1到火炬的入边,从火炬到2,4,6…m的出边;第二类边:同层连接边,从2i->(2i+1)%m的连接边[每个柱子出入平衡];第三类边:层间连接边,对每个节点的剩余k-1条边进行奇偶完美匹配[奇数为出边,偶数为入边].
  • 带限制的欧拉回路算法:直接用欧拉回路算法求解,只是要保证变色边是x->y中,使得若y是第一次到达,x->y是外向树的变色边.
  • 路径递推:得到了chris的路线之后,只需要把他到达的每个点向“右”旋转一个单位,就可以得到chrit的路线。什么意思?将路径平移转化到下一个间边即可。
  • 无解的情况:什么时候无解呢?没想清楚,因为按照构造法,m是偶数,k是奇数,这样一定能保证欧拉回路是存在的,而外向树的构造肯定是存在的.疑惑中,只有先烧烤一下了.

附一个外向树生成示意:

算法实现分析:

  • E路的两个简单实现:[不含验证逻辑,验证很简单,从一点出发DFS或者直接用es来做并查集,同时记录每点的入度和出度,入度出度不同,直接跳出;不连通,直接跳出]
  • 1, 圈套算法的一个简化版本[USCAO上摘录]
    //circuit is a global array
    void find_euler_circuit(){
        circuit_pos=0;
        find_circuit(node 1);
    }
    //nextnode and visited is a local array,the path will be found in reverse order
    void find_circuit(node i){
      while(hasNeighbors(node i)){//for list all nodes in Euler circuit
           pick a random neighbor node j of node i
           delete_edges(node j, node i);
           find_circuit(node j);
      }
      circuit[circuitpos++]=node i;
    }
     
    2,fleury算法 [离散数学上的代码框架]

    (1).任取v0属于v(G),P0=v0;

    (2) Pi=v0e1v1e2…eivi已经行遍,按下面方法来从E(G)-{e1,e2,…..ei}中任取ei+1 ;

          (a) : ei+1vi相关联:

          (b): 除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,….ei}中的桥.[求桥的算法那是相当讨厌的]

    (3): (2)不能再进行时,算法停止.

    可以证明,当算法停止时所得的简单回路Pm=v0e1v1e2….emvm(vm=vo)G中的一条Euler Circuit.

    总结:这种算法的复杂度是o(e*e),

    • 代码实现上的一个技巧:圈套算法USACO的版本,是以入边为基础的,因此在手动构造图的时候,将其边反过来,记录其入边集合,其实还可以优化一下的,可以把外向树的边放在每个入边顶点的最后,这样Euelur路的算法里面都不用交换顶点了.懒了一下.然后就是E路的求法了,由于E路是反向的[dfs递归的顶部是无后继点],最初的顶点是最后访问的,因此在扩展的时候,将外向树的边[每个顶点只有一条]放在最后即可.这样E路代码就可以在10行左右搞定了.
    • 悲惨的WA,UVA的结果是[估计应该是无欧拉路的时候的错误,郁闷,还是没能烧烤过去,再想下罗]

      7136448 10630 Millennium Ceremony Wrong answer C++ 0.416 2009-05-18 15:08:42

    附现在的代码实现:调试了一下,发现了无向树生成的错误和序号计算的错误.
    // MillCeremony.cpp : Defines the entry point for the console application.
    //
    #include "stdafx.h"
    #include <assert.h>
    #include <stdlib.h>
    #include <iostream>
    #include <fstream>
    #include <vector>
    using namespace std;
    const int MAXM=50, MAXN=50, MAXK=9, MAXENS=24000/*max crossing ropes*/, MAXET=25000, MAXMN=2600;
    typedef struct ENode{
        int i, j, next;
    }ENode;
    ENode inext[MAXENS];
    typedef struct Edge{
        int i, j, next;
        bool color, visited;
    }Edge;
    Edge es[MAXET];
    int eid, nid, m, n, k, firstI[MAXMN], firstG[MAXMN];
    //declaration
    void clr();
    void nextInner(int pid, int nid);
    void addREdge(int end, int start, bool color);
    void createEuler();
    void createOutTree();
    void addLeft();
    //perfect match algorithm
    //structure
    int linkX[MAXM+1], linkY[MAXM+1], distX[MAXM+1], distY[MAXM+1], queue[MAXM];
    int HK(int curl);
    bool HK_bfs(int curl);
    bool HK_dfs(int v, int curl);//v->0…m-1
    //EulerCircuirt algorithm
    vector<int> epath;
    void EulerCircuirt(int v);
    //implementation
    void EulerCircuirt(int v){
        for(int ed=firstG[v]; ed!=-1; ed=firstG[v]){//remove entry for each time,倒霉挨打的欧拉路
            if(es[ed].color&&es[ed].next!=-1){//swap(ed=firstG[v], es[ed].next)
                firstG[v]=es[ed].next, es[ed].next=es[firstG[v]].next, es[firstG[v]].next=ed;
                ed=firstG[v];
            }
            if(es[ed].next!=-1)assert(!es[ed].color);
            int tmp=es[ed].j;
            firstG[v]=es[ed].next;//remove the head of circuit
            EulerCircuirt(tmp);
        }
        epath.push_back(v);
    }
    //implementation of HK algorithm
    int HK(int curl){
        memset((void*)linkX, 0xff, sizeof(linkX)),
        memset((void*)linkY, 0xff, sizeof(linkY));
        int res(0);
        while(HK_bfs(curl)){
            for(int i=1; i<=m; i++){
                if(linkX[i]==-1&&HK_dfs(i, curl)) res++;
            }
        }
        //please remove the match edge from inext sets.
        for(int i=1; i<=m; i++){
            int t=linkX[i], from=(curl-1)*m+i, to=curl*m+t;//remove (curl, i)->(curl+1, t)
            int pre=-1, ed=firstI[from];
            for(;ed!=-1; pre=ed, ed=inext[ed].next){
                if(inext[ed].j==to) break;
            }
            assert(inext[ed].j==to);//must exist
            if(pre==-1) firstI[from]=inext[ed].next;
            else inext[ed].next=inext[ed].next;
        }
        return res;
    }
    bool HK_bfs(int curl){
        int top=0, size=0; bool found=false;
        for(int i=1; i<=m; i++){
            if(linkX[i]==-1) queue[size++]=i;
            distX[i]=0;
        }
        memset((void*)distY, 0, sizeof(distY));
        for(;top<size;top++){
            int v=queue[top];
            for(int ed=firstI[(curl-1)*m+v]; ed!=-1; ed=inext[ed].next){
                if(!distY[inext[ed].j-curl*m]){
                    distY[inext[ed].j-curl*m]=distX[v]+1;
                    if(linkY[inext[ed].j-curl*m]==-1) found=true;
                    else distX[linkY[inext[ed].j-curl*m]]=distX[v]+2, queue[size++]=linkY[inext[ed].j-curl*m];
                }
            }
        }
        return found;
    }
    bool HK_dfs(int v, int curl){
        for(int ed=firstI[(curl-1)*m+v]; ed!=-1; ed=inext[ed].next){
            if(distY[inext[ed].j-curl*m]==distX[v]+1){
                distY[inext[ed].j-curl*m]=0;
                if(linkY[inext[ed].j-curl*m]==-1||HK_dfs(linkY[inext[ed].j-curl*m], curl)){
                    linkX[v]=inext[ed].j-curl*m, linkY[inext[ed].j-curl*m]=v; return true;
                }
            }
        }
        return false;
    }
    //implementation
    void clr(){
        eid=0, nid=0, memset((void*)firstI, 0xff, sizeof(firstI)),
        memset((void*)firstG, 0xff, sizeof(firstG));
    }
    void nextInner(int p, int n){
        inext[nid].i=p, inext[nid].j=n;
        inext[nid].next=firstI[p], firstI[p]=nid; nid++;
    }
    void addREdge(int end, int start, bool color){//end->start, reverse starting inEdge.
        es[eid].i=start, es[eid].j=end;
        es[eid].visited=false, es[eid].color=color;
        es[eid].next=firstG[start], firstG[start]=eid; eid++;
    }
    void createEuler(){
        createOutTree(), addLeft();//外向树的生成逻辑以及添边生成全边欧拉回路
    }
    void createOutTree(){
        for(int i=1; i<=m; i+=2)
      addREdge(0, i, true);//0->(1, 2i+1)
        addREdge(n*m+1-m, n*m+1, true);//0, (1…m), (nm-m+1…nm), nm+1
        for(int i=1; i<n; i++){//for perfect-match of i layer -> i+1 layer.
            assert(HK(i)==m);//previous level
            for(int j=1; j<=m; j++){
       if(j&0x1){
        addREdge((i-1)*m+j, i*m+linkX[j], true);//must remove edge.
        addREdge((i-1)*m+j, (i-1)*m+j+1, true);//inner ropes. 1->2, 3->4…
       }
       else{//j is even
        addREdge(i*m+linkX[j], (i-1)*m+j, false);//must remove edge.
        addREdge((i-1)*m+j, (i-1)*m+(j+1)%m, false);//inner ropes. 1->2, 3->4…
       }
            }
        }
        for(int j=1; j<=m; j+=2) addREdge((n-1)*m+j, (n-1)*m+j+1, true);//left n layer
     for(int j=2; j<=m; j+=2) addREdge((n-1)*m+j, (n-1)*m+(j+1)%m, false);
    }
    void addLeft(){
        for(int i=2; i<=m; i+=2)
      addREdge(i, 0, false);//(1, i)->0
        for(int i=2; i<=m; i++){//for (n, i)->nm
            if(i&0x1) addREdge((n-1)*m+i, n*m+1, false);
            else addREdge(n*m+1, (n-1)*m+i, false);
        }
        for(int i=1; i<n; i++){//(i,x)->(i+1,linkX[x])
            for(int p=1; p<k; p++){//left k-1 time -> 2*p
                assert(HK(i)==m);
                if(p&0x1){
                    for(int q=1; q<=m; q++) addREdge(i*m+linkX[q], (i-1)*m+q, false);
                }
                else{
                    for(int q=1; q<=m; q++) addREdge((i-1)*m+q , i*m+linkX[q], false);
                }
            }
        }
    }
    #define fbase
    int main()
    {
    #ifdef fbase
        ifstream in("input.txt");
        if(!in) return EXIT_FAILURE;
        cin.rdbuf(in.rdbuf());
    #endif
        //implementation
        int ncase, icase=1, nx, lines, line;
        cin>>ncase;
        for(;icase<=ncase; icase++){
            cin>>n>>m>>k; clr();
            for(int i=1; i<n; i++){//take care of id for inner edge.
                for(int j=1; j<=m; j++){//start with k=0 to m-1, (i, j)
        for(int pk=0; pk<k; pk++){
         cin>>nx;
         nextInner((i-1)*m+j, i*m+nx);
        }
                }
            }
      lines=2*m*(n*k-k+n+2);
            if((m&0x1)==0&&(k&0x1)){
                createEuler();
                epath.clear(), EulerCircuirt(0);
       int x, y;
                cout<<"Case "<<icase<<": Yes"<<endl;
                vector<int>::iterator start=epath.begin(); start++;
       assert(lines/2==epath.size()-1);
                for(;start!=epath.end();start++){
        if(*start==0) cout<<0<<" "<<0<<endl;
        else if(*start==n*m+1) cout<<(n+1)<<" "<<0<<endl;
        else{//*start
         x=(*start-1)/m+1, y=*start-((*start-1)/m)*m;
         cout<<x<<" "<<y<<endl;
        }
                }
       start=epath.begin(), start++;
                for(;start!=epath.end();start++){
        if(*start==0) cout<<0<<" "<<0<<endl;
        else if(*start==n*m+1) cout<<(n+1)<<" "<<0<<endl;
        else{//*start
         x=(*start-1)/m+1, y=*start-((*start-1)/m)*m;
         cout<<x<<" "<<y%m+1<<endl;
        }
       }
            }
            else{
                cout<<"Case "<<icase<<": No"<<endl;
            }
        }
    #ifdef fbase
        in.close();
    #endif
     system("pause");
        return 0;
    }
    #undef fbase
    PS:实在不甘心,最后两道题目写出来结果遭两个WA,郁闷倒了!怎么办?继续研究,还是放弃,相当不甘心.
    一边回顾整理简历保持编码量的同时,再研究下落下的题目吧!数了数.
    图论里面:
    • 4个WA[这道,上道,漆门,水平可见].
    • 1个RLE(the rock).
    • 一道Messenger没有数据没有做,一道超级翻转没有数据没有做.
    搜索里面:
    • L-Game的预处理比较复杂,没有做.
    • Besty DP没有实现.
    • 还有道水题冠军篮球赛[被湖人那么弱的表现气到球了!]
    勉勉强强算把黑书和<实用>的动规,搜索以及图论部分结束了,可以开始整理简历和做BOP review和面试的白纸编程了.有了这些基础,我想应该要轻松多了吧!但代码量不能减少,应该再大一点.这样才能保持好状态.
    I’ll be back soon!

    Advertisements