[체인 전진 성] [이분 찾기] [이분 도] 범인 수감.
원제 링크 설명
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극히 조 화 롭 지 못 하 다.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.우 리 는 '원한 치' (하나의 정수 치) 로 어떤 두 범죄자 간 의 원한 정 도 를 나타 내 고 원한 치가 클 수록 이 두 범죄자 간 의 원한 이 많아 진다.만약 에 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 발생 하고 영향력 이 c 인 충돌 사건 을 초래 할 것 이다.
매년 말 경찰 서 는 이 해 내 교도소 의 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 으로 만 든 뒤 S 성 Z 시장 에 게 상신 한다.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 사건 의 영향력 만 보 러 가 고, 영향 이 나 쁘 면 경찰국장 경질 을 검토 할 것 으로 보인다.
N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 범죄자 들 을 두 감옥 에서 재분배 할 계획 이다.같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 고 가정 하면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.
그렇다면 어떻게 범죄 자 를 배분 해 야 Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 을 까?이 최소 치 는 얼마 입 니까?
Input
파일 이름 을 prison. in 으로 입력 하 십시오.
입력 한 파일 의 줄 마다 두 개의 숫자 사 이 를 빈 칸 으로 구분 합 니 다.
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.데이터 보증 1 ≤ a j < b j ≤ N, 0 < c j ≤ 1, 000, 000, 000, 000, 000, 000, 그리고 각 범죄자 조합 에 한 번 만 나타 납 니 다.
Output
출력 파일 prison. out.
모두 1 행 으로 Z 시장 이 본 그 충돌 사건 의 영향력.올해 안에 감옥 에서 충돌 사건 이 발생 하지 않 았 다 면 0 을 출력 하 십시오.
Sample Input
4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884 Sample Output
3512
2 점 답안 에 check 의 해답 을 고려 하 다.분석: check 함수 부분: 모든 변 을 옮 겨 다 니 며 변 의 가중치 가 mid 보다 크 면 이분 도 염색 을 하고 mid 보다 작 으 면 조작 하지 않 습 니 다. 색상 이 같 을 수 있 고 색상 이 다 를 수 있 기 때 문 입 니 다.그림 을 옮 겨 다 니 는 부분: 이것 은 무 방향 유 권 도 입 니 다. dfs 가 이 그림 을 옮 겨 다 니 려 면 체인 식 앞 별 을 사용 하 는 방법 으로 그림 을 기록 하 는 것 을 고려 하 십시오.(인접 표 는 옮 겨 다 니 기 가 힘 들 고 인접 행렬 은 공간 과 시간 을 차지한다).이분 도 검사 와 체인 식 전진 성의 실현 에 관 하여 독자 가 스스로 검색 할 수 있다
#include
#include
#include
#include
using namespace std;
const int maxn = 2000000;
int head[maxn], w[maxn], color[maxn];
struct node {
int to, w, next; // , ,
}mmap[maxn];
int n, m, cnt, key;
void insert(int a, int b, int c) {
mmap[++cnt].to = b;
mmap[cnt].w = c;
mmap[cnt].next = head[a];
head[a] = cnt;
}
bool dfs(int v, int c) {
color[v] = c;
for (int i = head[v]; i != 0; i = mmap[i].next) {
if (mmap[i].w > key) {
if (color[mmap[i].to] == c) return false;
if (color[mmap[i].to] == 0 && !dfs(mmap[i].to, -c)) return false;
}
}
return true;
}
bool test(int mid) {
memset(color, 0, sizeof color);
key = w[mid];
for (int i = 1; i <= n; i++) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
return false;
}
}
}
return true;
}
int main () {
cin >> n >> m;
int a, b, c;
for (int i = 1; i <= m; i++) {
cin >> a >> b >> c;
insert(a, b, c);
insert(b, a, c);
w[i + 1] = c;
}
w[1] = 0;
sort(w + 1, w + m + 1);
int l = 1, r = m + 1, mid;
while(l < r) {
mid = (l + r) / 2;
if (test(mid)) r = mid;
else l = mid + 1;
}
cout << w[l];
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.