gzwzm06

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

:: 管理 ::

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

<

2011年5月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

30

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

1

2

3

4

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

POJ 2060--Taxi Cab Scheme(最小路徑覆蓋)

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

1

#include <cstdio>
2

#include <cmath>
3

#include <memory.h>
4

5

const int SIZE = 501;
6

7

struct CAB
8

{
9

int m_sTime, m_eTime;
10

int m_srcX, m_srcY;
11

int m_desX, m_desY;
12

}ride[SIZE];
13

14

struct EDGE
15

{
16

int m_arr[SIZE];
17

int m_size;
18

}edge[SIZE];
19

20

int N, time[SIZE][2];
21

22

int link[SIZE];
23

bool visited[SIZE];
24

25

void 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

36

void 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

53

bool 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

76

int 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 巫閱讀(246) 評論(0) 編輯收藏引用所屬分類: 數據結構

只有注冊用戶登錄后才能發表評論。


相關文章: 7th GDCPC Problem H(DFS序 + 線段樹) POJ 3368 (RMQ) POJ 3368 Frequent values (線段樹) POJ 2060--Taxi Cab Scheme(最小路徑覆蓋) Atomic Nucleus Investigation (線段樹 n = 100000) POJ 2481(樹狀數組) POJ 2481 Cows(線段樹) POJ 3667 Hotel(模擬) Pku 2828(線段樹) Pku 2777(線段樹)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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