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

巢穴

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 閱讀(229) 評論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結構與算法


只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲精品日韩综合观看成人91| 一区二区三区www| 午夜亚洲一区| 国产亚洲aⅴaaaaaa毛片| 久久久国产视频91| 久久精品二区| 亚洲高清中文字幕| 最新日韩在线视频| 欧美国产免费| 亚洲欧美激情一区二区| 亚洲欧美在线看| 在线观看日韩av| 亚洲精品一级| 国产情侣一区| 欧美国产日韩一区二区在线观看| 欧美男人的天堂| 欧美在线播放一区| 欧美成人午夜视频| 午夜精品福利视频| 免费一级欧美片在线播放| 99视频精品在线| 久久国产精彩视频| 亚洲精品一二区| 午夜精品国产| 亚洲毛片在线| 欧美中在线观看| 日韩一级大片在线| 性欧美长视频| 99热精品在线| 久久精品系列| 亚洲视频在线二区| 久久最新视频| 久久精品国产2020观看福利| 麻豆精品精华液| 久久精品国产99精品国产亚洲性色| 久久午夜精品一区二区| 亚洲一区二区在线免费观看| 久久久久久久久久码影片| 亚洲欧美日韩在线一区| 欧美精品九九99久久| 久久久亚洲高清| 欧美性做爰毛片| 亚洲高清不卡在线| 在线精品国产成人综合| 亚洲特黄一级片| 一本色道久久综合亚洲精品小说| 久久久亚洲国产美女国产盗摄| 亚洲欧美在线免费观看| 欧美精品日日鲁夜夜添| 欧美激情1区2区| 狠狠色伊人亚洲综合成人| 亚洲永久精品国产| 一区二区不卡在线视频 午夜欧美不卡'| 久久av一区二区三区| 久久精品国产2020观看福利| 国产精品国产三级国产a| 亚洲乱码视频| 一区二区三区高清| 欧美区高清在线| 91久久精品www人人做人人爽| 影音先锋中文字幕一区| 久久久久青草大香线综合精品| 久久精品国产免费观看| 国产欧美一区二区色老头| 亚洲婷婷在线| 欧美一区二区三区婷婷月色 | 欧美午夜久久久| 亚洲精品乱码| 一区二区三区成人精品| 欧美日本在线| 亚洲精品日韩欧美| 亚洲一二三区精品| 国产精品羞羞答答| 亚洲欧美一区二区激情| 久久蜜桃资源一区二区老牛| 韩国一区电影| 你懂的亚洲视频| 亚洲人成网站999久久久综合| 日韩视频不卡| 欧美午夜久久久| 西瓜成人精品人成网站| 老鸭窝亚洲一区二区三区| 亚洲黄色一区| 欧美日韩福利在线观看| 亚洲图片欧美午夜| 久久久国产一区二区三区| 加勒比av一区二区| 欧美理论在线| 午夜欧美理论片| 麻豆av一区二区三区久久| 亚洲人体偷拍| 国产欧美精品xxxx另类| 老司机一区二区| 夜夜嗨一区二区| 久久人人97超碰国产公开结果 | 欧美日韩一区二区三区在线看| 亚洲视频免费观看| 久久久亚洲午夜电影| 亚洲啪啪91| 国产精品视频免费观看www| 久久久久久亚洲精品中文字幕| 亚洲黄页视频免费观看| 欧美有码在线观看视频| 亚洲激情视频在线播放| 国产乱码精品一区二区三| 美女91精品| 午夜精品久久久久久久白皮肤| 欧美高清视频一区二区| 欧美资源在线观看| 亚洲美女免费视频| 韩国一区二区三区美女美女秀| 欧美日韩天堂| 老司机精品久久| 欧美一区免费视频| 一二三区精品福利视频| 女女同性女同一区二区三区91| 先锋影音久久| 国产精品99久久久久久久女警| 在线看无码的免费网站| 国产日韩欧美精品综合| 国产精品jvid在线观看蜜臀| 欧美a一区二区| 久久高清免费观看| 亚洲永久在线| 亚洲无毛电影| 一本色道久久综合狠狠躁的推荐| 欧美二区在线看| 久久人人超碰| 久久久蜜桃一区二区人| 性伦欧美刺激片在线观看| 亚洲天堂av图片| 亚洲午夜精品久久| 一本不卡影院| 亚洲每日在线| 99国产精品久久久久老师 | 国产精品久久久久久户外露出| 欧美mv日韩mv国产网站app| 久久人体大胆视频| 久久久另类综合| 久久免费视频在线观看| 久久精品日产第一区二区| 欧美一区激情| 久久九九全国免费精品观看| 欧美影院成年免费版| 久久精品二区亚洲w码| 久久激情网站| 久久午夜精品| 欧美韩国在线| 欧美日韩国产影片| 欧美午夜宅男影院| 国产精品扒开腿做爽爽爽软件| 欧美性天天影院| 国产精品综合色区在线观看| 国产欧美日韩专区发布| 国产一区二区三区精品久久久 | 欧美日韩亚洲一区二区三区| 欧美精品 日韩| 欧美视频一区二| 国产精品亚洲综合| 国外成人在线视频网站| 亚洲国产毛片完整版| 亚洲精品四区| 亚洲自拍偷拍视频| 久久精品欧洲| 欧美激情免费观看| 夜夜嗨av一区二区三区四区| 午夜精品久久久久| 另类av导航| 国产精品夫妻自拍| 国产一区二区三区黄| 亚洲精品国产欧美| 亚洲免费中文| 欧美成人久久| 日韩亚洲欧美中文三级| 午夜精品久久久久久99热软件| 久热成人在线视频| 国产精品福利网站| 伊人色综合久久天天| 亚洲午夜精品久久久久久app| 久久精品国产免费观看| 亚洲韩国一区二区三区| 亚洲一区二区三区四区中文| 久久青草久久| 国产精品免费视频xxxx| 亚洲欧洲日本一区二区三区| 亚洲一区二区三区视频播放| 老司机午夜免费精品视频 | 亚洲国产成人在线播放| 一区二区三区日韩欧美精品| 久久三级视频| 国产伦精品一区二区三区高清| 亚洲区欧美区| 久久嫩草精品久久久久| 亚洲一区二区高清| 欧美黑人多人双交| 亚洲电影第三页| 久久精品视频在线看| 一本色道精品久久一区二区三区| 久久综合精品一区| 国产在线精品成人一区二区三区 |