글 읽기 - 이분탐색관련 주석있습니다!

(追記) (追記ここまで)

이분탐색관련 주석있습니다!

3666번 - 리스크

gks10101 1년 전 0

전역변수 inf를 1억으로 설정했고 이분탐색돌릴때 l을 0으로 r을 천만으로 할떄는 맞았습니다인데 r=inf로 하면 틀립니다 이유가뭘까요 int범위넘어가는 것도아닌데... 141번 줄입니다!!

#pragma warning (disable: 4996)
#define _CRT_NO_SECURE_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
struct node {
	int index, c, f;
	struct node* next;
	struct node* oppo;
};
struct node nodepool[2 * 101 * 101 + 6 * 101];
struct node head[205];
struct node* path[205];
int nodepoolcnt;
int t, n;
char a;
int que[205];
int army[205];
int pre[205];
int mine[205];
int closed[205];
int num, my;
int rear, front, s, e;
int inf = 100000000;
void push(int x, int y, int c) { //리스트에 삽입
	struct node* cursor1 = &nodepool[nodepoolcnt++];
	cursor1->c = c;
	cursor1->index = y;
	cursor1->next = head[x].next;
	head[x].next = cursor1;
	struct node* cursor2 = &nodepool[nodepoolcnt++];
	cursor2->c = 0;
	cursor2->index = x;
	cursor2->next = head[y].next;
	head[y].next = cursor2;
	cursor1->oppo = cursor2;
	cursor2->oppo = cursor1;
}
void init() {
	scanf("%d", &n);
	num = 0;
	my = 0;
	nodepoolcnt = 0;
	s = 0;
	e = 2 * n + 1;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &army[i]);
		if (army[i]>0) mine[i] = 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf(" %c", &a);
			if (a == 'Y') {
				if (mine[i] == 1 && mine[j] == 1) {
					push(i, j + n, inf);
				}
				else {
					closed[i] = mine[i];
					closed[j] = mine[j];
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (closed[i] == 1) num++;
	}
	for (int i = 1; i <= n; i++) {
		if (mine[i] == 1) {
			my++;
			push(i, i + n, inf);
			push(s, i, army[i]);
			push(i + n, e, 1);
		}
	}
}
int min(int g, int h) {
	return (g < h) ? g : h;
}
int networkflow() { //최대유량
	int max = 0;
	while (1) {
		rear = 0;
		front = 0;
		for (int i = 0; i <= e; i++) {
			pre[i] = -1;
			path[i] = NULL;
		}
		que[rear++] = s;
		while (rear != front && pre[e] == -1) {
			int curr = que[front++];
			struct node* cursor = head[curr].next;
			while (cursor != NULL) {
				int next = cursor->index;
				if (cursor->c - cursor->f > 0 && pre[next] == -1) {
					que[rear++] = next;
					pre[next] = curr;
					path[next] = cursor;
					if (next == e) break;
				}
				cursor = cursor->next;
			}
		}
		if (pre[e] == -1) break;
		int flow = inf;
		for (int i = e; i != s; i = pre[i]) {
			flow = min(flow, path[i]->c - path[i]->f);
		}
		for (int i = e; i != s; i = pre[i]) {
			path[i]->f += flow;
			path[i]->oppo->f -= flow;
		}
		max += flow;
	}
	return max;
}
void reset() {
	for (int i = 0; i <= e; i++) {
		mine[i] = 0;
		closed[i] = 0;
		head[i].next = NULL;
	}
}
int main() {
	scanf("%d", &t);
	while (t--) {
		init();
 //맞는 코드
		int l = 0, r = 10000000;
 //틀린 코드 -> r = inf;
		while (l <= r) {
			int mid = (l + r) / 2;
			for (int i = 0; i <= e; i++) {
				struct node* cursor = head[i].next;
				while (cursor != NULL) {
					cursor->f = 0;
					if (cursor->index == e && closed[cursor->oppo->index - n] == 1) {
						cursor->c = mid;
					}
					cursor = cursor->next;
				}
			}
			if (networkflow() < mid * num + my - num) r = mid - 1;
			else l = mid + 1;
		}
		printf("%d\n", r);
		reset();
	}
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

이분탐색관련 주석있습니다!

gks10101 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말