• 由于最大流和二分的特点,所以先把模型的代码实现过了一遍。然后现在开始按照lrj和实用上的题目进行练习,自己还是对二分的算法HK算法不是很熟悉,练习的时候要多注意!剩下还有四道图论的综合题,要好好练下,注意解题的思路在白纸上写清楚,然后一次性完成程序。图论挺锻炼人的程序能力的,从建模到模型的组合,很多时候都要把许多思想技巧结合在一起。废话不说了!
  • 有两个dotNet技术上的盲点要敲打下,1。GC的分代处理机制;2。CodeDom机制。dotNet一日千里,WPF,WCF,WF已经是今非昔比了,keep moving!
  • 图论结束之后的任务,主要就是进行一些BOP回顾[主要是把原来一些冗长的代码精简下,回头来看,应该有能多的改进才对]和一些基本题目的白纸编程,整理简历和练习口语的同时,把关于google搜索的框架整理下,然后从Heritrix入手,先用C#来实现一个网络爬虫的原型[最好能把一些针对C#的设计模式具体实现之],至于Lucence的分词器模拟,不晓得自己有没有时间完成。不过,无论以后在哪里工作,我还是会把这个作为自己的兴趣做完的!
完成的题目:
1,调皮的导盲犬[lrj P341, 又见实用,P230 小狗散步,在线链接]
分析:典型的二分图,多说无益,只是二分的时候把最后一个定点舍去即可。[代码框架:DFS的匈牙利算法,图的类型信息不够,无法判断是否是稠图,DFS足够了]

Source Code

Problem: 1034 User: orlando22
Memory: 360K Time: 47MS
Language: C++ Result: Accepted
  • Source Code
    #include <cmath>
    #include <iostream>
    
    //pku 1034, zju 2309
    using namespace std;
    const int MAXN=100, MAXE=10000;
    //for bio-partite graph
    typedef struct Edge{
        int x, y, next;
    }Edge;
    Edge es[MAXE];
    int eid, firstX[MAXN], linkY[MAXN];//X集的出边,Y集的匹配边,为了实现方便,将定点和景点翻了下!
    bool ry[MAXN];
    
    //for Xn and X1n
    int x[MAXN], y[MAXN], xx[MAXN], yy[MAXN], n, m;
    
    //declaration
    void inline addEdge(int start, int end);
    void inline clr();
    bool find(int u);
    
    //implementation
    void addEdge(int start, int end){
        es[eid].x=start, es[eid].y=end;
        es[eid].next=firstX[start], firstX[start]=eid; eid++;
    }
    void clr(){
        eid=0,
        memset((void*)firstX, 0xff, sizeof(firstX)),
        memset((void*)linkY, 0xff, sizeof(linkY));
    }
    bool find(int u){
        for(int e=firstX[u]; e!=-1; e=es[e].next){
            if(!ry[es[e].y]){
                ry[es[e].y]=true;
                if(linkY[es[e].y]==-1||find(linkY[es[e].y])){
                    linkY[es[e].y]=u; return true;
                }
            }
        }
        return false;
    }
    
    int main()
    {
        //implementation
        int res(0);
        cin>>n>>m;
        for(int i=0; i<n; i++) cin>>x[i]>>y[i];
        for(int i=0; i<m; i++) cin>>xx[i]>>yy[i];
        //create bio-partite, clr();
        clr();
        for(int i=0; i<n-1; i++){
            double dis=sqrt((double)((x[i]-x[i+1])*(x[i]-x[i+1])+(y[i]-y[i+1])*(y[i]-y[i+1])));
            for(int j=0; j<m; j++){
                double dis1=sqrt((double)((x[i]-xx[j])*(x[i]-xx[j])+(y[i]-yy[j])*(y[i]-yy[j]))),
                    dis2=sqrt((double)((x[i+1]-xx[j])*(x[i+1]-xx[j])+(y[i+1]-yy[j])*(y[i+1]-yy[j])));
                if(2*dis>=dis1+dis2) addEdge(j, i);//consider the speed, reverse
            }
        }
        for(int i=0; i<m; i++){
            memset((void*)ry, 0, sizeof(bool)*n);//for all target vertex->sizeof(bool)*n
            res+=find(i);
        }
        cout<<(res+n)<<endl;
        for(int i=0; i<n; i++){
            if(i!=n-1) cout<<x[i]<<" "<<y[i]<<" ";
            else cout<<x[i]<<" "<<y[i];
            if(linkY[i]!=-1) cout<<xx[linkY[i]]<<" "<<yy[linkY[i]]<<" ";
        }
        cout<<endl;
    
        return 0;
    }
其他的优化:可以用HK来加速,但对这个题目已经足够了!
2,棋盘上的骑士[lrj P332, 实用P234,在线链接]
分析:二分图的最大独立数问题;棋盘是一个自然的二分图,那么最大匹配必然对应棋盘上的最小覆盖数[最少那么多],由于最大独立数与最小覆盖互为补集,因此直接减去最大匹配即可。
先用DFS的匈牙利算法写了个,TLE了,O(VE)的复杂度,V为200,E为40000,那么就是8*10^6,估算差不多在10秒左右,果真直接挂了!

Source Code
#include <iostream>
 
using namespace std;
 
const int MAXN=201, MAXD=8;
int n, m, dx[MAXD]={-2, -2, -1, -1, 1, 1, 2, 2}, dy[MAXD]={-1, 1, -2, 2, -2, 2, -1, 1};
typedef struct LT{
    int x, y;
}LT;
LT link[MAXN][MAXN];
bool map[MAXN][MAXN], used[MAXN][MAXN];
 
//declaration
bool find(int x, int y);
 
//implemenataion
bool find(int x, int y){
    int x1, y1;
    for(int i=0; i<MAXD; i++){
        x1=x+dx[i], y1=y+dy[i];
        if(x1>0&&x1<=n&&y1>0&&y1<=n&&map[x1][y1]&&!used[x1][y1]){
            used[x1][y1]=true;
            if(link[x1][y1].x==-1||find(link[x1][y1].x, link[x1][y1].y)){
                link[x1][y1].x=x, link[x1][y1].y=y; return true;
            }
        }
    }
    return false;
}
 
int main()
{
    //implementation
    int x, y, res(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++) map[i][j]=true;
    for(int i=1; i<=m; i++) cin>>x>>y, map[x][y]=false;
    memset((void*)link, 0xff, sizeof(link));
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]&&((((n&0x1)==1&&((i-1)*n+j)&0x1)==1)||((n&0x1)==0&&(i&0x1)!=(j&0x1)))){//same color to (1,1)
                memset((void*)used, 0, sizeof(used));
                res+=find(i, j);
            }
        }
    }
    cout<<(n*n-m-res)<<endl;
    return 0;
}
 
然后用HK写了个,顺利过了,但实际从理论上估计变化不大的嘛,少了一个数量级而已,但显示的时间是672MS,菜晕!
Source Code

#include <iostream>
 
//BOI task , ECNU 1465 Knights
using namespace std;
 
const int MAXN=201, MAXD=8;
typedef struct LT{
    int x, y;
}LT;
LT link[MAXN][MAXN];
int n, m, dx[MAXD]={-2, -2, -1, -1, 1, 1, 2, 2}, dy[MAXD]={-1, 1, -2, 2, -2, 2, -1, 1};
bool map[MAXN][MAXN], xset[MAXN][MAXN];
int dist[MAXN][MAXN], queue[MAXN*MAXN];
 
//declaration
bool HK_bfs();
bool HK_dfs(int x, int y);
 
//implementation
bool HK_bfs(){
    bool found=false;
    int top=0, size=0, x, x1, y1, x2, y2;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(link[i][j].x==-1&&xset[i][j]) queue[size++]=i*(n+1)+j;//(1,1)起的数组和一维的转化,要小心
            dist[i][j]=0;
        }
    }
    //for modify queue
    for(;top<size;top++){
        x=queue[top], x1=x/(n+1), y1=x-x1*(n+1);
        for(int i=0; i<MAXD; i++){
            x2=x1+dx[i], y2=y1+dy[i];
            if(x2>0&&x2<n+1&&y2>0&&y2<n+1&&map[x2][y2]){//not required for !out[x2][y2]
                if(dist[x2][y2]==0){
                    dist[x2][y2]=dist[x1][y1]+1;
                    if(link[x2][y2].x==-1) found=true;
                    else dist[link[x2][y2].x][link[x2][y2].y]=dist[x2][y2]+1,
                        queue[size++]=link[x2][y2].x*(n+1)+link[x2][y2].y;
                }
            }
        }
    }
    return found;
}
 
bool HK_dfs(int x, int y){
    int x1, y1;
    for(int i=0; i<MAXD; i++){
        x1=x+dx[i], y1=y+dy[i];
        if(x1>0&&x1<n+1&&y1>0&&y1<n+1&&map[x1][y1]){
            if(dist[x1][y1]==dist[x][y]+1){
                dist[x1][y1]=0;//reset back to top
                if(link[x1][y1].x==-1||HK_dfs(link[x1][y1].x, link[x1][y1].y)){//昨晚忘记加link[x][y]了,搞了个死循环
                    link[x1][y1].x=x, link[x1][y1].y=y, link[x][y].x=x1, link[x][y].y=y1; return true;
                }
            }
        }
    }
    return false;
}
 
int main()
{
    //implementation
    cin>>n>>m;
    int x, y, res(0);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) map[i][j]=true, xset[i][j]=false;
    }
    for(int i=1; i<=m; i++) cin>>x>>y, map[x][y]=false;
    //set xset for out-link
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]&&(((n&0x1)&&(((i-1)*n+j)&0x1)==1)||(!(n&0x1)&&(i&0x1)!=(j&0x1))))
                xset[i][j]=true;
        }
    }
memset((void*)link, 0xff, sizeof(link));//reset for link
    //for HK algorithm
    while(HK_bfs()){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++)
                if(xset[i][j]&&link[i][j].x==-1&&HK_dfs(i, j)) res++;
        }
    }
    cout<<(n*n-m-res)<<endl;
    return 0;
}

 
Advertisements