• 完全失败了,今天进入了一个误区,qsort()对于指针链表排序居然存在不稳定的情况[算法退化,我倒,这个名字好],代码如下,去看了MS的帮助,说了等于白说!耽搁了我3个多小时,严重拖延了计划!

#include <time.h>
#include <stdlib.h>

using namespace std;

const int MAXN=22, MAXE=500;
typedef struct Edge{
 int i, j, value;
}Edge, *Pedge;
Edge storage[MAXE];
Pedge links[MAXE];//for heapsorting

int eid=0,lsize=0;

//int cmp(const void* p1, const void* p2){
// return (*(Pedge*)p1)->value>(*(Pedge*)p1)->value;
//}
int cmp(const void* p1, const void* p2){
 return ((Pedge)p1)->value>((Pedge)p2)->value;
}

int _tmain(int argc, _TCHAR* argv[])
{
 srand((unsigned int)time(0));
 int min=1, max=400;
 for(int i=0; i<400; i++){
  storage[eid].i=i, storage[eid].j=i-1, storage[eid].value=(double)rand()/(1+RAND_MAX)*(max-min)+min;
  links[lsize++]=storage+(eid++);
 }
 //sort(links, links+lsize, cmp);
 qsort((void*)links, lsize, sizeof(Pedge*), cmp);
 for(int i=1; i<lsize; i++){
  cout<<links[i]->value<<" ";
  assert(links[i]->value>=links[i-1]->value);//肯定报错,这个算法来自大牛Horae,不过不像STL的sort,heap是稳定算法,总之就是挨球!
 }
 system("pause");
 return 0;
}

  • k度限制生成树:对于生成树中的一个顶点V0存在度的要求,比如最大度不超过k之类的!理论可以参见《算法艺术入门》上的描述!这里总要给出算法描述,算法框架,严格基于框架实现一个BFS的“差额最小添删算法”。
1。算法描述:
  • 先做去V0点操作,在剩下的顶点基础上,基于各个连通块实现Prim或Kruskal算法,以求出各个连通块,由于Kruskal算法是基于边权的,因此可以用一次快排实现,不需要堆的支持![考虑到用堆,为了简化代码必然要引用push_heap,pop_heap的算法,反而影响性能,因此我用了边权的kruskal算法]。具体实现可以在整个图中进行操作,只需要控制边加入时,不能与V0相连即可!
  • 从V0引出一最小边到每个连通块以形成一个m度最小树
  • 然后工作要基于一个理论,也就是说对于原图E,删除一条不在除V0最小生成树上的边,E-(i,j)的最小限制度树也是E的最小限制度树!这里要敲下,写代码的时候出了错:我们添加一条(0,k)后,要删除相应的环上的最大权边->转化下,我们得到,对于一个在E而不T的与V0相连的顶点,但BFS的父亲不是V0,可以加入到T,并且可以用简单的DP求出其BFS路上最大权边!这样cost(0,k)-cost(DP边)一定是V0的添一度生成树的最小生成树。[写的太长了,精神重要]
2。算法框架:
算法主框架:
K-Degree-MST(G,w,v0,k){
      T<-Min-Degree-MST(G,w,v0,m)//连通块最小生成树
      if(k<m) then return 无k度限制生成树
      while(k!=m){
           do T<-EXTEND-Degree(G,w,v0,T)//差额最小添删操作
           if T不存在 then return 无k度限制生成树//这里要利用lrj的结论,T什么叫不存在,如果一个添边的T比原来的树代价还大,那就可以不添,直接退出
           m<-m+1
      }
}
 
最小度M生成树框架:
Min-Degree-MST(G,w,v0,*m){//这个框架比较挨球,应该改的更好实现的,可以看我的实现代码
     G'<-G/{V0}
     m<-G’的连通分量数目
     T<-空集
     for S<-G’中的每个连通分量
          do T<-T+MST-kruskal(G,w)
               根据权非递减序对G中与V0关联的边排序
               for 每条边(v0, u)<-E,按w的非递减序排列
                      do if v0与u在T中不连通
                           then T<-T+{v0, u}
}
 
差额最小添删操作框架:注意DP的实现方法
Extend-Degree(G,w,v0,T){
      for u<-V
         do best[u]<–负无穷大, bestChoice[u]<-NULL
      以v0为根进行宽搜,定义father[v]为v在搜索树上的父亲
      for v<-V+(-v0) 按照宽搜序列  //queue保存复用
           do if father[u]!=v0
                then if best[father[u]] > w(u, father[u])
                       then best[u]<-best[father[u]], bestchoice[u]<-bestchoice[father[u]]
                       else best[u]<-w(u,father[u]), bestchoice[u]<-(u, father[u])
      EXCHANGE=null
      for (v0,u)<- E/T 且father[u]!=v0//注意这个条件,避免删环出错
            do if w(v0, u)-best[u]<Exchage.cost
                 then Exchange<-(+(v0, u), -bestchoice[u])
                 then 对T施以Exchange的可行交换
}
 
3。代码实现:光是理论是没用的,看一道题目Picnic Planning 
这道题目而言,可以用更少的代码来实现,这是肯定的,甚至多用几个数组,然后用数组处理都可以得到结论,为了给以后留个清晰的框架,这里还是多严格按照书上框架做的,代码如下,和上面的框架一致。关键地方加了标注:
版本1:基于数组的实现,qsort处理边权

Source Code

Problem: 1639

User: orlando22

Memory: 312K

Time: 47MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    #include <string>
    #include <map>
    
    //pku 1639 Pinic planning
    //The maximum number of brothers will be 20 ,
    //the maximum length of any name will be 10 characters.
    //You may assume that there is a path from every brother's house
    //to the park and that a solution exists for each problem instance.
    //These roads will all be 2-way roads, and dist will always be positive.
    
    using namespace std;
    const int MAXN=22, MAXE=500;
    typedef struct Edge{
        int i, j, value;
    }Edge, *Pedge;
    Edge storage[MAXE];
    
    Pedge links[MAXE], tov0[MAXN];
    bool inCCs[MAXN]={0};//for heapsorting
    int n, nodes, k, eid=0, lid=0, vid=0, minCost=0, lsize=0;
    int EG[MAXN][MAXN]={0}, TG[MAXN][MAXN]={0};
    int bestCost[MAXN]={0}, bestChoice[MAXN]={0},
        father[MAXN]={0}, color[MAXN]={0}, queue[MAXN]={0};
    
    //UFS implementation
    class UFS{
    private:
        int n[MAXN], setn;
    public:
        UFS(){clr();}
        void clr(){memset((void*)n, 0, sizeof(n));}
        void setk(int k){
            this->setn=k; memset((void*)(n+1), 0xff, sizeof(int)*this->setn);
        }
        int find(int v){
            if(v<=0||v>setn) return -1;
            int p=v;
            while(n[v]>0) v=n[v];
            while(p!=v){
                int tmp=n[p];
                n[p]=v;
                p=tmp;
            }
            return v;
        }
        void unions(int i, int j){
            if(i<=0||i>setn||j<=0||j>setn) return;
            int v1=find(i), v2=find(j);
            if(v1==v2) return;
            int tmp1=n[v1], tmp2=n[v2];
            if(tmp1<tmp2){
                n[v1]=tmp1+tmp2;
                n[v2]=v1;
            }
            else{
                n[v2]=tmp1+tmp2;
                n[v1]=v2;
            }
        }
        int pkey(){
            int count=0;
            for(int i=1; i<setn+1; i++)
                if(n[i]<0) count++;
            return count;
        }
    };
    UFS _u;
    //heap implementation
    int cmp(const void* p1, const void* p2){
        return ((Pedge)p1)->value>((Pedge)p2)->value;//true, put it on the heads, so decending order
    }
    int inline popofH(Pedge *es, int& size){
        if(size>=1){
            int min=INT_MAX, j=size-1;
            for(int i=0; i<size; i++){
                if(es[i]->value<min) min=es[i]->value, j=i;
            }
            if(j!=size-1){
                if(es[j]->value!=es[size-1]->value){
                    Pedge tmp=es[j]; es[j]=es[size-1]; es[size-1]=tmp;
                }
            }
            size--;
        }
        return size;
    }
    //declaration
    void insertE(int i, int j, int value);
    void insert_T(int i, int j);
    void remove_T(int i, int j);
    //k Tree's generation
    int KdegMST();//k restricted tree
    int MinDegMST();//generate minTree with min connective components
    bool ExtendDeg();//extensive method
    
    //implementation
    void inline insertE(int i, int j, int value){
        EG[i][j]=EG[j][i]=value;
        storage[eid].i=i, storage[eid].j=j, storage[eid].value=value;
        links[lsize]=storage+eid;
        lsize++,eid++;
    }
    void inline insert_T(int i, int j){
        TG[i][j]=TG[j][i]=1;
    }
    void inline remove_T(int i, int j){
        TG[i][j]=TG[j][i]=0;
    }
    int inline costforE(int i, int j){
        if(EG[i][j]) return EG[i][j];
        return -1;
    }
    
    int KdegMST(){
        int m=MinDegMST();
        if(m>k) return -1;
        while(m!=k){
            if(!ExtendDeg()) return minCost;
            m++;
        }
        //get min cost return;
        return minCost;
    }
    int MinDegMST(){//minHeap code, need to be reviewed!
        _u.setk(nodes);
        int tovs=0, tmp, t1, t2;
        int en=0;//until n-1 nodes in minTree
        do{//多连通块的实现
            tmp=popofH(links, lsize), t1=links[tmp]->i, t2=links[tmp]->j;
            if(t1!=1&&t2!=1&&_u.find(t1)!=_u.find(t2)){
                _u.unions(t1, t2), minCost+=links[tmp]->value;
                insert_T(t1, t2),insert_T(t2, t1);
            }
            else if(t1==1||t2==1){//for all edges linked to v0=1
                tov0[tovs++]=links[tmp];
            }
        }while(lsize>=1);//all edges have been removed, just en=nodes-1 is not enough
        //pop-up all edges links to v0=1, except 1 vertex
        int ccs=_u.pkey();
        while(tovs!=0){//pop-up element from heap of tov0=0, only one block圈顶实现
            tmp=popofH(tov0, tovs), t1=tov0[tmp]->i, t2=tov0[tmp]->j;
    		if(TG[t1][t2]==0&&_u.find(t1)!=_u.find(t2)){//only one block left, so it's right!
                _u.unions(t1, t2);insert_T(t1, t2),insert_T(t2, t1);
                minCost+=tov0[tmp]->value;
            }
        }
        return ccs-1;
    }
    
    bool ExtendDeg(){//core implementation for "remove-add logic" BFS以及最优权实现
        memset((void*)bestCost,0xff, sizeof(int)*(nodes+2));
        memset((void*)bestChoice,0xff, sizeof(int)*(nodes+2));
        memset((void*)father,0, sizeof(int)*(nodes+2));
        memset((void*)color,0, sizeof(int)*(nodes+2));
        memset((void*)queue,0, sizeof(int)*(nodes+2));
        //bfs from v0=1 to generate tree
        int size=0, cid=0;
        color[1]=1, queue[size++]=1;
        while(cid<size){
            int current=queue[cid++];
            for(int cur=1; cur<nodes+1; cur++){
                if(cur==current) continue;
                if(TG[current][cur]&&color[cur]==0){
                    father[cur]=current; queue[size++]=cur;
                    color[cur]=1;//dot-gray
                }
            }
            color[current]=1;//dot-black
        }
        for(int i=1; i<nodes; i++){//from queue[1] to queue[nodes-1]
            int u=queue[i];
            if(father[u]!=1){
                int w=costforE(u, father[u]);//in T must in E
                if(bestCost[father[u]]>w)
                    bestCost[u]=bestCost[father[u]], bestChoice[u]=bestChoice[father[u]];
                else bestCost[u]=w, bestChoice[u]=father[u];//father[u]->u
            }
        }
        int vadd=-1, vre1=-1, vre2=-1, cost=INT_MAX;
        for(int cur=2; cur<nodes+1; cur++){//(t, 1) in E not in T, and father[t]!=1
            if(EG[1][cur]!=0&&TG[1][cur]==0){
                if(father[cur]!=1){
                    int w=EG[1][cur];
                    if(w-bestCost[cur]<cost)
                        cost=w-bestCost[cur],vadd=cur,vre1=father[cur],vre2=cur;
                }
            }
        }
        if(vadd==-1||cost>=0) return false;//lrj's description
        minCost+=cost;
        insert_T(1, vadd);remove_T(vre1, vre2);
        return true;
    }
    
    int main()
    {
        //implementation
        int s, t, value, id=1; string str;
        map<string, int> dic; dic.insert(make_pair("Park", id++));
        map<string, int>::iterator it;
        cin>>n;
        for(int i=1; i<n+1; i++){
            cin>>str;
            if((it=dic.find(str))!=dic.end()) s=it->second;
            else{
                s=id++;
                dic.insert(make_pair(str, s));
            }
            cin>>str;
            if((it=dic.find(str))!=dic.end()) t=it->second;
            else{
                t=id++;
                dic.insert(make_pair(str, t));
            }
            cin>>value;
            insertE(s, t, value);
        }
        cin>>k;
        nodes=id-1;
        int amount=0;
        if(nodes>1) amount=KdegMST();
        cout<<"Total miles driven: "<<amount<<endl;
        return 0;
    }
  • 基于链表实现:有个地方有错,呵呵,只有我自己看出来了,懒得改了!这个代码的核心是利用稳定排序进行处理,pop_heap,有兴趣可以研究下,个人估计在一些极端数据条件下表现应该更好!天大的系统怎么搞得,写来写去都0MS,俄,搞不懂,难道比我本地还快!gprof都0.01s

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <algorithm>

//pku 1639 Pinic planning
//The maximum number of brothers will be 20 ,
//the maximum length of any name will be 10 characters.
//You may assume that there is a path from every brother's house
//to the park and that a solution exists for each problem instance.
//These roads will all be 2-way roads, and dist will always be positive.

using namespace std;
const int MAXN=22, MAXE=500;
typedef struct Edge{
    int i, j, value;
}Edge, *Pedge;
typedef struct LEdge{
    Pedge e; LEdge *next;
}LEdge, *Pledge;
typedef struct VEdge{
    int i; VEdge *next;
}VEdge, *Pvedge;
Edge storage[MAXE];
VEdge vstorage[MAXE];
LEdge lstorage[MAXE];

Pledge links[MAXE]={0};
Pedge tov0[MAXN]={0}, es[MAXE]={0};//orignal graph structure
Pvedge t[MAXN]={0};//mapping graph
int bestCost[MAXN]={0}, bestChoice[MAXN]={0},
    father[MAXN]={0}, color[MAXN]={0}, queue[MAXN]={0};
int n, nodes, k, eid=0, lid=0, vid=0, minCost=0;

//UFS implementation
class UFS{
private:
    int n[MAXN], setn;
public:
    UFS(){clr();}
    void clr(){memset((void*)n, 0, sizeof(n));}
    void setk(int k){
        this->setn=k; memset((void*)(n+1), 0xff, sizeof(int)*this->setn);
    }
    int find(int v){
        if(v<=0||v>setn) return -1;
        int p=v;
        while(n[v]>0) v=n[v];
        while(p!=v){
            int tmp=n[p];
            n[p]=v;
            p=tmp;
        }
        return v;
    }
    void unions(int i, int j){
        if(i<=0||i>setn||j<=0||j>setn) return;
        int v1=find(i), v2=find(j);
        if(v1==v2) return;
        int tmp1=n[v1], tmp2=n[v2];
        if(tmp1<tmp2){
            n[v1]=tmp1+tmp2;
            n[v2]=v1;
        }
        else{
            n[v2]=tmp1+tmp2;
            n[v1]=v2;
        }
    }
    int pkey(){
        int count=0;
        for(int i=1; i<setn+1; i++)
            if(n[i]<0) count++;
        return count;
    }
};
UFS _u;
//heap implementation
int cmp(const void* p1, const void* p2){
    return ((Pedge)p1)->value>((Pedge)p2)->value;
}
void pushtoH(Pedge *es, int size){
    push_heap(es, es+size, cmp);
}
int popofH(Pedge *es, int& size){
    if(size>=1){
        pop_heap(es, es+size, cmp);
        size--;
    }
    return size;
}

//declaration
void insert(int i, int j, int value);
void insert_T(int i, int j);
void remove_T(int i, int j);
bool inT(int i, int j);
//k Tree's generation
int KdegMST();//k restricted tree
int MinDegMST();//generate minTree with min connective components
bool ExtendDeg();//extensive method

//implementation
void insert(int i, int j, int value){
    if(i==j) return;
    if(i>j) i^=j,j^=i,i^=j;
    Pedge cur=storage+(eid++); 
    cur->i=i,cur->j=j,cur->value=value;
    //insert into links[i]
    Pledge ci=lstorage+(lid++); 
    ci->e=cur,ci->next=NULL;//at the tail
    Pledge cl=links[i];
    for(;cl&&cl->next;cl=cl->next);
    if(!cl) links[i]=ci;
    else cl->next=ci;
    //insert into links[j]
    ci=lstorage+(lid++);
    ci->e=cur,ci->next=NULL;
    cl=links[j];
    for(;cl&&cl->next;cl=cl->next);
    if(!cl) links[j]=ci;
    else cl->next=ci;
}
void insert_T(int i, int j){
    Pvedge cur=vstorage+(vid++);
    cur->i=j, cur->next=NULL;
    Pvedge cl=t[i];
    for(;cl&&cl->next;cl=cl->next);
    if(!cl) t[i]=cur;
    else cl->next=cur;
    //reverse edge
    cur=vstorage+(vid++);
    cur->i=i, cur->next=NULL;
    cl=t[j];
    for(;cl&&cl->next;cl=cl->next);
    if(!cl) t[j]=cur;
    else cl->next=cur;
}
void remove_T(int i, int j){
    Pvedge cur=t[i], pre=NULL;
    for(;cur;pre=cur,cur=cur->next)
        if(cur->i==j) break;
    if(!cur) return;//no exists
    if(!pre) t[i]=cur->next;
    else pre->next=cur->next;
    cur=t[j], pre=NULL;
    for(;cur;pre=cur,cur=cur->next)
        if(cur->i==i) break;
    if(!cur) return;//no exists
    if(!pre) t[j]=cur->next;
    else pre->next=cur->next;
}
int costforE(int i, int j){
    for(Pledge cur=links[i]; cur; cur=cur->next){
        if(cur->e->i==i&&cur->e->j==j) return cur->e->value;
        else if(cur->e->i==j&&cur->e->j==i) return cur->e->value;
    }
    return -1;
}
bool inT(int i, int j){
    for(Pvedge cur=t[i]; cur; cur=cur->next)
        if(cur->i==j) return true;
    return false;
}

int KdegMST(){
    int m=MinDegMST();
    if(m>k) return -1;
    while(m!=k){
        if(!ExtendDeg()) return minCost;
        m++;
    }
    //get min cost return;
    return minCost;
}
int MinDegMST(){//minHeap code, need to be reviewed!
    _u.setk(nodes);
    int size=0, tovs=0, tmp, t1, t2;
    for(int i=0; i<eid; i++) es[i]=storage+i, size++, pushtoH(es, size);
    int en=0;//until n-1 nodes in minTree
    do{
        tmp=popofH(es, size), t1=es[tmp]->i, t2=es[tmp]->j;
        if(t1!=1&&t2!=1&&_u.find(t1)!=_u.find(t2)){
            _u.unions(t1, t2), minCost+=es[tmp]->value;
            insert_T(t1, t2),insert_T(t2, t1);
        }
        else if(t1==1||t2==1){//for all edges linked to v0=1
            tov0[tovs++]=es[tmp]; pushtoH(tov0, tovs);
        }
    }while(size>=1);
    //pop-up all edges links to v0=1
    int ccs=_u.pkey();
    while(tovs!=0){//pop-up element from heap of tov0
        tmp=popofH(tov0, tovs), t1=tov0[tmp]->i, t2=tov0[tmp]->j;
        if(_u.find(t1)!=_u.find(t2)){
            _u.unions(t1, t2);insert_T(t1, t2),insert_T(t2, t1);
            minCost+=tov0[tmp]->value;
        }
    }
    return ccs-1;
}

bool ExtendDeg(){//core implementation for "remove-add logic"
    for(int i=1; i<nodes+1; i++) bestCost[i]=-1, bestChoice[i]=-1, color[i]=0;
    //bfs from v0=1 to generate tree
    int size=0, cid=0;
    color[1]=1, queue[size++]=1;
    while(cid<size){
        int current=queue[cid++];
        for(Pvedge cur=t[current]; cur; cur=cur->next){
            if(color[cur->i]==0){
                father[cur->i]=current; queue[size++]=cur->i;
                color[cur->i]=1;//dot-gray
            }
        }
        color[current]=1;//dot-black
    }
    for(int i=1; i<nodes; i++){//from queue[1] to queue[nodes-1]
        int u=queue[i];
        if(father[u]!=1){
           int w=costforE(u, father[u]);//in T must in E
            if(bestCost[father[u]]>w)
                bestCost[u]=bestCost[father[u]], bestChoice[u]=bestChoice[father[u]];
            else bestCost[u]=w, bestChoice[u]=father[u];//father[u]->u
        }
    }
    int vadd=-1, vre1=-1, vre2=-1, cost=INT_MAX;
    for(Pledge cur=links[1]; cur; cur=cur->next){//(t, 1) in E not in T, and father[t]!=1
        if(!(inT(cur->e->i, cur->e->j))){
            int t=(cur->e->i==1?cur->e->j:cur->e->i);
            if(father[t]!=1){
                int w=cur->e->value;
                if(w-bestCost[t]<cost) cost=w-bestCost[t], vadd=t, vre1=father[t], vre2=t;
            }
        }
    }
    if(vadd==-1||cost>=0) return false;
    minCost+=cost;
    insert_T(1, vadd);remove_T(vre1, vre2);
    return true;
}

int main()
{
    //implementation
    int s, t, value, id=1; string str;
    map<string, int> dic; dic.insert(make_pair("Park", id++));
    map<string, int>::iterator it;
    cin>>n;
    for(int i=1; i<n+1; i++){
        cin>>str;
        if((it=dic.find(str))!=dic.end()) s=it->second;
        else{
            s=id++;
            dic.insert(make_pair(str, s));
        }
        cin>>str;
        if((it=dic.find(str))!=dic.end()) t=it->second;
        else{
            t=id++;
            dic.insert(make_pair(str, t));
        }
        cin>>value;
        insert(s, t, value);
    }
    cin>>k;
    nodes=id-1;
    cout<<"Total miles driven: "<<KdegMST()<<endl;

    return 0;
}
  • 睡觉了,明天加油把最优比率树,以及最短路的前面扫掉,LLV泣血中!

Advertisements