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

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				1 
				隨筆 ::
				52 文章
				::
				17 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		最小路徑覆蓋 =  |N| - 最大匹配數
            

              1#include <cstdio>
              2#include <cmath>
              3#include <memory.h>
              4
              5const int SIZE = 501;
              6
              7struct CAB
              8{
              9    int m_sTime, m_eTime;
             10    int m_srcX, m_srcY;
             11    int m_desX, m_desY;
             12}            ride[SIZE];
             13
             14struct EDGE
             15{
             16    int m_arr[SIZE];
             17    int m_size;
             18}            edge[SIZE];
             19
             20int N, time[SIZE][2];
             21
             22int link[SIZE];
             23bool visited[SIZE];
             24
             25void Init()
             26{
             27    int i;
             28
             29    for ( i = 0; i < N; ++i )
             30    {
             31        edge[i].m_size = 0;
             32        link[i] = -1;
             33    }
             34}
             35
             36void Build()
             37{
             38    int i, j, t;
             39
             40    for ( i = 0; i < N; ++i )
             41        for ( j = i + 1; j < N; ++j )
             42        {
             43            if ( i == j )
             44                continue;
             45            t = abs(ride[i].m_desX - ride[j].m_srcX) + abs(ride[i].m_desY - ride[j].m_srcY);
             46            if ( t + ride[i].m_eTime < ride[j].m_sTime )
             47            {
             48                edge[i].m_arr[edge[i].m_size++] = j;
             49            }
             50        }
             51}
             52
             53bool Find( const int& v )
             54{
             55    int i, x;
             56
             57    for ( i = 0; i < edge[v].m_size; ++i )
             58    {
             59        x = edge[v].m_arr[i];
             60
             61        if ( !visited[x] )
             62        {
             63            visited[x] = true;
             64
             65            if ( link[x] == -1 || Find( link[x] ) )
             66            {
             67                link[x] = v;
             68                return true;
             69            }
             70        }
             71    }
             72
             73    return false;
             74}
             75
             76int main()
             77{
             78//    freopen("1.txt", "r", stdin);
             79
             80    int test, i, t;
             81    char str_time[10];
             82
             83    scanf("%d", &test);
             84
             85    while ( test-- )
             86    {
             87        scanf("%d", &N);
             88
             89        Init();
             90
             91        for ( i = 0; i < N; ++i )
             92        {
             93            scanf("%s %d %d %d %d", str_time, &ride[i].m_srcX, &ride[i].m_srcY, 
             94                &ride[i].m_desX, &ride[i].m_desY);
             95
             96            t = (str_time[0] - '0') * 10 + str_time[1] - '0';
             97
             98            t = t * 60 + (str_time[3] - '0') * 10 + str_time[4] - '0';
             99
            100            ride[i].m_sTime = t;
            101            ride[i].m_eTime = t + abs(ride[i].m_srcX - ride[i].m_desX)
            102                            + abs(ride[i].m_srcY - ride[i].m_desY);
            103        }
            104
            105        Build();
            106
            107        t = 0;
            108        for ( i = 0; i < N; ++i )
            109        {
            110            memset(visited, 0, sizeof(visited));
            111
            112            if ( Find( i ) )
            113                t++;
            114        }
            115
            116        t = N - t;
            117
            118        printf("%d\n", t);
            119    }
            120    return 0;
            121}
            

	
            
	
	
            
		posted on 2009-04-22 20:33 巫 閱讀(231) 評論(0)  編輯 收藏 引用  所屬分類: 數據結構 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



狠色狠色狠狠色综合久久|
一级女性全黄久久生活片免费|
亚洲精品国产字幕久久不卡|
午夜精品久久久久久毛片|
欧美综合天天夜夜久久|
欧美激情精品久久久久久|
亚洲精品乱码久久久久久按摩|
99久久国产综合精品麻豆|
久久av免费天堂小草播放|
久久人人爽人人爽人人爽|
国产亚洲精品美女久久久|
很黄很污的网站久久mimi色|
国产A级毛片久久久精品毛片|
狠狠干狠狠久久|
久久久久久曰本AV免费免费|
中文字幕亚洲综合久久|
午夜天堂av天堂久久久|
欧美午夜A∨大片久久|
国产99久久精品一区二区|
久久精品国产精品亚洲精品|
国产精品美女久久久久av爽|
欧美精品一区二区久久|
久久精品国产亚洲网站|
99精品国产免费久久久久久下载
|
久久亚洲综合色一区二区三区|
一级a性色生活片久久无少妇一级婬片免费放|
久久久一本精品99久久精品66|
久久青青草原精品国产软件|
伊人久久大香线蕉精品|
国产一区二区三区久久精品|
婷婷五月深深久久精品|
少妇无套内谢久久久久|
中文国产成人精品久久亚洲精品AⅤ无码精品
|
2021国产成人精品久久|
国产国产成人精品久久|
狠狠88综合久久久久综合网|
亚洲中文久久精品无码|
亚洲人成网亚洲欧洲无码久久
|
国产精品免费久久久久电影网|
东京热TOKYO综合久久精品|
久久久久久九九99精品|