The Fourth Dimension Space

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

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匹配的點(diǎn)編號(hào)

bool visit[maxn];//確保在此次增廣路搜索中不會(huì)回頭

int f[maxn];//每個(gè)點(diǎn)的狀態(tài)

//-1, 表示自由點(diǎn);

//0 , 表示飽和點(diǎn), 進(jìn)入方向未搜索;

//1 , 表示飽和點(diǎn),進(jìn)入方向已搜索;

//2 , 表示不能匹配自由點(diǎn)

void init()

{

memset(list,-1,sizeof(list));

eid=0;

}

inline void insert(int u,int v)

{

if( u==v ) return;//自環(huán)無意義

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為匹配的對(duì)數(shù)

{

memset(match,-1,sizeof(match));//沒匹配的點(diǎn)為-1

memset(f,-1,sizeof(f));

ret=0;

for(int i=0;i<N;i++)//貪心一個(gè)初始匹配

{

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;//已經(jīng)是完美匹配了

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

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

ZOJ 3316 Game