巢穴

about:blank

My Links

Blog Stats

Posts - 74
Stories - 1
Comments - 16
Trackbacks - 0

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

2010年12月 (1)

Link

lxr
zh
北極天南星
我的豆瓣

搜索

閱讀排行榜

評論排行榜

ctsc2000 丘比特的煩惱

km..第一次寫km..

#include <iostream>

#include <fstream>

#include <string>

#include <math.h>

using namespace std;

ifstream fin("cupid.in");

ofstream fout("cupid.out");

int k,n;

struct node

{

int x,y;

string name;

}man[31],woman[31];

int connect[31][31];

double dist(node ma,node wo)

{

return sqrt((ma.x-wo.x)*(ma.x-wo.x)+(ma.y-wo.y)*(ma.y-wo.y));

}

bool isCross(node a,node b,node c)

{

if ((a.x-b.x)*(b.y-c.y) == (b.x-c.x)*(a.y-b.y)) //共線

{

if (a.y==c.y)

return (a.x < b.x && b.x < c.x)||(c.x < b.x && b.x < a.x);

else

return (a.y < b.y && b.y < c.y)||(c.y < b.y && b.y < a.y);

}

return false;

}

int lx[31],ly[31];

bool hash[31],hash1[31];

int pre[31];

bool find(int x)

{

hash1[x]=true;

for (int i=1;i<=n;i++)

{

if (!hash[i]&&(lx[x]+ly[i]==connect[x][i]))

{

hash[i]=true;

if (pre[i]==0||find(pre[i]))

{

pre[i]=x;

return true;

}

return false;

}

int main()

{

for (int i=1;i<=31;i++)

for (int j=1;j<=31;j++)

connect[i][j]=1;

memset(pre,0,sizeof(pre));

fin>>k;

fin>>n;

for (int i=1;i<=n;i++)

{

int x,y;

string name;

fin>>x>>y>>name;

for (int j=0;j<name.length();j++)

if (name[j]>='A'&&name[j]<='Z') name[j]+='a'-'A';

man[i].x=x;

man[i].y=y;

man[i].name=name;

}

for (int i=1;i<=n;i++)

{

int x,y;

string name;

fin>>x>>y>>name;

for (int j=0;j<name.length();j++)

if (name[j]>='A'&&name[j]<='Z') name[j]+='a'-'A';

woman[i].x=x;

woman[i].y=y;

woman[i].name=name;

}

string name1,name2;

int t;

while(1)

{

fin>>name1;

if (name1=="End") break;

fin>>name2;

for (int j=0;j<name1.length();j++)

if (name1[j]>='A'&&name1[j]<='Z') name1[j]+='a'-'A';

for (int j=0;j<name2.length();j++)

if (name2[j]>='A'&&name2[j]<='Z') name2[j]+='a'-'A';

fin>>t;

int x,y;

for (int i=1;i<=n;i++)

{

if (man[i].name==name1) x=i;

if (woman[i].name==name1) y=i;

if (man[i].name==name2) x=i;

if (woman[i].name==name2) y=i;

}

connect[x][y]=t;

}

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

{

double distance=dist(man[i],woman[j]);

if (distance>k) connect[i][j]=0;

for (int k=1;k<=n;k++)

{

if (k==i) continue;

if (isCross(man[i],man[k],woman[j])) {connect[i][j]=0;break;}

}

for (int k=1;k<=n;k++)

{

if (k==j) continue;

if (isCross(man[i],woman[k],woman[j])) {connect[i][j]=0;break;}

}

for (int i=1;i<=n;i++)

{

int max=-1;

for (int j=1;j<=n;j++)

{

if (max<connect[i][j]) max=connect[i][j];

}

lx[i]=max;

ly[i]=0;

}

for (int i=1;i<=n;i++)

{

while(true)

{

memset(hash,false,sizeof(hash));

memset(hash1,false,sizeof(hash1));

if (find(i)) break;

else

{

int d=10000;

for (int j=1;j<=n;j++)

{

if (hash1[j])

{

for (int k=1;k<=n;k++)

{

if (!hash[k])

if (d>lx[j]+ly[k]-connect[j][k]) d=lx[j]+ly[k]-connect[j][k];

}

for (int j=1;j<=n;j++)

{

if (hash1[j]) lx[j]=lx[j]-d;

if (hash[j]) ly[j]=ly[j]+d;

}

int result=0;

for (int i=1;i<=n;i++)

{

if (pre[i]!=0) result+=connect[pre[i]][i];

}

fout<<result<<endl;

//system("pause");

return 0;

}

posted on 2009-11-07 22:54 Vincent 閱讀(229) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

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


相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

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

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

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

ctsc2000 丘比特的煩惱