-
Notifications
You must be signed in to change notification settings - Fork 0
/
165_NationalAntColony.cpp
49 lines (49 loc) · 1.1 KB
/
165_NationalAntColony.cpp
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
int V,E,C;
int ant[50005],v[70005][3],h[50005],visit[50005];
int i,j,t1,t2,t3,cnt;
int l,r,mid;
int head(int x){
if (h[x] != x) return h[x] = head(h[x]);
return x;
}
bool f(int x){
cnt = 0;
for (i = 1; i <= V; i++){
h[i] = i;
visit[i] = -1;
}
for (i = 0; i < E; i++){
if (v[i][2] <= x) continue;
h[head(v[i][0])] = head(v[i][1]);
}
for (i = 1; i <= V; i++){
if (visit[ant[i]] == -1) visit[ant[i]] = head(i);
else if (visit[ant[i]] != head(i)) cnt++;
}
if (cnt == 0) return 1;
return 0;
}
int main(){
scanf("%d%d%d",&V,&E,&C);
for (i = 1; i <= V; i++) scanf("%d",&ant[i]);
for (i = 0; i < E; i++){
scanf("%d%d%d",&t1,&t2,&t3);
v[i][0] = t1;
v[i][1] = t2;
v[i][2] = t3;
}
l = 0; r = 10e9;
while (l <= r){
mid = l+r>>1;
if (!f(mid)) r = mid-1;
else if (f(mid) && f(mid+1)) l = mid+1;
else break;
}
cnt = 0;
for (i = 0; i < E; i++){
if (v[i][2] <= mid) cnt++;
}
cout << cnt;
}