• <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>
            

    
            

            




            







												


        


            


            巢穴
            

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





            
	    
    




            






            

				

            


    
    







            
	   
	



国产成人精品综合久久久久|
麻豆精品久久久久久久99蜜桃|
久久久精品一区二区三区|
久久av无码专区亚洲av桃花岛|
国内精品久久久人妻中文字幕|
国产精品九九九久久九九|
一本久久a久久精品综合夜夜
|
久久噜噜电影你懂的|
日日狠狠久久偷偷色综合免费|
亚洲人成伊人成综合网久久久|
久久久久久免费一区二区三区|
久久经典免费视频|
国产精品对白刺激久久久|
日韩美女18网站久久精品|
久久亚洲精品成人AV|
噜噜噜色噜噜噜久久|
国产精品久久久久影视不卡|
亚洲精品乱码久久久久久蜜桃图片
|
久久久久这里只有精品|
少妇人妻88久久中文字幕|
亚洲国产成人精品久久久国产成人一区二区三区综
|
久久综合日本熟妇|
狠狠色丁香婷婷综合久久来|
麻豆精品久久久久久久99蜜桃|
久久免费99精品国产自在现线|
国产精品美女久久久久av爽|
蜜臀av性久久久久蜜臀aⅴ麻豆|
国内精品伊人久久久久777|
久久国产免费直播|
国产精品免费久久久久影院|
蜜桃麻豆www久久|
精品国产福利久久久|
久久99精品综合国产首页|
久久久久久久亚洲Av无码|
久久精品夜夜夜夜夜久久|
久久精品国产99久久久古代|
国产69精品久久久久观看软件|
久久久久av无码免费网|
久久人人爽人人人人爽AV
|
久久天天躁夜夜躁狠狠|
亚洲性久久久影院|