The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

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 閱讀(266) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

ZOJ 3316 Game