gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 2060--Taxi Cab Scheme(最小路径覆盖)
最小路径覆盖 =  |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 巫 阅读(217) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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