1。复习了下平面图的理论部分,平面图最重要的莫过于“欧拉5色原理”,即一个任意的平面图,都能使用不超过5色来使得相邻区域颜色不一致。

  • 欧拉定理:设有一个连通平面图G,共有v个节点e条边r块面,则v-e+r=2;
  • 推论1:给定G=<V,E,F>,若|V|>=3,则|E|<=3|V|-6,且|F|<=2|V|-4
  • 推论2:若|V|>=3,则存在v<V,使得d(v)<=5;

2。个人觉得没意思,记不住就翻书嘛,再说画出图来证明下就没问题了。还是来个与编程相关的。

procedurce Paint(G:Graph)
begin
  找出度最小的点v0
  Paint(G-v0)
  if 在图中无法找到对v0着色 then
          对v0的相邻店枚举双色对[见黑书],用UFS检测是否在同一分量中;
     若v1,v3在不同分量中,则提取v1的颜色使得其颜色与v3相同,然后把空闲的颜色给v0;
     否则,v2,v4在不同分量中,处理之
  end
end

先来个不是很相关的题目, Timus Online Judge.这道题目考的很简单,二分图处理问题[BFS可以作为二分图验证,第一,验证深度是否相差为奇数;第二,父节点和子节点不同色,注意gray的边界处理,很多书上没有处理这种边界,对于环路的时候程序是不稳定的,谨慎谨慎]

当然这种菜题不是我追求的,主要犯了个错!开始用前向星做的,然后由于是无向图,需要将一条边再次插入,结果vs[]变化了,想了下没好办法,就简单水过了事!

  • 1080. Map Colouring

Time Limit: 1.0 second
Memory Limit: 16 MB

Recent submissions

Problem: Map Colouring

ID

  Author

    Problem

  Language

  Judgement result

  Test #

 Execution time

 Memory used

2521921 

   

orlando22   

  1080

  C++

  Accepted

 

  0.031

  301 KB
 
#include <iostream>
#include <queue>
#include <fstream>
//1080 Map Colouring, Timus Online judge
using namespace std;
const int N=99;
enum{red=0,blue=1,white=-1,gray=-2};
int n;
typedef struct Node{
    int i;
    Node* next;
}Node, *Pnode;
Pnode list[N+1];
Node buffer[N*N];
int bufid=0;
//declaration
void insert(int i, int j){
    //for i->j
    Pnode newnode=&buffer[bufid++];
    newnode->i=j;newnode->next=NULL;
    Pnode cur=list[i];
    for(;cur&&cur->next; cur=cur->next);
    if(!cur) list[i]=newnode;
    else cur->next=newnode;
}
//for color and parent
int color[N], p[N];
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    cin>>n; int tmp;
    for(int i=0; i<n; i++){
        while((cin>>tmp)&&tmp)
            insert(i, tmp-1),insert(tmp-1, i);
    }
    memset((void*)color, 0xff, sizeof(int)*n);
    p[0]=-1;
    queue<int> q;
    q.push(0);
    while(q.size()>0){
        int c=q.front(); q.pop();
        for(Pnode child=list[c]; child; child=child->next){
            if(color[child->i]==white){
                color[child->i]=gray;p[child->i]=c;
                q.push(child->i);
            }
            else if(p[c]!=-1&&color[child->i]!=gray&&color[child->i]!=color[p[c]]){
                cout<<-1<<endl;return 0;
            }
        }
        if(p[c]==-1) color[c]=red;
        else if(color[p[c]]==red) color[c]=blue;
        else if(color[p[c]]==blue) color[c]=red;
    }
    for(int i=0; i<n; i++) cout<<color[i];
    cout<<endl;
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
  • VII Olimpiada Informatyczna 1999/2000
Task: NAR
Author: Marcin Kubica
Skiers[stage I]
公正的评价这道题目不难,折腾料半天,但还好每次代码都没写多长!现在对这种一次写出来,连错都查不出的题,真的一点办法都没有!只能说好好细心研究吧!
分析如下:
1.题目是要求最大路,lrj说很容易让人想到最大流,俄!确实是的,但orlando有两个不同的想法!
2.DFS的贪心,lrj提示的方法,不过如何做却需要好好思考下:
由于每条路径不相交,因此需要做个的判断[开始想成边了,说老是不对呢];但这里会存在一个问题,那我什么时候才晓得,这个点是有效点[对路径有贡献的点]呢?当然是通过这个点的路径,有且只有一条,能使得最终路径增加一条,或者把所有边都用完料,还不行就自认倒霉吧!这里我又有个思路错了,开始写了句来将此点重置,好让其他点能再次访问,但出现料死循环.仔细分析下,确实如此,这样的话,一条无效路径就会不停的进入,然后再测试,再进入,再测试!
我们可以这样认为,假设此点不能使其增加一条有效路径,说明下面的路径,从此点到终点的路径已经被完全堵死,那么这个点也就没有再访问的必要了!
3.其实更简单的思路是什么当然是BFS,用一个队列来记录其可达深度,对于有交叉的中间点,直接合并,同时计数,这样到最后的接点之后,有效路径就是最大化的了.我们可以这样看,开始的时候,其最大路径为1的出度,然后向下一层,找到一个交叉点,合并一条路径,到达最后就是合法的最大路径.
4.最后才是最大流解题,一是本菜对最大流不熟悉,二是题目才菜,不用杀牛刀了.我一定能把最大流掌握的很熟练,动规也是!
好,代码如下:
GNU: 29ms,已通过官方测试文件nar0-nar8
#include <iostream>
#include <fstream>
//POI 1999/2000 Skiers
using namespace std;
const int MAX=5000;//2<=n<=5000
int n, vs[MAX+1], lenofE, maxofski, es[MAX*MAX];
char v[MAX+1];
//declaration
void dfs(int i);
//implementation
void dfs(int i){
    if(i==n-1){
        maxofski++;return;
    }
    //for each child
    for(int k=vs[i]; k<vs[i+1]; k++){
        //edge is available
        if(!v[es[k]]||es[k]==n-1){
            v[es[k]]=1;
            int pre=maxofski;
            dfs(es[k]);
            if(i==0) continue;
            else if(pre+1==maxofski) break;
            //else v[es[k]]=0;自己想想为什么?
        }
    }
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("nar8.in");//
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    int lenc;lenofE=0;
    cin>>n;
    memset((void*)v, 0, n);
    for(int i=0; i<n-1; i++){
        cin>>lenc; vs[i]=lenofE;
        for(int j=0; j<lenc; j++){
            cin>>es[lenofE];es[lenofE]–;
            lenofE++;
        }
    }
    vs[n-1]=lenofE;
    maxofski=0;
    dfs(0);
    cout<<maxofski<<endl;
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
  • 似乎今天的三道题目除了第一道之外,其它都太简单了!所以,明天的开始是这么一道.貌似比较难.
Horizontally Visible Segments-Central Europe 2001
Time Limit: 5000MS  Memory Limit: 65536K
图论要加油了,明天还有三道动规!休息了!
 
分析:
  • 理论分析:这道题目实际上是求线段的相邻公共覆盖,黑书的分析有道理!但由于篇幅没有证明,这里简单说下,第一,要证明"三元组"实际上是一个平面图基础上的"三元组"验证.投映为图关系,实际上就是要证明两个含相邻边的“平面三角形”不可能有对边,这个很容易反证。第二,就是在生成的平面图里面计算三元组个数了,由于相邻的定义,是k对应于k-1,k+1,那么这个映射应该是很简单的。
  • 编程分析

1。难在线段树的生成上,要花点功夫,lrj有个很巧妙的思路!端点是很难分析的,如何做呢?简单的说就是将原来的端点展开为线段,然后再统一处理,如下图所示,lrj书上写的东西,我没看懂,估摸着应该是这个意思吧!

2。然后这点我还在思索中,如何才能让生成的平面图更高效呢?两种等价的选择,前向星和邻接表,问题在于我需要删边,当然我可以做一个标志位,但这个不好,因为扫描规模并没有随有效边的减少而变少,所以最好是将其删掉,如果用前向星,那么每次删边必然要处理整个边数组的移动,非常不好;所以邻接表应该更好,如果用Jon的统一内存分配的话,我甚至可以不管内存的回收。个人比较倾向这种做法,但pku上有牛人说空间占的太大,所以我有点犹豫!

研究了以下lrj的思路[貌似有点混乱,主要我太菜了,精神领会到了],确实没看懂!核心应该是用静态线段树来处理,自己随便想了个招!

对于此题,Top区间宽度为8000-0=8000,那么树深度Log8000+1[含端点]=13+1,一共结点有:2^14-1=16383[取17000].剩下的没什么好说的,用静态线段树的逻辑处理即可。说到专门的线段树,还有两道相关的题目:MatrixA Simple Problem with Integers,一起切了吧!

Advertisements