The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

ZOJ 3316 Game

淘来的代码 慢慢研究下 呵呵。

#include<iostream>
using namespace std;

#define maxn 405
#define maxm 330000

struct Edge
{
    
int v,next;
}
E[maxm];

int list[maxn],eid;
int match[maxn];//match[i]表示和i匹配的点编号
bool visit[maxn];//确保在此次增广路搜索中不会回头
int f[maxn];//每个点的状态
//-1, 表示自由点;
//0 , 表示饱和点, 进入方向未搜索;
//1 , 表示饱和点,进入方向已搜索; 
//2 , 表示不能匹配自由点

void init()
{
    memset(list,
-1,sizeof(list));
    eid
=0;
}


inline 
void insert(int u,int v)
{
    
if( u==v ) return;//自环无意义
    E[eid].v=v;
    E[eid].next
=list[u];
    list[u]
=eid++;

    E[eid].v
=u;
    E[eid].next
=list[v];
    list[v]
=eid++;
}


bool dfs(int u)
{
    visit[u]
=true;//**
    int v,p=list[u];
    
while(p!=-1)
    
{
        v
=E[p].v;

        
if( f[v] == -1)
        
{
            match[u]
=v,match[v]=u;
            f[v]
=f[u]=0;
            
return true;
        }


        
if(f[v]==0 && !visit[v])
        
{
            f[v]
=1;//*******
            visit[v]=true;
            
if( dfs( match[v] ) )
            
{
                match[u]
=v,match[v]=u;
                f[v]
=f[u]=0;
                
return true;
            }

            visit[v]
=false;//回溯
        }


        p
=E[p].next;
    }

    visit[u]
=false;//回溯
    return false;
}


void Match(int N,int &ret)//0~N-1,ret为匹配的对数
{
    memset(match,
-1,sizeof(match));//没匹配的点为-1
    memset(f,-1,sizeof(f));
    ret
=0;
    
for(int i=0;i<N;i++)//贪心一个初始匹配
    {
        
if( f[i] != -1continue;
        
int v,p=list[i];
        
while(p!=-1)
        
{
            v
=E[p].v;
            
if(v!=&& f[v] == -1)
            
{
                ret
++;
                match[v]
=i,match[i]=v;
                f[v]
=f[i]=0;
                
break;
            }

            p
=E[p].next;
        }

    }

    
if(ret*2 == N) return;//已经是完美匹配了
    for(int i=0;i<N;i++)
    
{
        
if( f[i] != -1 ) continue;

        memset(visit,
false,sizeof(visit));
        f[i]
=2;
        
if( dfs(i) )    ret++;
        
else f[i]=-1;
        
for(int j=0;j<N;j++if(f[j]==1) f[j]=0;
    }

    
return ;
}


void Print(int N)
{
    
for(int i=0;i<N;i++)
    
{
        
if(match[i]!=-1)
            printf(
"%d %d\n",i,match[i]);
    }

}

//**********************************************
struct DD
{
    
int x,y;
}
dd[444];

int main()
{
    
int N,K;
    
while(scanf("%d",&N)!=EOF)
    
{
        init();
        
for(int i=0;i<N;i++)
        
{
            scanf(
"%d%d",&dd[i].x,&dd[i].y);
        }

        scanf(
"%d",&K);

        
for(int i=0;i<N;i++)
        
{
            
for(int j=i+1;j<N;j++)
            
{
                
if( abs(dd[i].x-dd[j].x)+abs(dd[i].y-dd[j].y) <= K)
                    insert(i,j);
            }

        }

        
int ret;
        Match(N,ret);

        
if( ret*2 == N)
            puts(
"YES");
        
else
            puts(
"NO");
    }

}

posted on 2010-04-24 14:54 abilitytao 阅读(236) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理