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] != -1) continue;
        int v,p=list[i];
        while(p!=-1)
        {
            v=E[p].v;
            if(v!=i && 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 阅读(229) 评论(0)  编辑 收藏 引用


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