• 图论模型主要是一些比较成熟的基本图论算法:[我会把重点放在后面两个,因为上次只是把理论过了一次,实践证明没有练过题的理论,漏洞百出]
1,生成树算法
2,最短路算法
3,网络流算法
4,二分图算法
 
  • 生成树算法:[今天有点烦躁,反省一下,患得患失是不行,有始有终的加油!]
生成树算法:15分钟搞定,但是有个问题,我的heap实现RE,标准的STL实现没问题!问题在哪里呢?人有问题!
代码如下:[我决定去看下标准库的实现!]
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <memory.h>
#include <math.h>
using namespace std;
const int MAXN=52;
double x[MAXN],y[MAXN],p[MAXN];
bool linktoM[MAXN];
typedef struct Lnode{
    int i, j; double value;
}Lnode, *Pnode;
int nid=0;
Lnode np[MAXN*MAXN/2];
Pnode nptr[MAXN*MAXN/2];
//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;
        }
    }
};
UFS _u;
//declaration
void heapAdjust(int child, int end);
void inline toHeap();
int inline popHeap();
//My Heap implementation
void heapAdjust(int current, int end){//start with 0
    if(current>end) return;
    double tmp=nptr[current]->value;
    int child=(current<<1)+1;
    while(child<=end){
        if(child<end&&nptr[child+1]->value<nptr[child]->value) child++;//logic judgement, order!
        if(tmp<=nptr[child]->value) break;
        //swap current and child
        Pnode t=nptr[current]; nptr[current]=nptr[child]; nptr[child]=t;
        current=child, child=(child<<1)+1;
    }
}
void inline toHeap(){//nptr+nid the next slot
    if(nid>1){//[0,nid]
        for(int i=nid/2; i>=0; i–) heapAdjust(i, nid-1);//?
    }
}
int inline popHeap(){//pop for next slot
    if(nid>1){ Pnode t=nptr[0]; nptr[0]=nptr[nid-1]; nptr[nid-1]=t; }
    nid–;
    if(nid>1) heapAdjust(0, nid-1);
    return nid;
}
//STL Heap implementation
int cmp(const void* p1, const void* p2){
    return ((Pnode)p1)->value>((Pnode)p2)->value;//remember bracket
}
//Heap implementation
void inline toHeap(){//nptr+nid the next slot
    if(nid>1) push_heap(nptr, nptr+nid, cmp);
}
int inline popHeap(){//pop for next slot
    pop_heap(nptr, nptr+nid, cmp);nid–;return nid;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int n, num=1;
    while(cin>>n&&n>0){
        nid=0;
        double total=0, mt=0;
        int m=1, edges=0;
        for(int i=1; i<n+1; i++){
            cin>>x[i], cin>>y[i], cin>>p[i];
            mt+=p[i];
        }
        for(int i=1; i<n+1; i++){//O(N*N)
            for(int j=i+1; j<n+1; j++){
                double value=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
                np[nid].i=i, np[nid].j=j, np[nid].value=value;
                nptr[nid]=np+nid;//put it into minheap
                nid++; toHeap(); //previous operatin to make min heap
            }
        }
        _u.setk(n); for(int i=1; i<n+1; i++) linktoM[i]=false;
        do{
            int tmp=popHeap();
            int t1=_u.find(nptr[tmp]->i), t2=_u.find(nptr[tmp]->j);
            if(t1!=t2){
                _u.unions(t1, t2); edges++;
                //update t[nptr[tmp]->i], t[nptr[tmp]->i]
                m=_u.find(1);
                for(int i=2; i<n+1; i++){
                    if(_u.find(i)==m&&!linktoM[i]){
                        total+=nptr[tmp]->value*p[i], linktoM[i]=true;
                    }
                }
            }
        }while(edges<n-1);
        printf("Island Group: %d Average %.2f\n\n", num, total/mt);
        num++;
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
              • 最后三道题目:POI 1995 Messenger, Timus 1128 Partition, 还有一道经典题目,图论基本理论主要是以连通量为支撑,然后扩展开来将BFS,DFS以及一些树转化的方法结合在一起,开始有点小看这个部分,其实真的比较难![POI 1995的那道题目缺乏测试数据,所以先跳过了,而且有点没有想得很清楚如何实现]
              • 感概一下,很快我的ACM2的工程也满了,再开一个ACM3吧,深有体会,为什么别人比自己强很多的原因了!千里马又勤奋,当然就可以一日千里,驽马加油!~~
              1,Timus 1128 Partition into Group
              理论不难:
              • 一个二着色问题,用BFS树先作一次色,然后进行判断!可以证明根节点和内节点不可能是坏点,因为根节点开始BFS的,所以下面的节点不会和他有冲突;而内节点的度为3,其父以及其子根据算法是不会冲突的,那么最多有一个冲突;因此坏点在叶节点上。又由于对于任意的叶结点x,其仇敌a,b而言(a,b不能为根,怎么证明:首先两个不可能同时为根,因此任选一个如a为根,那么对于一个生成树而言x,a必然直接在根之下的相邻层,OK,而这是无法冲突的),可以反证,x<->b变色是一个悖论,因此结果是x只能变一次色!好了,那么说明我们对所有坏点的操作是一个O(n)的序列。用一个循坏队列作一次操作即可,问题在于原来的节点在放入队列之后,可能变成好点,这点我开始忽略了,因为在更改坏点属性时,队列里面的点是可能更改的,所以这里用的是循坏队列!
              • 然后就是一些比较烦的判断了,我们不妨把点分为三类:red,white,black,white表示什么颜色都不会冲突,分情况讨论即可,这里省去,可以看代码的实现!
              • 不要忘记了,这道题目没有讲是一个连通图,所以要作一次循环,这是细节
              • Timus的judge online是有问题的,所以不提交也罢,因为这道题目肯定是一个多解题目,有些情况作者没有考虑到,或者是题目的描述没有将作者的意图说的很清楚,我的程序很轻松的就跑了几个完全不一样的结果出来,而且都是对的。

              下面是我的实现:

              #include <iostream>
              #include <fstream>

              using namespace std;
              const int MAXN=7200, MAXE=22000;
              int es[MAXE]={0}, vs[MAXN]={0}, queue[MAXN]={0}, color[MAXN]={0};
              enum {white=0, red=1, black=2};

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

                  //implementation
                  int n, vlen, idofe=0, t;
                  cin>>n;
                  for(int i=1; i<n+1; i++){
                      cin>>vlen; vs[i]=idofe, vs[i+1]=idofe+vlen;
                      for(int j=1; j<vlen+1; j++){
                          cin>>t, es[idofe++]=t;
                      }
                  }
                  //bfs to color all dot
                  for(int i=1; i<n+1; i++){
                      if(vs[i+1]-vs[i]==0) continue;//no adversary
                      if(color[i]==white){//start bfs, multi-connective components
                          memset((void*)queue, 0, sizeof(int)*n);
                          color[i]=black, queue[0]=i;
                          int cid=0, size=1;
                          while(cid<size){
                              int cnode=queue[cid++];//already colored
                              for(int t=vs[cnode]; t<vs[cnode+1]; t++){
                                  int tnode=es[t];
                                  if(color[tnode]==white){
                                      if(color[cnode]==black) color[tnode]=red;
                                      else color[tnode]=black;
                                      queue[size++]=tnode;
                                  }
                              }
                              //if with p[cnode], then if(p[cnode]==-1) color=black; otherwise, color=~color[p[cnode]];
                          }
                      }
                  }
                  //find the bad node and put into queue;
                  memset((void*)queue, 0, sizeof(int)*(n+1));
                  int bid=0, badcount;
                  for(int i=1; i<n+1; i++){
                      if(color[i]==white) continue;//no adversary, always good
                      badcount=0;
                      for(int j=vs[i]; j<vs[i+1]; j++){
                          if(color[i]==color[es[j]]) badcount++;
                      }
                      if(badcount>1) queue[bid++]=i;
                  }
                  int idofout=-1;//tricky
                  if(bid>0){//reverse color to find good partition, cycle queue!
                      idofout=0; int times=0;
                      while(times<n&&idofout!=bid){//idofout==n-1, change n times; or idofout<bid, no output!循环队列实现
                          int nv=queue[idofout];
                          if(idofout==n-1) idofout=0;
                          else idofout++;
                          int ncheck=0, cn;
                          for(int j=vs[nv]; j<vs[nv+1]; j++)
                              if(color[nv]==color[es[j]]) ncheck++;//color different
                          if(ncheck<=1) continue;//become good
                          //change color
                          times++;
                          if(color[nv]==black) color[nv]=red;
                          else color[nv]=black;
                          //check neighbour
                          for(int j=vs[nv]; j<vs[nv+1]; j++){
                              ncheck=0, cn=es[j];
                              for(int k=vs[cn]; k<vs[cn+1]; k++){
                                  if(color[cn]==color[es[k]]) ncheck++;
                              }
                              if(ncheck>1){
                                  queue[bid]=cn;
                                  if(bid==n-1) bid=0;
                                  else bid++;
                              }
                          }
                      }
                      if(idofout!=bid){
                          cout<<"NO SOLUTION"<<endl; return EXIT_SUCCESS;
                      }
                      //idofout==bid, all bad dot has been swept.
                  }
                  int redc=0, blackc=0, whitec=0, color1, tcolor, tcount;
                  for(int i=1; i<n+1; i++){
                      if(i==1) color1=color[1];
                      if(color[i]==red) redc++;
                      else if(color[i]==black) blackc++;
                      else whitec++;
                  }
                  //find the less group,这个是所谓很烦的判断
                  if(redc<blackc) tcolor=red, tcount=redc;
                  else if(redc>blackc) tcolor=black, tcount=blackc;
                  else if(redc==blackc){
                      if(whitec>0){
                          if(color1==white) tcolor=black, tcount=blackc;//abitrary black or red
                          else{
                              tcolor=color1;
                              if(tcolor==black) tcount=blackc;
                              else tcount=redc;
                          }
                      }
                      else{
                          tcolor=color1;//whitec==0
                          if(tcolor==black) tcount=blackc;
                          else tcount=redc;
                      }
                  }
                  for(int i=1, count=1; i<n+1; i++){
                      if(color[i]==tcolor){
                          cout<<i;
                          if(count!=tcount) cout<<" ",count++;
                      }
                  }
                  cout<<endl;

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

              2,经典的连通图编号问题:

              一点理论:如何让对于每个顶点的边最大公约数为1呢?开始的那个顶点的出边肯定为1,而后面的顶点的DFS生成树入边为k的话,那么假设为单支,那不存在公约数问题;而对于多支的话,必然有一条出边为k+1,OK!

              下面是我的实现:

              #include <iostream>
              #include <fstream>

              using namespace std;
              const int MAXE=500, MAXN=20;
              typedef struct Edge{
                  int t, num; Edge* next;
              }Edge, *Pedge;
              Edge storage[MAXE];
              Pedge links[MAXN]={0};
              int eid=0;
              int n, k, id=1, color[MAXN]={0};
              enum {white=0, gray=1, black=2};

              //declaration
              void insert(int i, int j);
              void setnum(int i, int j, int num);
              void dfs(int v);

              //implementation
              void insert(int i, int j){
                  Pedge cur=storage+(eid++);
                  cur->t=j, cur->next=NULL, cur->num=-1;
                  Pedge l=links[i], pre=NULL;
                  for(;l&&l->t<j; pre=l,l=l->next);
                  if(l&&l->t==j) return;
                  if(l) cur->next=l;
                  if(!pre) links[i]=cur;
                  else pre->next=cur;
              }
              void setnum(int i, int j, int num){
                  for(Pedge cur=links[i]; cur; cur=cur->next)
                      if(cur->t==j){ cur->num=num;break; }
              }
              void dfs(int v){
                  color[v]=gray;
                  for(Pedge cur=links[v]; cur; cur=cur->next){
                      if(color[cur->t]==white){
                          cur->num=id, setnum(cur->t, v, id);
                          id++;
                          dfs(cur->t);
                      }
                      else{
                          if(cur->num==-1){
                              cur->num=id, setnum(cur->t, v, id);
                              id++;
                          }
                      }
                  }
                  color[v]=black;
              }

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

                  //implementation
                  int s, t;
                  cin>>n, cin>>k;
                  for(int i=1; i<k+1; i++){
                      cin>>s, cin>>t;
                      insert(s, t), insert(t, s);
                  }
                  dfs(1);
                  for(int i=1; i<n+1; i++){
                      cout<<i<<" to : ";
                      for(Pedge cur=links[i]; cur; cur=cur->next){
                          cout<<"->"<<cur->t<<" [id:"<<cur->num<<"] ";
                      }
                      cout<<endl;
                  }

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

               

               
               

              Advertisements