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

巢穴

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲精品美女在线观看播放| 亚洲视屏在线播放| 老鸭窝亚洲一区二区三区| 亚洲国产日韩精品| 久久国产福利| 国产精品一区二区在线观看不卡| 亚洲三级免费电影| 欧美成在线视频| 久久深夜福利免费观看| 在线欧美三区| 欧美超级免费视 在线| 欧美自拍偷拍| 红桃视频成人| 欧美大香线蕉线伊人久久国产精品| 久久精品视频网| 一区视频在线播放| 欧美刺激午夜性久久久久久久| 久久久美女艺术照精彩视频福利播放 | 国内免费精品永久在线视频| 午夜精品福利一区二区蜜股av| 一区二区欧美在线观看| 欧美四级剧情无删版影片| 国产精品99久久久久久久久| 在线视频精品一| 国产乱码精品1区2区3区| 欧美主播一区二区三区| 欧美一区二区三区在线观看视频 | 亚洲精品视频免费| 亚洲国产1区| 欧美激情亚洲自拍| 中文网丁香综合网| 亚洲欧美久久久久一区二区三区| 国语自产精品视频在线看抢先版结局| 久久只有精品| 欧美韩日一区| 亚洲欧美偷拍卡通变态| 欧美一区二区性| 亚洲女人av| 久久五月激情| 亚洲视频一区二区| 欧美亚洲在线播放| 亚洲黄色成人网| 99视频精品免费观看| 国产综合精品| 亚洲欧洲日产国产综合网| 国产精品视频999| 欧美国产三级| 国产精品午夜在线| 亚洲国产一区在线| 国产麻豆精品视频| 亚洲国产精品热久久| 国产精品在线看| 亚洲高清久久久| 国产精品一香蕉国产线看观看| 老司机午夜精品视频| 欧美日韩一区二区三区在线看| 久久精品视频导航| 欧美超级免费视 在线| 欧美一区二区三区久久精品| 老司机一区二区三区| 亚洲在线成人| 欧美国产高潮xxxx1819| 欧美一区免费| 欧美国产一区视频在线观看| 欧美在线视频导航| 女同一区二区| 久久久夜色精品亚洲| 欧美日韩成人精品| 亚洲二区视频| 经典三级久久| 亚洲综合好骚| 亚洲天堂免费观看| 欧美高清视频一区二区| 久久视频国产精品免费视频在线| 欧美午夜在线观看| 亚洲高清一区二区三区| 激情亚洲网站| 亚洲欧美日韩系列| 欧美一级大片在线免费观看| 欧美日韩1区2区| 91久久国产精品91久久性色| 激情综合色综合久久| 亚洲欧美精品中文字幕在线| 亚洲一二区在线| 欧美日韩不卡视频| 亚洲免费成人av| 亚洲免费不卡| 欧美乱大交xxxxx| 亚洲欧洲精品一区二区三区波多野1战4| 在线不卡欧美| 玖玖综合伊人| 亚洲国产精品一区制服丝袜 | 国产精品一区二区三区久久| 亚洲精品一区二区网址| 亚洲欧洲日韩综合二区| 免费在线看成人av| 男男成人高潮片免费网站| 一区二区三区亚洲| 久久人人爽人人| 欧美日韩精品在线| 亚洲人成在线观看一区二区| 国产在线国偷精品产拍免费yy| 午夜久久久久久| 久久精品免费看| 狠狠色综合网| 免费中文日韩| 日韩午夜av在线| 亚洲深夜福利网站| 国产精品久久久久9999吃药| 亚洲女同同性videoxma| 久久久久久久999精品视频| 国产一区二区三区高清播放| 久久久伊人欧美| 亚洲欧洲视频| 欧美一区二区三区的| 国内精品视频在线观看| 久热精品视频在线| 亚洲精品一区二区三区四区高清| 香蕉乱码成人久久天堂爱免费| 国产欧美日韩综合一区在线观看| 久久久久久久网| 亚洲日本一区二区| 午夜精品网站| 亚洲高清久久| 欧美新色视频| 欧美一区二区三区四区在线| 亚洲大片在线观看| 亚洲欧美视频一区| 亚洲国产日韩欧美在线99| 欧美精品在线观看91| 亚洲一区自拍| 亚洲欧洲三级| 美女诱惑黄网站一区| 亚洲午夜激情网页| 国内精品美女在线观看| 欧美日韩第一区| 欧美伊人影院| 一本色道久久88综合亚洲精品ⅰ| 久久综合久久综合这里只有精品| 一本色道久久综合亚洲精品不卡 | 久热综合在线亚洲精品| 夜夜嗨av色综合久久久综合网 | 欧美日韩1234| 久久全球大尺度高清视频| 亚洲一区二区三区精品在线观看| 欧美69视频| 欧美影院在线播放| 日韩五码在线| 在线国产亚洲欧美| 国产精品久在线观看| 欧美国产一区二区在线观看 | 欧美日韩亚洲成人| 久久人91精品久久久久久不卡| 亚洲婷婷在线| 亚洲精品少妇网址| 免费欧美电影| 久久人体大胆视频| 欧美一区亚洲二区| 宅男精品视频| 亚洲黄色三级| 国内久久婷婷综合| 国精品一区二区三区| 国产精品久久久久久亚洲调教| 欧美精品一区二区三区在线播放| 噜噜噜在线观看免费视频日韩| 在线观看91精品国产麻豆| 免费在线亚洲欧美| 麻豆av一区二区三区| 久久精品72免费观看| 欧美一级黄色录像| 亚洲欧美日韩在线| 亚洲免费一级电影| 午夜精品视频在线| 久久久av水蜜桃| 午夜伦理片一区| 亚洲尤物视频网| 亚洲无玛一区| 亚洲午夜精品久久久久久浪潮| 亚洲美女色禁图| 亚洲精品色婷婷福利天堂| 亚洲国产成人91精品| 极品中文字幕一区| 精品电影一区| 亚洲国产精品一区| 亚洲精品一区二区三| 亚洲激情偷拍| 99re6热在线精品视频播放速度| 日韩视频―中文字幕| aⅴ色国产欧美| 亚洲少妇一区| 午夜欧美大尺度福利影院在线看 | 久久亚洲精选| 免费亚洲网站| 亚洲国产精品黑人久久久 | 国产精品美女xx| 国产精品视频免费在线观看| 国产欧美日韩一级| 在线播放中文字幕一区| 亚洲精品国产精品国自产观看浪潮| 亚洲精品日韩在线观看|