• 自己觉得这道题目很简单,结果搞了一天多!要好生总结下!
  • Alice and Bob,意思5分钟就搞懂了,有一个图有唯一的H路,然后将图恢复过来![这里只分析书上的最后两种思路,前一种复杂度太大,没必要写!]

图结构存储:由于输出是一个升序序列,我们可以将邻接表的输入以关键字升序排列,这样可以将找路的算法基本控制为O(1),对于一个方向已定的H路!

算法思路1
1。将度为2的节点Ai取出,找出Ai-1和Ai+1,将非虚拟边[在原图中的边]放入一个目标图shadow,然后为Ai-1和Ai+1添加一条虚拟边在原图中;判断Ai-1<->Ai和Ai<->Ai+1是否在原图中,是否需要放入目标图shadow,可以用UFS来处理!是否很简单?这样每次目标图中增加一个顶点,两或者一条边在目标图内。
2。不简单的地方在于,只剩下两个顶点,怎么办?因为无论Ai和Ai-1如何处理,UFS都无法单独判断是否这条边为原图。看了几个ACMer和标程的处理,但觉得巧妙但不直观,我的方法是:找出剩下两个点中在目标图shadow中度为一的点,然后用O(1)的方法找出这条H路。
3。最后的处理要小心,因为要求从1开始的路,这个是循环数组的处理,直觉告诉我可以用reverse(a, b)来搞定,但是,有更好的方法,这里只要输出,所以先判断1的坐标前一个,和后一个数字的比较,然后从1开始,沿后一个数字方向或者正向移到1的坐标就行了!OK!
 
一句话,还是很简单,但时间花在什么地方呢?这就是骄兵必败的原因了,我写这个程序花了不到30分钟,但搞了一个晚上才勉强过。第一个版本的时间大概2500MS,第一个调试通过的程序跑了11s!
错误点
1。对qsort和make_heap的误用,qsort是针对数组指针的,所以对于char* t[max]的排序,是qsort((void*)t, max, sizeof(char*), cmp)->*(char**)p1;而make_heap是将元素视为一个STL的基本元处理,所以make_heap((void*)t, (void*)t+max, cmp), ->(char*)p1即可。对于结构体,应该这样写:
 
Hnode q[MAXN];//degree structure array
Phnode ptr[MAXN+1];
 
由于要找出所有的元素中度为2的点,作了个结构体的数组,再用一个指针数组处理,这样q[1。。。MAXN-1]我们直接更改其度,然后就可以用heap找出最小度的元素了!是否很聪明?所以qsort((void*)ptr, size, sizeof(Phnode), cmp)->cmp:*(Phnode*)p1,而make_heap为make_heap((void*)ptr, (void*)ptr+size, cmp)->cmp:(Phnode)p1.
但告诉你这成为程序最大的bottleneck,也是第一个程序跑料11s的最大原因!
我用gprof -b查看了一下,发现make_heap和pop_heap占用了70%的时间,11s的70%,对了STL的默认策略,反复拷贝调整堆,接口转化iterator;谢谢Jon的书,我马上改用qsort速度一下就快了一半多!再想下,其实排序有必要么,O(N)一次找出度为2的点,然后用^换到数组边界一切就行了,这样的程序大概2000MS,对所有的程序都能跑出正确的结果!
 
所以,对STL的东西还是要三思而后行,qsort是STL么?有iterator支持么?make_heap则是肯定要iterator支持的,用结构体肯定出错,iterator::trait有么?
当你不满意程序性能的时候[正确的程序哈,错误的程序没有讨论的必要,跑再快也没用],gprof可以帮你一把!最大的经验是,技巧不可乱用,聪明的做法有的时候实际上是愚蠢的,上面的例子就是,别人需要你求最小的么?如果知道最小的为2,何必再花力气维护堆呢?无论是你,还是系统,都不可取!
 
下面是我的程序代码:

Source Code

Problem: 1429

User: orlando22

Memory: 1000K

Time: 2500MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAXN=10001, MAXE=60000;
    typedef struct Edge{
        int t; Edge* next;
    }Edge, *Pedge;
    int eid=0;
    Edge storage[MAXE];
    Pedge links[MAXN], shadow[MAXN];//linklist
    typedef struct Hnode{
        int id, degree;
    }Hnode, *Phnode;
    Hnode q[MAXN];//degree structure array
    Phnode ptr[MAXN+1];
    int color[MAXN], size;
    
    //UFS set
    class UFS{
    private:
        int sets[MAXN], setk;
    public:
        void clr(){memset((void*)sets, 0, sizeof(sets));}
        UFS(){clr();}
        void setKeys(int k){
            setk=k,memset((void*)(sets+1), 0xff, sizeof(int)*k);
        }
        int find(int i){
            if(i<1||i>setk||!sets[i]) return -1;
            int v=i;
            while(sets[i]>0) i=sets[i];
            while(v!=i){
                int tmp=sets[v];sets[v]=i;v=tmp;
            }
            return i;
        }
        void unions(int i, int j){
            if(i<1||i>setk||!sets[i]||j<1||j>setk||!sets[j]) return;
            int t1=find(i), t2=find(j);
            if(t1==t2) return;
            int p1=sets[t1], p2=sets[t2];
            if(p1<p2){
                sets[t1]=p1+p2; sets[t2]=t1;
            }
            else{
                sets[t2]=p1+p2; sets[t1]=t2;
            }
        }
    };
    //priority queue
    void Intial(int s){//一气子下,删掉实现
        size=s;
        for(int i=1; i<size+1; i++) ptr[i]=q+i;
    }
    int Popup(){//sort from [1...size]
        int ret=size;
        for(int i=1; i<size+1; i++){
            if(ptr[i]->degree==2){
                if(i!=size){
                    Phnode tmp=ptr[i]; ptr[i]=ptr[size]; ptr[size]=tmp; break;
                }
            }
        }
        size--;
        return ret;
    }
    UFS _u;
    
    //local data part
    int n, k, out[MAXN];
    //declaration
    bool inline insert(int i, int j);//don't require change type function
    void moveto(int i, int j);
    void inline remove(int i, int j);
    void solution();
    void reverse(int i, int j);
    void output(int v);
    
    //implementation
    bool inline insert(int i, int j){
        Pedge cur=storage+(eid++);
        cur->t=j, cur->next=NULL;
    	Pedge c=links[i], pre=NULL;
        for(;c&&c->t<j;pre=c,c=c->next);
        if(c&&c->t==j) return false;//impossible for assert(edges)
        if(c) cur->next=c;
    	if(!pre) links[i]=cur;
        else pre->next=cur;
        return true;
    }
    void solution(){
        int c, x, y;
        while(size>2){//for pologyns with more than
            int id=Popup(); x=y=0,c=ptr[id]->id;//current 2-degree point
            q[c].degree=0;
            for(Pedge cur=links[c]; cur; cur=cur->next){
                if(!x) x=cur->t;
                else if(!y) y=cur->t;
            }//don't need to modify c's degree, it's out of game
            if(_u.find(c)!=_u.find(x))//not the same sets
                moveto(c, x), moveto(x, c), _u.unions(c, x);
            else remove(c, x), remove(x, c);
            q[x].degree--;
            if(_u.find(c)!=_u.find(y))
                moveto(c, y), moveto(y, c), _u.unions(c, y);
            else remove(c, y), remove(y, c);
            q[y].degree--;
            //x<->y
            if(insert(x, y)&&insert(y, x)) q[x].degree++, q[y].degree++;
        }
    	for(int i=1; i<3; i++){//找1度点
    		int cdegree=0;
    		for(Pedge cur=shadow[ptr[i]->id]; cur; cdegree++, cur=cur->next);
    		if(cdegree==1){x=ptr[i]->id; break;}
    	}
        output(x);
    }
    void inline remove(int i, int j){
        Pedge cur=links[i], pre=NULL;
        for(;cur;pre=cur,cur=cur->next)
            if(cur->t==j) break;
        if(!pre) links[i]=cur->next;
        else pre->next=cur->next;
    }
    
    void moveto(int i, int j){//get c->x pointer
        Pedge cur=links[i], pre=NULL, p;
        for(;cur;pre=cur,cur=cur->next)
            if(cur->t==j) break;
        if(!pre) links[i]=cur->next;
        else pre->next=cur->next;
        cur->next=NULL;//erase
        //links to shadow
        p=shadow[i], pre=NULL;
        for(;p&&p->t<j;pre=p,p=p->next);
        if(p) cur->next=p;
        if(!pre) shadow[i]=cur;
        else pre->next=cur;
    }
    void output(int v){
        memset((void*)(color+1), 0, sizeof(int)*n);
        int start=v, cur1=-1; Pedge e;
        out[1]=start,color[start]=1;
        for(int i=2; i<n+1; i++){//2->n
            e=shadow[start];
            for(;e;e=e->next) if(!color[e->t]) break;
            out[i]=e->t,color[e->t]=1,start=e->t;
    		if(e->t==1) cur1=i;
        }
    	int pre=(cur1==1?n:cur1-1), fol=(cur1<n?cur1+1:1), t;//滚动逻辑
    	if(out[pre]<out[fol]){
    		for(int i=cur1; i>cur1-n; i--){
    			if(i>0) cout<<out[i];
    			else cout<<out[i+n];
    			if(i!=cur1-n+1) cout<<" ";
    		}
    	}
    	else{
    		for(int i=cur1; i<cur1+n; i++){
    			if(i<n+1) cout<<out[i];
    			else cout<<out[i-n];
    			if(i!=cur1+n-1) cout<<" ";
    		}
    	}
    	cout<<endl;
    }
    
    int main()
    {
        //implementation
        int ncase, s, t, len;
        cin>>ncase;
        for(int i=0; i<ncase; i++){
            cin>>n, cin>>k;
            len=n+k, eid=0;
            memset((void*)links, 0, sizeof(links)),memset((void*)shadow, 0, sizeof(shadow)),
            memset((void*)q, 0, sizeof(q)), memset((void*)ptr, 0, sizeof(ptr));
            for(int j=0; j<len; j++){
                cin>>s, cin>>t;
                insert(s, t), insert(t, s);
                q[s].degree++,q[t].degree++;
            }
            for(int i=1; i<n+1; i++) q[i].id=i;
            Intial(n), _u.setKeys(n);//set ptr of q
            solution();
        }
        return 0;
    }
    
算法思路2:书上写的很乱,我没有看懂,实际上他也是抄标程的代码,所以节选原文如下。
Solution: Let us define a polygon graph as the graph in which two verices are joined if they are ends of the same side or diagonal. Such a graph has only one Hamiltonian cycle and our goal is to find this cycle.
We proceed as follows:
   1. Identify sides of the polygon.
   2. Build the subgraph spanned on the sides – this is the required cycle.
   3. Find proper order of the vertices on the cycle.
  
   The only hard steps are 1 and 2. In order to identify sides of the polygon
   we apply Depth First Search computing the dfs_numbering and the function
   low defined on the vertices in the following way
   (this is the same function as in the the famous algorithm for computing biconnected components):
  
    low[v] = min(<dfs_nr[v]> + <low[w]: w son of v in dfs tree> +
                  <dfs_nr[w]: w is ancector of v in dfs tree diffrent from
                its parent>)
        
   (Note: ‘+’ means sum of sets.)
  
   Both the function low and dfs_numbering can be computind during the one run of the depth first search.
   Applying these two functions we can classify the edges of the graph as follows.
   
Let us consider a dfs-tree edge u—v, where u is the parent of v.
There are several cases:
   1. vertex v has no children — it means that u–v is a side of the polygon;
among the other edges incident to v the edge going to the vertex with the smallest dfs_number corresponds to the another side incident to v.
   2. vertex v has 1 child — unfortunately there are 2 subcases
      2.1 parent of v is the root of the tree: u–v is a side of the polygon; the other sides incident to u or v have been already found.
      2.2 u is not the root of the tree, let w be the only child of v:
          if low[w]//wrong,actually it’s depth < dfs_nr[u] , then u–v is a side of the polygon, the other side incident to v has been already found;
          if low[w] >= dfs_nr[u] , then u–v is a diagonal; let x be the ancestor of v for which the value low[x] is the smallest one; v–x is a side of the polygon, the other side incident to v has been already found.
   
   Running time – linear.
*}     
那剩下的问题就不多了撒,但程序只跑了1283MS。我看了下程序gprof的输出,发现所有的时间花在邻接表上了,然后立刻把shadow的实现用数组重写了一次,快了一点!但如果用vector会快很多的,网上一个兄弟就用这种方法水的,但vector的话,还是正规开发用吧,这里我就自己写了!
针对算法优化已经没有多大的必要,80%的时间在邻接表生成上,行了!这道题目就此划上句号![很不完美,前一个那么难的题目都只用了32MS.]
一个小优化,控制图的边为循环控制变量,然后将DFS也用在边判断里面[这里犯了个错,要将所有定点过一次,避免环上的点没有判断],发现DFS的时间基本已经降到0MS,差不多了,不用较真!

Source Code

Problem: 1429

User: orlando22

Memory: 1312K

Time: 1282MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    //pku 1429 Alice and Bob
    using namespace std;
    const int MAXN=10002, MAXE=50000;//array size
    typedef struct Edge{
    	int t; Edge* next;
    }Edge, *Pedge;
    Edge storage[MAXE];
    int eid=0, size=0;
    //linkedlist
    Pedge links[MAXN];
    int n, k, low[MAXN], dep[MAXN], color[MAXN], out[MAXN],
    childnum[MAXN], child[MAXN], p[MAXN], shadow[MAXN][2];
    enum {white=0, gray=1, black=2};
    
    //declaration
    void inline insert(int i, int j);
    void inline shadow_insert(int i, int j);
    void dfs(int v, int father, int deep);
    void sideCheck(int v, int cofv);
    void judgeSide(int v);
    void output();
    
    //implemenation
    void insert(int i, int j){
    	Pedge cur=storage+(eid++);
    	cur->t=j,cur->next=NULL;
    	Pedge l=links[i], pre=NULL;
    	for(;l&&l->t<j;pre=l,l=l->next);
    	if(l&&l->t==j) return;//impossible
    	if(l) cur->next=l;//common operations
    	if(!pre) links[i]=cur;
    	else pre->next=cur;
    }
    void shadow_insert(int i, int j){
        if(shadow[i][0]==j||shadow[i][1]==j) return;
        if(shadow[i][0]==0) shadow[i][0]=j, size++;
        else if(shadow[i][1]==0) shadow[i][1]=j, size++;
        else return;//no more than two vertexs for it, impossible
        if(shadow[i][0]>shadow[i][1])
            shadow[i][0]^=shadow[i][1], shadow[i][1]^=shadow[i][0], shadow[i][0]^=shadow[i][1];
    }
    
    void dfs(int v, int father, int deep){
    	low[v]=dep[v]=deep, color[v]=gray;
    	int tot=0; p[v]=father;
    	for(Pedge cn=links[v]; cn; cn=cn->next){
    		if(color[cn->t]==gray&&cn->t!=father){
    			if(dep[cn->t]<low[v]) low[v]=dep[cn->t];
    		}
    		if(color[cn->t]==white){
    			if(tot==0) child[v]=cn->t;
    			dfs(cn->t, v, deep+1);
    			tot++; if(low[cn->t]<low[v]) low[v]=low[cn->t];
    			//pre-calculation
    			sideCheck(v, cn->t);
    		}
    	}
    	color[v]=black, childnum[v]=tot;
    	if(tot>1) child[v]=0;//erase if more than one child
    }
    
    void sideCheck(int v, int cofv){//v is cofv [abbriviated by childofv] parent
        if(childnum[cofv]==0){
            shadow_insert(v, cofv), shadow_insert(cofv, v);
            int minDeptoV=INT_MAX, toV=0;
            for(Pedge tocv=links[cofv]; tocv; tocv=tocv->next){
                if(dep[tocv->t]<minDeptoV)//other side with smallest depth&&tocv->t!=v
                    minDeptoV=dep[tocv->t], toV=tocv->t;
            }
            if(toV!=0) shadow_insert(toV, cofv), shadow_insert(cofv, toV);
        }
        else if(childnum[cofv]==1){
            if(v==1) shadow_insert(v, cofv), shadow_insert(cofv, v);
            else{
                int w=child[cofv];
                if(low[w]<dep[v])//not bridge, u->v
                    shadow_insert(cofv, v), shadow_insert(v, cofv);
                else{//u->v is diagnoal
                    int minlow=INT_MAX, tov=0;
                    for(Pedge tocv=links[cofv]; tocv; tocv=tocv->next){//tocv->t attach to av->t, it's its ancestor, and having smallest low value
                        if(dep[tocv->t]<minlow)//&&tov!=v&&dep[tocv->t]<dep[cv->t]
                            minlow=dep[tocv->t], tov=tocv->t;
                    }
                    if(tov!=0) shadow_insert(tov, cofv), shadow_insert(cofv, tov);
                }
            }
        }
    }
    
    void judgeSide(int v){
    	for(Pedge cv=links[v]; cv; cv=cv->next){
    		if(p[cv->t]==v){//cv->t is the child of node v of subcase
    			sideCheck(v, cv->t);
    			if(size==2*n) break;
    		}
    	}
    }
    
    void output(){
    	int start=1, e;
    	memset((void*)color, 0, sizeof(color));
    	out[1]=start; color[1]=1;
    	for(int i=2; i<n+1; i++){
    		if(color[shadow[start][0]]==0) e=shadow[start][0];
    		else if(color[shadow[start][1]]==0) e=shadow[start][1];
    		out[i]=e,color[e]=1,start=e;
    	}
    }
    
    int main()
    {
    	//implementation
    	int ncase, s, t, len;
    	cin>>ncase;
    	for(int i=0; i<ncase; i++){
    		cin>>n, cin>>k;
    		len=(n+k); eid=0, size=0;//reset for edage recording
    		memset((void*)links, 0, sizeof(links)),
    			memset((void*)shadow, 0, sizeof(shadow));
    		for(int j=0; j<len; j++){
    			cin>>s, cin>>t;
    			insert(s, t), insert(t, s);
    		}
    		memset((void*)low, 0, sizeof(low)),
    			memset((void*)dep, 0, sizeof(dep)),
    			memset((void*)childnum, 0, sizeof(childnum)),
    			memset((void*)color, 0, sizeof(color)),
    			memset((void*)p, 0, sizeof(p)),
    			memset((void*)child, 0, sizeof(child));
    		dfs(1, 0, 0);
    		for(int i=n; i>1&&size!=2*n; i--) judgeSide(i);
    		output();
    		//int t;
    		for(int i=1; i<n+1; i++){
    			cout<<out[i]; //outf>>t;
    			if(i!=n) cout<<" ";
    			//assert(out[i]==t);
    		}
    		cout<<endl;
    	}
    	return 0;
    }
  • 继续努力!!!

Advertisements