• The Cave 知识点:数组二叉树,bfs[没有上面一道那么艰深]
算法分析:[特殊的H路处理问题,但由于内度为3,因此通过特殊的定向环处理可以将其转化为特殊的二叉树,随后写出O(1)算法]
1.对于从1开始的一条最优路而言,可以看作是以1为根的二叉树,这样问题有点类似于线索二叉树.如图:

OK,lrj的思路,对于一个M->A->E确定的路线[枚举]而言,下面分情况处理:
1.若存在未被访问过的最高点I,找出一条经过E1,E2以及I的唯一内路径,可以从I开始两次树遍历.
昨晚开始编码的时候才发现有个问题没解决,如果我们是随机生成dfs的二叉树,那么对于一个从I点开始的唯一内通道,我们不可能有O(E)的方法找到相应的相邻的开始和结束外端点的!因为要每次验证两个节点是否相邻,这个会使得效率大大降低!
所以,我采用的方法是:在录入数据的时候,生成一个外环的序列[从1的高端开始,回到1本身],对应每一个外环节点给一个序号oid[i],具体就是用pre[i=1..k],fol[i=1..k]记录i的相邻点,然后从1开始进行调整,pre[i]!=上一个节点,就交换];然后先用dfs生成一个随机二叉树O(E),随后进行一个树调整[后序树遍历调整],使得二叉树的左子树oid[i]序号一定比右子树序号大,O(E).
有了这样的二叉树,I对应的内通路实际上就是,以它为根的子树中序序列,左树的最后一个叶结点以及右树的第一个叶结点。O(E),每次只要删除树路径,标记图上的路径;而删除树路径,只需要在递归之后将其路径结点的leftc,rightc置空即可!
 
2.反之,检查当前未访问的外结点(E1,E2)是否能通过已经访问的红色边相连,如果不行则,直接使用边E1->E2.
反复处理,直到被访问的边数为N。
 
2.M->A->E的枚举,OK,最简单的是两条都是外通道。先排除一种可能,两条不可能都是内通道,因为内通道只能被访问一次,而两个顶点之间只有唯一一条内通道相连,若两条都是内通道那么必然有条连接的内通道被访问两次.所以,下面就是枚举两者的可能性,一共3种可能,编号即可实现。
 
算法设计:
1.用邻接表存储图,将其结点升序排列。生成外结点序列
2.bfs生成树,注意那个所谓的辈分表就是dfs的队列。[由于我们的邻接表是按节点升序排列的,因此可以默认其发现的第一个内节点,就是其left枝;而第二个节点则是right枝]。
3.调整生成树。
3.实现上面描述的逻辑:最终的路径一定是1->p1->(p1->p2)->p2,如何求p1->p2?按照标记路径走一次即可
 
算法实现:犯了两个错误,还有一些需要改进的地方
1.在枚举路径的时候1->p1->(p1->p2)->p2,我用一个邻接表来存储访问路径,那最后可以将1->p2的邻接表收敛起来,就得到一条路径;关键在于1->p1和p2->1的两条内路径处理上,p2->1的处理有所不同,因为只能存储p2->1的前一个节点,所以要注意了bool findIn(int I, const int& e, const bool& reverse)的实现要分两种情况来处理!
2.书上是描述性的语言,其实那个路径的颜色完全没必要存储,如果标记了每个顶点的颜色,那么和是否在生成树中的数组,red颜色在编程中完全没有必要显式定义!可以直接省去!
3.树边的连通性处理可以用UFS来进行处理,这个比较简单,5分钟搞定且没有bug!
4.在连接边的存储问题上犯了一个错,由于连接边存储了头节点,因此LinkNode的预设内存应该是顶点的两倍,再次提醒自己要注意边界预估[开始过了1-11,结果12-16打死抱错,而且是内存的一个tag被修改,直觉告诉我内存有问题,一看果真是预设值小了!]避免头节点重复存储,这个是常识,写代码的时候注意即可!
下面是我实现的代码,还是太长了,虽然勉强以32ms挤进了statistics 17/16[LLV,Orlando22都是我,LLV是拿来存储所有过关的代码的,没有马甲的意思,Orlando22里面原来提交的无效代码太多了]还是觉得代码功底不够,上面的代码最多就有我的一半长,惭愧!要加油了
 

Source Code

Problem: 1714

User: orlando22

Memory: 340K

Time: 32MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    #include <fstream>
    
    using namespace std;
    const int MAXN=510, MAXE=1550;
    typedef struct Edge{
    	int t; Edge* next;
    	bool hard;
    }Edge, *Pedge;
    Edge storage[MAXE];
    Pedge links[MAXN]={0};
    
    //linklist
    typedef struct LinkNode{
    	int n; LinkNode* next;
    }LinkNode, *PlinkNode;
    LinkNode lstorage[MAXN*2];
    int lid=0;
    class LinkList{
    public:
    	PlinkNode s, e;
    	LinkList():s(NULL),e(NULL){}
    	void front_insert(int n){
    		PlinkNode cur=lstorage+(lid++);
    		cur->n=n,cur->next=NULL;//clr shit!
    		if(!s) s=e=cur;
    		else{
    			PlinkNode tmp=s;s=cur;s->next=tmp;
    		}
    	}
    	void back_insert(int n){
    		PlinkNode cur=lstorage+(lid++);
    		cur->n=n,cur->next=NULL;
    		if(!s) s=e=cur;
    		else e=e->next=cur;
    	}
    	void clr(){s=e=NULL;}
    	LinkList& operator=(LinkList& _clone){//auto_ptr<U> MST->release
    		this->s=_clone.s,this->e=_clone.e;
    		_clone.clr();
    		return (*this);
    	}
    };
    LinkList lpath[MAXN];
    
    int n, k, p1, p2, cHards, bestHards=INT_MAX, pid=0, sid=0, pan=0;
    int leftc[MAXN]={0}, rightc[MAXN]={0}, anc[MAXN]={0},
    pre[MAXN]={0}, fol[MAXN]={0}, oid[MAXN]={0};//binary tree's structure
    bool redv[MAXN]={0}, cutTree[MAXN]={0};//vertex visited array
    
    //declaration
    void insert(int i, int j, bool hard);//insert into edges
    void color(int i, int j);
    int treeAdjust(int v);
    void bfs();//bfs to generate binary-tree, then decide p1 and p2.
    void visit_MAE(int i);
    void coreVisit();
    bool findIn(int I, const int& e, const bool& reverse);//I->e inner routine
    bool routineRed(int ox, int oy);
    void out_visit(int v);//to p2
    void front_insert(int i);
    void back_insert(int i);
    
    //UFS for connective components
    class UFS{
    private:
    	int set[MAXN], setk;
    	void clr(){memset((void*)set, 0, sizeof(set));}
    public:
    	UFS(){setk=0, clr();}
    	void sets(int k){
    		setk=k;
    		memset((void*)(set+1), 0xff, sizeof(int)*k);
    	}
    	int find(int i){
    		if(i<1||i>k) return -1;
    		int v=i;
    		while(set[i]>0) i=set[i];
    		while(i!=v){
    			int tmp=set[v];
    			set[v]=i;
    			v=tmp;
    		}
    		return i;
    	}
    	void unions(int i, int j){
    		if(i<1||i>k||j<1||j>k) return;
    		int t1=find(i), t2=find(j);
    		if(t1==t2) return;
    		int tmp1=set[t1], tmp2=set[t2];
    		if(tmp1<tmp2){
    			set[t1]=tmp1+tmp2;
    			set[t2]=t1;
    		}
    		else{
    			set[t2]=tmp1+tmp2;
    			set[t1]=t2;
    		}
    	}
    };
    UFS outer;
    
    //implemenation
    void insert(int i, int j, bool hard){
    	Pedge cur=links[i], pre=NULL;
    	for(;cur&&cur->t<j;pre=cur,cur=cur->next);
    	if(cur&&cur->t==j) return;
    	Pedge ct=storage+(sid++);
    	ct->t=j,ct->next=NULL,ct->hard=hard;
    	if(!pre){
    		links[i]=ct;
    		if(cur) ct->next=cur;
    	}
    	else{
    		pre->next=ct;
    		if(cur) ct->next=cur;
    	}
    	//for reverse
    	for(cur=links[j],pre=NULL;cur&&cur->t<i;pre=cur,cur=cur->next);
    	if(cur&&cur->t==i) return;
    	ct=storage+(sid++);
    	ct->t=i,ct->next=NULL,ct->hard=hard;
    	if(!pre){
    		links[j]=ct;
    		if(cur) ct->next=cur;
    	}
    	else{
    		pre->next=ct;
    		if(cur) ct->next=cur;
    	}
    }
    void bfs(){//2O(E)
    	redv[1]=true;
    	int size=0, cur=0; anc[size++]=1;//error
    	while(size<n){//1...n-1's tree
    	int v=anc[cur++];
    	for(Pedge ce=links[v]; ce; ce=ce->next){
    		if(!redv[ce->t]&&!(v<=k&&ce->t<=k)){//first one
    			if(!leftc[v]) leftc[v]=ce->t;
    			else if(!rightc[v]) rightc[v]=ce->t;
    			//push into queue
    			anc[size++]=ce->t;
    		}
    	}
    	redv[v]=true;
    	}
    	//adjust tree to guarantee the order
    	treeAdjust(1);
    }
    //adjust binary tree to fit the outer node order
    int treeAdjust(int v){
    if(v==0) return 0;//avoid loop
    int loid=treeAdjust(leftc[v]);
    int roid=treeAdjust(rightc[v]);
    if(loid==0&&roid==0) return oid[v];//leaf node
    if(loid<roid){//left > right
    	leftc[v]^=rightc[v], rightc[v]^=leftc[v], leftc[v]^=rightc[v];
    	loid=roid;
    }
    return loid;
    }
    void visit_MAE(int i){
    	cHards=0, pan=0, lid=0;//reset
    	outer.sets(k);
    	memset((void*)redv, 0, sizeof(redv)),
    		memset((void*)cutTree, 0, sizeof(cutTree)),
    		memset((void*)oid, 0xff, sizeof(oid));//for outer room
    	for(int k=1; k<MAXN; k++) lpath[k].clr();
    	//clrE();
    	Pedge forp1,forp2;
    	for(Pedge cur=links[1]; cur; cur=cur->next){
    		if(cur->t==p1) forp1=cur;
    		if(cur->t==p2) forp2=cur;
    	}
    	redv[1]=true; oid[1]=1, oid[p2]=1;//p2->fol[p2]:1, 1->fol[1]:p1;
    	outer.unions(1, p1), outer.unions(1, p2);
    	//for each M->A->E
    	if(!i){//both 1->p1 and p2->1 are external routine
    		if(forp1->hard) cHards++;
    		if(forp2->hard) cHards++;
    	redv[p1]=true, redv[p2]=true, color(1, p1), color(1, p2), pan+=2;
    		lpath[1].front_insert(p1), lpath[1].front_insert(1);
    	}
    	else if(i==1){//1->p1 outer
    		if(forp1->hard) cHards++;
    		redv[p1]=true, pan++, color(1, p1);
    		findIn(1, p2, false);//p2->1
    		//lpath[p2].front_insert(1);igonre the ending of 1
    		lpath[1].front_insert(p1), lpath[1].front_insert(1);
    	}
    	else{//p2->1 outer
    		if(forp2->hard) cHards++;
    		redv[p2]=true, pan++, color(1, p2);
    		findIn(1, p1, true);//1->p1
    		lpath[1].front_insert(1);
    	}
    	coreVisit();
    }
    bool findIn(int I, const int& e, const bool& reverse){//I->e
    	if(I==0) return false;
    	if(I==e) {redv[e]=true; return true;}
    	bool b1=findIn(leftc[I], e, reverse);
    	bool b2=findIn(rightc[I], e, reverse);
    	if(b1){//I->leftc[I]
    		redv[I]=true, cutTree[I]=true;//erase
    		if(reverse) lpath[1].front_insert(leftc[I]);
    		else lpath[p2].back_insert(leftc[I]);
    		color(I, leftc[I]); pan++;
    	}
    	if(b2){//I->rightc[I]
    		redv[I]=true, cutTree[I]=true;//erase
    		if(reverse) lpath[1].front_insert(rightc[I]);
    		else lpath[p2].back_insert(rightc[I]);
    		color(I, rightc[I]); pan++;
    	}
    	return b1||b2;
    }
    void color(int i, int j){
    for(Pedge cur=links[i]; cur; cur=cur->next){
    	if(cur->t==j){
    		if(cur->hard) cHards++; break;//only once for hard
    	}
    }
    }
    void coreVisit(){
    	//find the inner room I
    	while(pan<n&&cHards<bestHards){//red path=n, terminate!
    	int I=-1,x,y;
    	for(int i=1; i<n; i++){//highest ancetor inner room
    		if(!redv[anc[i]]&&anc[i]>k){ I=anc[i]; break; }
    	}
    	if(I!=-1){//having inner room for I
    		int cl=rightc[I]; color(I, cl), redv[I]=redv[cl]=true, pan++;
    		lpath[I].front_insert(I),lpath[I].front_insert(cl);
    		while(leftc[cl]&&rightc[cl]&&!cutTree[cl]){//not-leaf node
    			int tmp=leftc[cl]; cutTree[cl]=true;//cut-off branches
    			lpath[I].front_insert(tmp);
    			color(cl, tmp), redv[cl]=redv[tmp]=true, pan++;//dot color
    			cl=tmp;
    		}
    		oid[cl]=1,x=cl;
    		cl=leftc[I], color(I, cl), redv[cl]=true, pan++;
    		lpath[I].back_insert(cl);
    		while(leftc[cl]&&rightc[cl]&&!cutTree[cl]){
    			int tmp=rightc[cl]; cutTree[cl]=true;
    			lpath[I].back_insert(tmp);
    			color(cl, tmp), redv[cl]=redv[tmp]=true, pan++;
    			cl=tmp;
    		}
    		y=cl;lpath[x]=lpath[I];
    		outer.unions(x, y), oid[x]=1;
    		}
    	else{//don't have inner room, find outer-room
    		int x=-1;
    		for(int i=2; i<=k; i++) if(oid[i]==-1) x=i;
    		//find (x->fol[x])
    		lpath[x].back_insert(x),lpath[x].back_insert(fol[x]);//x->fol[x], just need fol[k]
    		if(outer.find(x)!=outer.find(fol[x])){
    			color(x, fol[x]), oid[x]=1, pan++;
    		}
    	}
    	}
    }
    void out_visit(int v, int i){
    //copy linklist into pre
    int cpre=0; pre[cpre]=1, i=1; 
    for(int k=1; i; k=fol[k]){
    	if(k==p2) i=0;
    	if(lpath[k].s!=NULL){//listlink is not null
    		for(PlinkNode cur=lpath[k].s; cur; cur=cur->next){
    			if(pre[cpre]!=cur->n) pre[++cpre]=cur->n;
    		}
    	}
    }
    }
    
    int main()
    {
    	//implementation
    	cin>>n, cin>>k;
    	int len=3*n/2, s, e, tag;
    	for(int i=0; i<len; i++){
    		cin>>s, cin>>e, cin>>tag;
    		//decide outer order
    		if(s<=k&&e<=k){
    			if(!pre[s]) pre[s]=e;//for e
    			else if(!fol[s]) fol[s]=e;
    			if(!pre[e]) pre[e]=s;//for s
    			else if(!fol[e]) fol[e]=s;
    		}
    		insert(s, e, tag==1);
    	}
    	//generate outer order for pre[i] and fol[i], also for oid
    	int id=1;
    	if(fol[1]<pre[1]) pre[1]^=fol[1],fol[1]^=pre[1],pre[1]^=fol[1];
    	p1=fol[1],p2=pre[1]; oid[1]=id++;
    	for(int i=p1, pp=1; i!=1; pp=i, i=fol[i]){
    		if(pre[i]!=pp) pre[i]^=fol[i],fol[i]^=pre[i],pre[i]^=fol[i];
    		oid[i]=id++;
    	}
    	//find p1 and p2
    	bfs();
    	for(int i=0; i<3; i++){
    		visit_MAE(i);
    		if(cHards<bestHards) bestHards=cHards, out_visit(p1, i);//start with p1->p2
    	}
    	//output for pre[1...]
    	for(int i=0; i<n; i++){
    		cout<<pre[i];
    		if(i!=n-1) cout<<" ";
    	}
    	cout<<endl;
    	return 0;
    }

Advertisements