巢穴

about:blank

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 阅读(205) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


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