• 我已经下决心了,以后再也不用DFS来找连通分量!还要开个多大的标志位,还是UFS好!

Primitivus – VI Olimpiada Informatyczna 1998/1999

一道很简单但很复杂的题目:基因编码 POI的一道基本图论题目,分析如下

1。将(l,r)映射为有向边,然后用UFS来合并连通分量,统计每一个连通分量里面的|in-out|

2。假设我们能找到一条欧拉回路或者道路,那么OK可以说明其最短路径。但这道题妙就妙在,不需要求出具体的欧拉回路是什么,只需要路长,如何分析呢?我们把原来条件中的路径按某种排列展开,如果是一条欧拉路[回路或道路],那么就没问题了,否则就要添上一些边,让它能组成一条欧拉路。

用欧拉回路的充要条件:一个连通分支,加所有点入度和出度差为0。

分情况讨论:若只有一个连通分支,且出入度绝对值之差和为N,那么我们应该要加N/2+1或者N/2,来构成欧拉回路,不过欧拉道路就可以了,因此N/2;

若有多个连通分支,对于当前计算的连通分支A,假设其存在欧拉回路[出入度为0],那么需要加对于整个图而言需要加一条边,但是考虑到一条边一定会搭到某一个连通分支上,因此这个增量可以视为下一个连通分量的增加值,因此当前不增;[POI牛人链接,牛人就是这里搞错了,估计写的太快了吧!]

而若当前分支A,出入度之差不为0,那么要增加N/2条边,其中一条边要搭到下一个分支上,那么算下一个分支的时候,我们是否要减去这条边呢,其实不用了;假设N/2形成的是欧拉回路,那么这条边搭到下一个分支上,我们可以知道下一个分支增值其实是不变的,因为我们取得是下取整!而假设是欧拉道路呢,则需要增加一条边,并且在下一个分支里面减去一条边,因为下一个分支N/2至少会形成一个欧拉道路,因此平均的效应就是当前的分支增加N/2即可.

代码实现:没找到judge online的地方,POI的测试用例都过了的!本来想用eager evalation来做Union的,想了下,好像没必要,所以就写料个函数完事!

GNU:293ms

#include <iostream>
#include <fstream>
//POI 1999, Primitivus , 1 <= l <= 1000, 1 <= r <= 1000, (l,r) and l!=r
using namespace std;
const int MAX=1001;
int A[MAX];//1…1000, in and out degree counting
int C[MAX];//connective components
int vn;
//UFS implementation
class UFS{
private:
    int T[MAX],t1;
public:
    UFS(){
        memset((void*)T, 0xff, sizeof(int)*MAX);
    }
    void adjust(int tsize){
        this->t1=tsize;
    }
    int find(int i){
        if(i<1||i>=MAX) return -1;
        int v=i,p;
        while(T[v]>0) v=T[v];
        p=v,v=i;
        while(v!=p){
            int tmp=T[v];
            T[v]=p;
            v=tmp;
        }
        return p;
    }
    void Union(int i, int j){
        if(i<1||i>=MAX||j<1||j>=MAX) return;
        int r1=find(i), r2=find(j), tmp;
        if(r1==r2) return;//sign!用紫色标记出来这个问题,Union的时候,千万要注意是否属于同一!!!!!!死循环!!!!!!!
        if(T[r1]<T[r2]){//r1 has more elements
            tmp=T[r2]; T[r2]=r1;
            T[r1]+=tmp;
        }
        else{
            tmp=T[r1]; T[r1]=r2;
            T[r2]+=tmp;
        }
    }
    int TorNot(int i, int j){
        if(i<1||i>=MAX||j<1||j>=MAX) return -1;
        return (find(i)==find(j));
    }
    //lazy evalation
    void TGroup(int& size){
        int i=0;
        C[i++]=0;
        for(int j=1; j<=t1; j++)
            if(T[j]<0) C[i++]=j;
        size=i;//1…i-1
    }

};
UFS u;

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

    //implementation
    long n, total;
    int maxv=-1, start, end, tsize=0;
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>start, cin>>end;
        A[start]++, A[end]–;
        u.Union(start, end);
        if(start>maxv) maxv=start;
        if(end>maxv) maxv=end;
    }
    u.adjust(maxv);
    for(int i=1; i<=maxv; i++)
        if(A[i]<0) A[i]*=-1;
    for(int i=1; i<=maxv; i++){
        int tmp=u.find(i);
        if(tmp!=i) A[tmp]+=A[i];
    }

    total=n;
    u.TGroup(tsize);//看来看去,只有这里比较有价值,但好像似乎,估摸着。。。不太规范!
    if(tsize==1){
        if(A[C[1]]==0);//OK
        else total+=(A[C[1]]>>1);//OK
    }
    else{//tsize>0
        for(int i=1; i<=tsize; i++){
            if(A[C[i]]==0);//add one edge
            else total+=(A[C[i]]>>1);
        }
    }
    cout<<total<<endl;

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

  • 星期三很失败的一天,我不说什么了!基本什么都没过!明天压力大了!好好休息!省下力气来做题吧!
  • 图论确实比较难,不过好在理论基础还打得比较好,适应一下就好了!

1。Euler路的Euler Circuit算法,加前向星构图,Timus Online Judge上的online judge有问题,这道题目明显是多解[欧拉游程在多数情况下不可能是单一解的],自己写了两个用例确实如此! [先放下,觉得思路有点卡,等把下面的题目过了,再回来研究用例!那个管理员多好的,还答应给我发数据过来,平易的牛人压!]

2。用STL的list来做了个链表插入,本来没什么说的,只是怕自己忘了,iterator失效的问题,随便提下!

GNU:

0.015  Memory :  

221 KB

#include <iostream>
#include <list>
#include <fstream>
//Timus Online Judge, 1129. Door painting
//forward star for graph
//Vertexs N<=100, Max Edges are C(n,2)=5000
using namespace std;
const int MAXV=100,MAXE=50000;
typedef struct Edge{
 int s,e,link;
 bool v,add;
}Edge;
Edge es[MAXE];
typedef struct Vertex{
 int sv,d;
}Vertex;
Vertex vs[MAXV+1];//for last one
typedef list<int>::iterator INIITER;
char visited[MAXV]={0}, buffer[MAXE]={0}, status[MAXE]={0}, vertexs[MAXV]={0};
enum {white=0,gray=1,black=2};
//for all vertexs in the graph
int n,lenofE,bufid=0,staid=0;

//declaration
bool dfs(int i);
void solution(int iodds);
int insert(int s, int e, bool append);
//euler circuit algorithm
void euler(int i, list<int>& circuit);
void dfs_loop(int i, const int& start, int cur, list<int>& circuit, char* path, char* check, bool& stop);

//implementation
void dfs(int i, bool& connected){
 if(visited[i]!=white) return;
 //not visited
 //dummy implementation
 visited[i]=gray;
 for(int k=vs[i].sv; k<vs[i+1].sv; k++)
  if(visited[k]==white) dfs(k, connected);
 visited[i]=black;
 if(visited[0]==black){
  connected=true;
  for(int j=0; j<n; j++)
   connected=connected&&(visited[j]!=white);
 }
}
void solution(int iodds){//change into even edges for each odd vertexs
 int len=(iodds>>1)+1;
 for(int i=0,start=0; i<len&&start<n; i++){
  while(!(vs[start].d&0x1)) start++;
  int s=start;start++;
  while(!(vs[start].d&0x1)) start++;
  int e=start;start++;
  int e1=insert(s, e, true);
  int e2=insert(e, s, true);
        es[e1].link=e2,es[e2].link=e1;
 }//Add Edges done!
 for(int i=0; i<n; i++){
        for(int k=vs[i].sv; k<vs[i+1].sv; k++){
            int e=es[k].e;//i->e
            for(int p=vs[e].sv; p<vs[e+1].sv; p++)
                if(es[p].e==i&&!es[p].add) es[p].link=k,es[k].link=p;//前向星的无向图改进,把对等的边关联起来!
        }
  vertexs[i]=vs[i+1].sv-vs[i].sv;//copy vertex[i]
 }
 lenofE=vs[n].sv;
 list<int> path;
 euler(0, path);path.push_back(0);
 INIITER pre=path.begin(), s=path.begin();s++;
 for(; s!=path.end(); pre++,s++){
  int s1=*pre, e1=*s;
  for(int v=vs[s1].sv; v<vs[s1+1].sv; v++){
   if(es[v].e==e1&&!es[v].add)
                es[v].v=false, es[es[v].link].v=true;//for G color
  }
    }
 for(int i=0; i<n; i++){
  for(int v=vs[i].sv; v<vs[i+1].sv; v++){
   if(!es[v].add){
    if(es[v].v) cout<<"G";
    else cout<<"Y";
    if(v+1!=vs[i+1].sv) cout<<" ";
   }
  }
  cout<<endl;
 }
}
//euler path
void euler(int i, list<int>& circuit){//欧拉游程的套圈算法
 memset((void*)visited, 0, n);
 char *path=buffer+bufid;bufid+=lenofE;
 char *check=status+staid;staid+=n;
 memset((void*)check, 0, n),memset((void*)path, 0, lenofE);
 bool stop=false;
 visited[i]=1;
 dfs_loop(i, i, 0, circuit, path, check, stop);
 //once we have more than two path for single node?
 list<int> sub;
 //circuit status
 for(INIITER j=circuit.begin(); j!=circuit.end(); j++) visited[*j]=1;
 INIITER end=circuit.end();
 for(INIITER j=circuit.begin(); j!=end; j++){
  if(visited[*j]==1&&vertexs[*j]!=0){
   sub.clear();
   euler(*j, sub);
   if(sub.size()>1){
    circuit.insert(j, sub.begin(), sub.end());
    j=circuit.begin(),end=circuit.end();
   }
  }
 }
 //recovery
 bufid-=lenofE,staid-=n;
}

void dfs_loop(int i, const int& start, int cur, list<int>& circuit, char* path, char* check, bool& stop){
 if(stop) return;
 if(i==start&&check[i]){//find dfs loop
  for(int j=0; j<cur; j++) circuit.push_back((int)path[j]);
  stop=true;//just find one loop, avoid two circuit together
  return;
 }
 check[i]=1,path[cur]=i;
 for(int k=vs[i].sv; k<vs[i+1].sv; k++){
  int end=es[k].e;
  if((!check[end]||es[k].e==start)&&!es[k].v&&!stop){//target non-visited, and target edge exists
   es[k].v=true;
   int j=es[k].link; es[j].v=true;
   vertexs[i]–;vertexs[end]–;
   dfs_loop(es[k].e, start, cur+1, circuit, path, check, stop);
   if(!stop){
    es[k].v=false;es[j].v=false;
    vertexs[i]++;vertexs[end]++;
   }
  }
 }
}

int insert(int s, int e, bool append){//insert s->e into es
 int end=vs[s+1].sv;
 for(int i=vs[n].sv-1; i>=end; i–) es[i+1]=es[i];
 es[end].s=s,es[end].e=e,es[end].add=true,es[end].v=false;
 //modify starting position
 for(int i=s+1; i<=n; i++) vs[i].sv++;
 return end;
}

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

 //implementation
 cin>>n;
 int iofE=0,iodds=0;
 for(int i=0; i<n; i++){
  vs[i].sv=iofE;
  cin>>vs[i].d;
  if(vs[i].d&0x1) iodds++;
  for(int j=0; j<vs[i].d; j++, iofE++){
   es[iofE].s=i,es[iofE].v=false, es[iofE].add=false;
   cin>>es[iofE].e;es[iofE].e–;//why? here is error, char type is different from int
  }
 }
 //last item, dummy implementation
 vs[n].sv=iofE,vs[n].d=-1;
 if(iodds&0x1){
  cout<<"Impossible"<<endl;return 0;
 }
 bool connected=false;
 dfs(0, connected);
 if(!connected){
  cout<<"Impossible"<<endl;return 0;
 }
 //OK, valid items for graph
 solution(iodds);
#ifdef fbase
 in.close();
#endif
 return 0;
}
#undef fbase

  • 欲哭无泪,我连优化都不想做了,这道题目让我尝到了什么叫简单到你不用脑壳想,但就是搞不出来!

图论第一题就简直让我放弃了,终于找到原因了!http://acm.pku.edu.cn/JudgeOnline/problem?id=1257 Cross-stitch.

知识点:连通量的DFS;以及图映射。注意哈:唯一难的地方在我们可以求出一个顶点的真值,然后再求和,一点都不麻烦;唉!邻接表居然都能写错!我的天呀!当然能加速,可以用UFS来做通量的合并,这样不做DFS,会快一点,唉!轻视ACM的任何一道题,都要自食其果的!

我一直自信:邻接表,肯定不会错的!结果就是邻接表出的错!这道题目也创纪录了,之慢!LLV吐了,上次那道叫Bugs的程序是由于本来题目就比较难,这种菜题也花这么多时间,我只能说太失败了,只有用后来的行动来洗刷耻辱料!

Source Code

Problem: 1257

User: orlando22

Memory: 6036K

Time: 1844MS//我心都凉了!

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    const int MAX=40600;//(1+200)*(1+200)
    typedef struct Lnode{
        int i;//256 char type, estimate
        Lnode *next;
    }Lnode, *Pnode;
    Pnode llist[MAX];
    int lt[MAX];
    char visited[MAX];
    int n,m,total,threads;
    enum {white=0, gray=1, black=2};
    
    //declaration
    void insert(int i, int j, int r);
    int dfs(int i);
    
    //implementation
    void insert(int i, int j, int r){
        //for i->j, and j->i, i<j
        Pnode cur=llist[i];
        for(;cur&&cur->next&&cur->i!=j;cur=cur->next);//next is not null
        if(!cur||(!cur->next&&cur->i!=j)){//cur=NULL, last item
            Pnode n1=new Lnode;
            n1->i=j,n1->next=NULL;
            if(!cur) llist[i]=n1;
            else cur->next=n1;
            //insert for j
            Pnode n2=new Lnode;
            n2->i=i,n2->next=NULL;
            Pnode n=llist[j];
            for(;n&&n->next;n=n->next);//n may NULL
            if(!n) llist[j]=n2;
            else n->next=n2;
        }
        //else cur!=NULL&&cur->i==j;
        if(r==1) lt[i]++,lt[j]++;
        else lt[i]--,lt[j]--;
    }
    int dfs(int i){
        int tmp=lt[i];visited[i]=gray;
        //list node traverse
        for(Pnode cur=llist[i]; cur; cur=cur->next){
            if(visited[(int)cur->i]==white&&llist[(int)cur->i]!=NULL)
                tmp+=dfs((int)cur->i);
        }
        visited[i]=black;
        return tmp;
    }
    
    int main()
    {
        //implementation
        cin>>n,cin>>m;
        total=(n+1)*(m+1);
        memset((void*)lt, 0, sizeof(int)*MAX);
        memset((void*)visited, 0, MAX);
        memset((void*)llist, 0, sizeof(Pnode)*MAX);
        char c;
        for(int k=1; k>=0; k--){
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    cin>>c;
                    if(c=='.') continue;
                    //left_top:(i*m+j)+i,right_top:(i*m+j)+i+1,left_bottom:i*(m+1)+j+m+1,right_bottom:i*(m+1)+j+m+2
                    else{
                        if(c=='\\')
                            insert((i*m+j)+i, i*(m+1)+j+m+2, k);
                        if(c=='/')
                            insert((i*m+j)+i+1, i*(m+1)+j+m+1, k);
                        if(c=='X'){
                            insert((i*m+j)+i, i*(m+1)+j+m+2, k);
                            insert((i*m+j)+i+1, i*(m+1)+j+m+1, k);
                        }
                    }
                }
            }
        }
        //llist done, set value
        for(int i=0; i<total; i++)
            if(lt[i]<0) lt[i]*=-1;
        //DFS to find the linked block
        threads=0;
        for(int i=0; i<total; i++){
            if(visited[i]==white&&llist[i]!=NULL){
                int pre=dfs(i);
                if(pre==0) threads+=1;
                else threads+=(pre>>1);
            }
        }
        cout<<threads<<endl;
    
        return 0;
    }
  • E路的练习:1129. Door painting http://acm.timus.ru/problem.aspx?space=1&num=1129
改造欧拉回路题目!加油,A了它!
  • 先看个基本问题,如何求A[0…n-1]的逆序数,可以说是最简单的一种分治法了!但要结合归并的方式,却不见的能写得漂亮而不失风格!

不解释思路了,直接贴代码了[当然,这个算法不是最好的,分段归并n^1/2+就地重排,应该是更好的!但本菜认为,如果不是大数据量,有点杀鸡用牛刀!]

当然这是段常识性代码,还是能很快且正确的写出才算是基本功到家了!我刚才有个错误的思路,在就地重排的过程中,我想找到第一个orig[i]>=orig[j]的地方,然后把所有的右侧数据用swap_segment转移到左边,有什么问题orig[i]>orig[j],并不代表大于所有的右侧数据,好料!再简单的题也有它的价值,行加油了!

#include <iostream>
#include <fstream>

using namespace std;
const int MAX=30;
int orig[MAX], backup[MAX];
int n;

//declaration
int revert(int l, int r);
//implementation
int revert(int l, int r){
    if(l>=r) return 0;
    if(l+1==r){
        if(orig[l]>orig[r]){
            orig[l]^=orig[r],orig[r]^=orig[l],orig[l]^=orig[r];
            return 1;
        }
    }
    int c=0,mid=l+((r-l)>>1);
    c+=revert(l, mid)+revert(mid+1, r);
    //merge logic,这种代码才是我应该追求的
    for(int i=l,j=mid+1,k=l;i<=mid||j<=r;k++){
        if(i<=mid&&(j>r||orig[i]<=orig[j])){//merge sorting
            backup[k]=orig[i++]; c+=j-mid-1;//previous revert counting number for orig[i]
        }
        else{
            assert(i>mid||(j<=r&&orig[i]>orig[j]));
            backup[k]=orig[j++];
        }
    }
    memcpy((void*)(orig+l), (void*)(backup+l), sizeof(int)*(r-l+1));
    return c;
}

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

    //implementation
    cin>>n;
    for(int i=0;i<n;i++) cin>>orig[i];
    cout<<local(0, n-1)<<endl;

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

  • 今天的目标是把图论的4道基本题目[图的H路,E路问题]做完,然后解决3道动规的编码问题[至少2道,双向规划和多维动规],加油了!注意编码风格和思维严谨!
  • 提醒自己周末用socket和IO完成端口做一个小的网络测试咚咚,研究下IO完成端口到底性能有多好!
  • 可以用WPF框架重新写个俄罗斯方块的游戏,但注意运用和设计博弈论中的启发性算法!如果还是写那种没有价值的咚咚,那就不用动手浪费时间了!

Advertisements