• 图论的部分继续前进!

1.   Wandering flea trainers [P287] 知识点:特殊的同构图判定算法![评价:图的一道基础综合题,很全面]

核心算法如下:

  • 基于DFS的圈以及连通分量查找算法;
  • 对于圈上的每一个顶点,基于其消圈反向边来生成圈外节点括号序列;[环状内向树的括号序列,这里要说明下:如果两个圈的大小相同,那么我们就要继续比较每一个顶点是否等价,一个简单的思路是以每个顶点为根生成一个内向树,这个很好理解。但可以简化一步,我们可以只比较两个顶点在圈外的内向树是否等价,原因很简单,圈长度相同且首尾相连,完全没有比较的必要!]
  • 连通分量的圈等价比较,这个用一个年历回溯可以搞定不用多说!
  • 一个细节:括号序列怎么生成?如果用string的话,比较简单,但在极限条件下,性能不好;正在思考中!

基本数据结构:

  • 正向边用一维数组即可,反向边用邻接表处理;连通分量[圈]用一个一维邻接表数组[STL的list即可,为练习目的还是自己写吧]
  • 对于圈中节点可以用括号序列来处理长度,数据结构要考虑下!

编程结果:通过了测试用例1-8,9和10数据规模太大,string果真爆栈了,IRJ真的是句句经典,估摸着有人也遭过。这道题目很经典,非常符合彭牛同学说的算法问题分解原则,每个知识点都不难[注意查圈的算法,这个容易错],但组合起来的代码容易叫人晕菜!除了这些,以下是我犯的错:

  • linkedlist的插入操作,居然忘了修改尾指针,e=e->next=XXX;程序一长就写的太随性,这个习惯不好!要注意!
  • string* t[MAXN]这个的排序是什么,qsort((void*)t, MAXN, sizeof(string*), cmp)->(*(string**)a)->XXX();//基本功要注意
  • 对于年历回溯的一个变体bool used[MAXN]中,可以加上一个DP table来避免重复计算!
  • 最大的问题在这里,在动态构造seq[MAXN],圈上定点的内向树序列时,字符串存放指针居然用了全局数组,在递归过程中无法保证数据一致性!
  • 要继续改进的地方:string要改成0-1串,这个可能要用位图4000/32->120的长度来处理,还是不满意,等把后面的过了在返过来改进吧!时不我待

代码如下:

#include <iostream>
#include <string>
#include <fstream>

using namespace std;
//1<=d<=100, test case; 1<=n<=2000, coins
const int MAXN=4001, NEXT=2000;//for reverse node

//structure for graph
int n, ed[MAXN], nv, id=0, s1, s2, cn;//direct edge
typedef struct Edge{
    int t;
    Edge *next;
}Edge, *Pedge;
Pedge er[MAXN];//reverse edge
Edge storage[MAXN];

//for connectivity
template<typename T> class linklist;
template<typename T> class linknode;
//implementation before declaration, linklist<int> could be judged about the size.
template<typename T> class linknode{
public:
    T item; linknode *next;
    explicit linknode(T _item): item(_item), next(NULL){}
};

template<typename T> class linklist{
public:
    linknode<T> *s,*e;
    linklist():s(NULL),e(NULL){}
    void insert(T _item){
        if(e) e=e->next=new linknode<T>(_item);//modify the last item
        else s=e=new linknode<T>(_item);
    }
    void clr(){
        for(linknode<T> *p=s, *b=NULL; p; p=b){
            b=p->next; delete p;
        }
        s=e=NULL;
    }
    ~linklist(){clr();}
};

bool inLoop[MAXN];
int con[MAXN], conSize[MAXN], used[MAXN], rb[MAXN], rt;//connected compoent and its size; rb and rt will clr for each time
linklist<int> circle[MAXN];

//for sequence of each node
string seq[MAXN];
char vm[MAXN][MAXN];

//declaration, from i->j
void insert(Edge* &A, int j);
bool solution();
void connect(int start, int end);//calculation for connective compoent and circle for each item
int dfs_forward(int v);
void dfs_backward(int v);
void InTreeSeq(int v);//InTreeSeq to generate match pairs
int cmp(const void* s1, const void* s2);
bool match(int i);//dfs comparation [1…s1] with [s1+1…s2]
bool equal(int i, int j);//compare the brackets sequence of i, and j

//implemenation
void insert(Pedge &A, int j){//good implementation for A*&;
    if(A){ Pedge t=A;A=&storage[id];A->next=t; }
    else{ A=&storage[id];A->next=NULL; }
    storage[id++].t=j;
}
//first for dfs and dfs_back to find loop and circle
bool solution(){
    connect(1, nv), s1=cn;//connective compoent
    connect(1+NEXT, nv+NEXT), s2=cn;//注意连通分量的反向查找
    if(s1!=s2-s1) return false;
    //for each circle to calculate sequences of seq[i] [1…cn]
    for(int i=1; i<=cn; i++){//for each node in the circle
        for(linknode<int> *cur=circle[i].s; cur; cur=cur->next){
            InTreeSeq(cur->item);//内向树括号序列的处理
        }
    }
    for(int i=1; i<=s1; i++) used[i]=i+s1;
    return match(1);//from [1…s1] with [s1+1…cn]
}
void connect(int start, int end){
    //for each connective compoent, dfs to find the current con[i], i->[start…end]
    //dfs_forward to find loop of forward edges, dfs_backward to find all connective vertexs
    for(int i=start; i<=end; i++){
        if(!con[i]){
            rt=0;conSize[++cn]=0;
            dfs_forward(i);
            for(int j=1; j<=rt; j++) dfs_backward(rb[j]);
        }
    }
}
int dfs_forward(int v){
    //core implementatino for forward_algorithm, cn is current connective component
    con[v]=cn,rb[++rt]=v;
    int t=ed[v];
    if(!con[t]){
        int ret=dfs_forward(t);
        if(ret){//on the way to loop
            conSize[cn]++,circle[cn].insert(v),inLoop[v]=true;
            if(v==ret) return 0;//already close loop
            return ret;//return frontier返回最前端顶点,若回到v点则表示圈闭合
        }
        else return 0;//pass back to top
    }
    else{
        conSize[cn]++,circle[cn].insert(v),inLoop[v]=true;
        if(v==t) return 0;//close loop
        return t;//loop frontier
    }
}
void dfs_backward(int v){
    con[v]=cn;
    for(Pedge cur=er[v]; cur; cur=cur->next){
        if(!con[cur->t]) dfs_backward(cur->t);
    }
}
void InTreeSeq(int v){//internal tree with v as the top node递归生成内向树括号序列
    int l=0;
    string** substr=new string*[conSize[con[v]]+2];
    seq[v]+='(‘;
    //back to substr in order to sort all sk by size();
    for(Pedge cur=er[v]; cur; cur=cur->next){
        if(inLoop[cur->t]) continue;//out of Loop strings
        InTreeSeq(cur->t);
        substr[l++]=&seq[cur->t];
    }
    qsort((void*)substr, l, sizeof(string*), cmp);
    //sort by order, OK let link together
    for(int i=0; i<l; i++) seq[v]+=(*substr[i]);
    seq[v]+=’)’;
    delete[] substr;
}
inline int cmp(const void* s1, const void* s2){
    return (*(string**)s1)->compare(*(*((string**)s2)));
}
bool match(int v){//for dfs
    if(v>s1) return true;
    for(int i=v; i<=s2; i++){//compare k with i [s1+1…s2]
        if(equal(v, used[i])){//v, i
            if(used[i]!=used[v]) used[i]^=used[v],used[v]^=used[i],used[i]^=used[v];
            bool ret=match(v+1);
            if(used[i]!=used[v]) used[i]^=used[v],used[v]^=used[i],used[i]^=used[v];
            if(ret) return true;//just found one is enough
        }
    }
    return false;
}
bool equal(int i, int j){
    if(conSize[i]!=conSize[j]) return false;
    if(vm[i][j]!=-1){
        if(vm[i][j]) return true;
        return false;
    }
    linknode<int> *ik, *jk, *ci;//compare linklist’s brackets
    for(ik=circle[i].s; ik; ik=ik->next){
        ci=ik;//current comparion, that’s a loop
        for(jk=circle[j].s; jk; jk=jk->next){//compare jk with ci
            int p1=ci->item, p2=jk->item;
            if(seq[p1]!=seq[p2]) break;
            //OK,for ci’s next
            if(!(ci=ci->next)) ci=circle[i].s;//if loop to end, then back to top
        }
        if(!jk) {vm[i][j]=1; return true;}
    }
    vm[i][j]=0;
    return false;
}

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input1.txt");//input1.txt="pch9.in","pch10.in"
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    int t;
    cin>>n;
    for(int i=0; i<n; i++){
        id=0,cn=0;//storage and connective compoent count [cn]
        cin>>nv;
        for(int j=1; j<nv+1; j++){
            cin>>t;
            ed[j]=t,insert(er[t], j),string().swap(seq[j]);
        }
        for(int j=1; j<nv+1; j++){
            cin>>t;
            ed[j+NEXT]=t+NEXT,insert(er[t+NEXT], j+NEXT),string().swap(seq[j+NEXT]);
        }
        //clr
        memset((void*)inLoop, 0, sizeof(inLoop)),
        memset((void*)used, 0, sizeof(used)),
        memset((void*)vm, 0xff, sizeof(vm)),
        memset((void*)con, 0, sizeof(con));

        if(solution()) cout<<"T"<<endl;
        else cout<<"N"<<endl;

        for(int i=1; i<=s2; i++) circle[i].clr();//clear connective compoents
        memset((void*)er, 0, sizeof(er));
        memset((void*)ed, 0, sizeof(ed));
    }

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

2.   Round__Trip[P287] 知识点:图的收缩以及桥查找算法

CEOI2001,这个算法有点问题,我疑心是简单路径的问题,没有过掉Trip5的测试用例,问题在简单路径是要求路径上无环吧!怎么做呢?疑惑中,不过桥的算法是过了的!没有online judge,没提起研究的兴趣!下面是简单路径有错的代码。

#include <iostream>
#include <fstream>

using namespace std;
const int MAXV=1001, MAXE=200000;
typedef struct Edge{
    int t;
    bool bridge,avail;
    Edge* next;
}Edge, *Pedge;
Pedge vertexs[MAXV];
Edge edges[MAXE];
int s, d, v, e, ce=0, bc=0;
int color[MAXV]={0}, depth[MAXV], ancestor[MAXV], path[MAXV];//vertexs
bool reachable=false, stop=false;
enum{white=0,gray=1,black=2};

//declaration
void dfs(int i, int father, int deep);//find all of bridges and s<->d?
void travel(int i, int steps, const int& dest);
void insert(int i, int j);//insert i->j and j->i;
void disable(int i, int j);//for i->j and j->i;
bool setbridge(int i, int j);

//implementation
void dfs(int i, int father, int deep){
    color[i]=gray,ancestor[i]=deep,depth[i]=deep;
    for(Pedge cur=vertexs[i]; cur; cur=cur->next){
        //if cur->t is gray and cut->t!=father not directly linked
        if(cur->t!=father&&color[cur->t]==gray){
            if(depth[cur->t]<ancestor[i]) ancestor[i]=depth[cur->t];
        }
        if(color[cur->t]==white){
            if(cur->t==d) reachable=true;
            dfs(cur->t, i, deep+1);
            if(ancestor[cur->t]<ancestor[i]) ancestor[i]=ancestor[cur->t];
            //check bridge and cut
            if(ancestor[cur->t]>depth[i]){
                if(!cur->bridge) cur->bridge=true,setbridge(cur->t, i);
            }
        }
    }
    color[i]=black;
}
void travel(int i, int steps, const int& dest){//from s->d, start not step already!
    if(stop) return;
    if(i==dest){//reach the last
        path[steps]=dest;bc=0;
        if(dest==d){
            for(int c=1; c<steps+1; c++)//path[c], path[c-1]
                disable(path[c-1], path[c]);
            cout<<bc<<endl;
        }
        for(int c=1; c<steps+1; c++) cout<<path[c-1]<<" ";
        cout<<dest<<endl;stop=true;
        return;
    }
    path[steps]=i;color[i]=gray;
    for(Pedge cur=vertexs[i]; cur; cur=cur->next){
        if(color[cur->t]==white&&cur->avail) travel(cur->t, steps+1, dest);
    }
    color[i]=black;
}
void insert(int i, int j){//supposed no-duplicate items in the entry
    //forward edge
    Pedge toj=edges+(ce++);
    toj->t=j,toj->next=NULL,toj->bridge=false,toj->avail=true;
    Pedge cur=vertexs[i];
    for(;cur&&cur->next;cur=cur->next);
    if(!cur)//if cur==NULL
        vertexs[i]=toj;
    else cur->next=toj;//cur!=NULL
    //backward edge
    Pedge toi=edges+(ce++);
    toi->t=i,toi->next=NULL,toi->bridge=false,toi->avail=true;
    cur=vertexs[j];
    for(;cur&&cur->next;cur=cur->next);
    if(!cur) vertexs[j]=toi;
    else cur->next=toi;
}
void disable(int i, int j){//supposed i<->j exists
    for(Pedge cur=vertexs[i]; cur; cur=cur->next)
        if(cur->t==j){
            if(cur->bridge){bc++; return;}//not bridge
            cur->avail=false; break;
        }
    for(Pedge cur=vertexs[j]; cur; cur=cur->next)
        if(cur->t==i){cur->avail=false; break;}
}
bool setbridge(int i, int j){
    for(Pedge cur=vertexs[i]; cur; cur=cur->next)
        if(cur->t==j) {
            cur->bridge=true;
            break;
        }
}

#define fbase
int main()
{
    #ifdef fbase
    ifstream in("trip5.in");//trip5
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif

    //implementation
    int c1, c2;
    cin>>s, cin>>d, cin>>v, cin>>e;
    for(int i=0; i<e; i++){
        cin>>c1, cin>>c2;
        insert(c1, c2);
    }
    reachable=false,bc=0;
    dfs(s, -1, 0);
    if(!reachable){ cout<<-1<<endl; return EXIT_SUCCESS; }
    memset((void*)color, 0, sizeof(color)),stop=false;
    travel(s, 0, d);
    memset((void*)color, 0, sizeof(color)),stop=false;
    travel(d, 0, s);

    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase

  • 提醒自己,加深算法的目的:为了改掉编程坏习惯,所以在写jerry的代码C#的时候,要有意识的把编程的习惯改过来!要记得自己是为了开发在做准备,不是单纯的为算法而学算法!C#项目的SVN地址:http://code.google.com/p/jptocsharp/,要有意识的在提交SVN之前做代码review!
  • DP的一道水题先:pku 1141 — Brackets Sequence

1.zju和ACM官网的没过,由于我很菜的文件操作,这个要好好反思下!明天专门找个时间来把文件操作的c API复习下,再把那道题过掉!

2.那个print的过程比较巧妙,可以赞一个![c和c++混用的风格要不得,以后不能写这种代码,这道题目居然不能用getline,很好很强大!]

Source Code

Problem: 1141

User: orlando22

Memory: 324K

Time: 16MS

Language: C++

Result: Accepted
  • Source Code
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    const int MAXL=102;
    int n, d[MAXL][MAXL], t[MAXL][MAXL];
    char tmp[MAXL]={0};
    
    //declaration
    int brackets(int i, int j);
    void print(int i, int j);
    
    //implementation
    int brackets(int i, int j){//i,j [1...len]
        if(d[i][j]!=-1) return d[i][j];
        int ret=INT_MAX, tp, sel;//贡献了一个CE
        if((tmp[i]=='('&&tmp[j]==')')||
            (tmp[i]=='['&&tmp[j]==']')){
            tp=brackets(i+1,j-1);
            if(ret>tp) ret=tp, sel=-2;
        }
        if(tmp[i]=='('||tmp[i]=='['){
            tp=brackets(i+1,j)+1;
            if(ret>tp) ret=tp,sel=j+1;
        }
        if(tmp[j]==')'||tmp[j]==']'){
            tp=brackets(i,j-1)+1;
            if(ret>tp) ret=tp,sel=i-1;
        }
        for(int k=i; k<j; k++){
            tp=brackets(i,k)+brackets(k+1,j);
            if(ret>tp) ret=tp, sel=k;
        }
        d[i][j]=ret,t[i][j]=sel;
        return ret;
    }
    void print(int i, int j){
        if(i>j) return;//贡献了一个WA
        if(i==j){
            if(tmp[i]=='('||tmp[i]==')') printf("()");
            if(tmp[i]=='['||tmp[i]==']') printf("[]");
            return;
        }
        //i!=j
        if(t[i][j]==-2){
            printf("%c", tmp[i]);
            print(i+1,j-1);
            printf("%c", tmp[j]);
            return;
        }
        if(t[i][j]==j+1){
            cout<<tmp[i];
            print(i+1,j);
            if(tmp[i]=='(') printf(")");
            if(tmp[i]=='[') printf("]");
            return;
        }
        if(t[i][j]==i-1){//may error
            if(tmp[j]==')') printf("(");
            if(tmp[j]==']') printf("[");
            print(i,j-1);
            cout<<tmp[j];
            return;
        }
        print(i, t[i][j]),print(t[i][j]+1, j);
        return;
    }
    
    
    int main()
    {
        //implementation
        memset((void*)d, 0xff, sizeof(d)),
        memset((void*)t, 0xff, sizeof(t));
        gets(tmp+1);
        int len=strlen(tmp+1);
        for(int i=0; i<len+1; i++) d[i][i]=1;
        for(int i=1; i<len+1; i++) d[i][i-1]=0;
        if(len==0) printf("%s\n",tmp);
        else{//for f[1...MAXL]
            brackets(1, len);
            print(1, len);
            printf("\n");
        }
        return 0;
    }
    

Advertisements