• 博客访问： 40257
• 博文数量： 1
• 博客积分： 227
• 博客等级： 二等列兵
• 技术积分： 30
• 用 户 组： 普通用户
• 注册时间： 2011-01-26 12:17

2011年（1）

2011-06-01 15:27:32

1. #include <iostream>
2. #include <algorithm>
3. #include <cstdio>
4. #include <cstring>
5. #include <cstdlib>

6. using namespace std;

7. const int M = 100000;
8. const int N = 20000;

9. struct EDGE {
10.         int a;
11.         int b;
12.         int v;
13. } edge[M];

14. int f[N * 2];

15. bool Compare(const EDGE &a, const EDGE &b)
16. {
17.         return a.v < b.v;
18. }

19. int Find(int x)
20. {
21.         if (f[x] == x) {
22.                 return f[x];
23.         } else {
24.                 return f[x] = Find(f[x]);
25.         }
26. }

27. int main()
28. {
29.         int n, m;

30.         ios::sync_with_stdio(false);

31.         cin >> n;
32.         cin >> m;
33.         for (int i = 0; i < m; i++) {
34.                 cin >> edge[i].a;
35.                 cin >> edge[i].b;
36.                 cin >> edge[i].v;
37.         }

38.         for (int i = 0; i < n * 2; i++) {
39.                 f[i] = i;
40.         }

41.         sort(edge, edge + m, Compare);

42.         for (int i = m - 1; i >= 0; i--) {
43.                 int x = Find(edge[i].a);
44.                 int y = Find(edge[i].b);

45.                 if (x == y) {
46.                         cout << edge[i].v << endl;

47.                         return 0;
48.                 }

49.                 int xx = Find(edge[i].a + n);
50.                 int yy = Find(edge[i].b + n);

51.                 f[x] = yy;
52.                 f[y] = xx;
53.         }

54.         cout << "0" << endl;

55.         return 0;
56. }

1. #include <cstdio>
2. #include <cstring>
3. #include <cstdlib>
4. #include <iostream>
5. #include <algorithm>
6. #include <queue>

7. const int kMaxN = 20000 + 1;
8. const int kMaxM = 100000 + 1;
9. const int kInf = 0x7FFFFFFF;

10. typedef struct graph *Graph;
12. typedef struct edge Edge;
13. struct graph {
14.         int V;
15.         int E;
17. };
18. struct node {
19.         int v;
20.         int len;
22. };
23. struct edge {
24.         int v;
25.         int w;
26.         int len;
27. };

28. struct prison {
29.         int v;
30.         int w;
31.         int len;
32. } people[kMaxM];

33. int n, m;

34. inline Graph GraphBuild(int v) {
35.         Graph t = (Graph)malloc(sizeof *t);

36.         t->V = v;
37.         t->E = 0;
39.         for (int i = 0; i <= v; i++) {
41.         }

42.         return t;
43. }

44. inline void GraphReset(Graph& G) {
45.         G->E = 0;
46.         for (int i = 0; i <= G->V; i++) {
48.         }
49. }

52.         t->v = v;
53.         t->len = len;
54.         t->next = next;

55.         return t;
56. }

57. inline Edge EdgeNew(int v, int w, int len) {
58.         Edge e;

59.         e.v = v;
60.         e.w = w;
61.         e.len = len;

62.         return e;
63. }

64. inline void GraphInsert(Graph &G, Edge e) {
65.         int v = e.v;
66.         int w = e.w;
67.         int len = e.len;

70.         G->E++;
71. }

72. inline bool BinaryGraphJudge(Graph &G) {
73.         std::queue<int> q;
74.         bool visited[kMaxN];
75.         int vertex_color[kMaxN];
76.         int visited_vertex = 0;

77.         memset(visited, false, sizeof(visited));
78.         memset(vertex_color, -1, sizeof(vertex_color));

79.         q.push(1);
80.         vertex_color[1] = 1;
81.         while (visited_vertex < G->V) {
82.                 if (q.empty()) {
83.                         for (int i = 1; i <= G->V; i++) {
84.                                 if (!visited[i]) {
85.                                         q.push(i);
86.                                         break;
87.                                 }
88.                         }
89.                 }

90.                 while (!q.empty()) {
91.                         int now;

93.                         now = q.front();
94.                         q.pop();
95.                         visited[now] = true;
96.                         visited_vertex++;
97.                         for (t = G->adj[now]; t != NULL; t = t->next) {
98.                                 if (vertex_color[t->v] == -1 || vertex_color[t->v] == 3 - vertex_color[now]) {
99.                                         vertex_color[t->v] = 3 - vertex_color[now];
100.                                 } else {
101.                                         return false;
102.                                 }

103.                                 if (!visited[t->v]) {
104.                                         q.push(t->v);
105.                                 }
106.                         }
107.                 }
108.         }

109.         return true;
110. }

111. inline void AddGraph(Graph &G, int mid_border) {
112.         GraphReset(G);

113.         for (int i = mid_border; i <= m; i++) {
114.                 GraphInsert(G, EdgeNew(people[i].v, people[i].w, people[i].len));
115.         }
116. }

117. inline int BinarySearch(Graph &G, int left_border, int right_border) {
118.         int mid_border;

119.         while (left_border < right_border) {
120.                 mid_border = (left_border + right_border) / 2;
121.

123.                 if (BinaryGraphJudge(G)) {
124.                         right_border = mid_border;
125.                 } else {
126.                         left_border = mid_border + 1;
127.                 }
128.         }

129.         return left_border - 1;
130. }

131. bool compare(const prison &a, const prison &b) {
132.         return a.len < b.len;
133. }

134. int main()
135. {
136.         int v, w, len;
137.         int ans;
138.         Graph G;

139.         std::ios::sync_with_stdio(false);
140.         std::cin >> n;
141.         std::cin >> m;
142.
143.         G = GraphBuild(n);
144.
145.         people[0].v = -1;
146.         people[0].w = -1;
147.         people[0].len = 0;
148.         for (int i = 1; i <= m; i++) {
149.                 std::cin >> v >> w >> n;
150.                 people[i].v = v;
151.                 people[i].w = w;
152.                 people[i].len = len;
153.         }

154.         std::sort(people, people + 1 + m, compare);
155.
156.         ans = BinarySearch(G, 0, m);
157.         std::cout << people[ans].len << std::endl;

158.         return 0;
159. }

0