본문 바로가기

플로이드 워셜

BOJ)14938 서강그라운드 문제: icpc.me/14938 n의 범위가 작고 다대다 최단거리를 필요로 하기 때문에 플로이드 워셜 알고리즘을 사용할 수 있다.플로이드 워셜 알고리즘으로 모든 정점쌍의 최단거리를 구해준 후 , 모든 정점을 기준으로 얻을 수 있는 아이템의 개수를 세준 뒤 그 중에 최댓값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, m, r, item[111], a[111][111], res;int main() { memset(a, 0x3f, sizeof(a)); scanf("%d%d%d", &n, &m, &r); for (int i = 1.. 더보기
BOJ)5651 완전 중요한 간선 문제: icpc.me/5651 어떤 그래프에서 플로우를 흘렸을 때 어떤 간선의 용량이 1 줄어들면 최대유량도 1 줄어들게 되는 간선을 완전 중요한 간선이라 할 때 그러한 간선의 수를 구하는 문제이다. 유량을 최대로 흘렸을 때 해당 간선에 용량을 줄였을 때 maximum flow에 직접적인 타격을 주려면 해당 유량이 해당 간선으로 밖에 통하지 못하여야 한다. 즉 유량 그래프에서 u->v로의 경로가 유일해야 한다. 답을 구하기 위해 유량을 흘려준 뒤 플로이드 워셜을 이용해 transitive closure를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565.. 더보기
BOJ)2610 회의준비 문제: icpc.me/2610 각각의 컴포넌트에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들의 최댓값이 최소가 되는 정점들을 출력하는 문제이다. 각 정점들간의 최단거리는 플로이드 워셜을 이용하여 구해주면 되고 어떤 컴포넌트에 속한 정점에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들 중 최댓값을 힙에 저장하여 순서대로 답에 넣어주는 것으로 문제를 해결할 수 있다. 힙을 볼 때 이미 처리한 컴포넌트에 속한 정점은 지나쳐주어야하는데 이는 disjoint-set을 이용하면 간단하게 해결해줄 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859.. 더보기
BOJ)1058 친구 문제: icpc.me/1058 2-친구수가 가장 많은 사람의 2-친구 수를 구하는 문제이다. 2-친구의 수는 플로이드 워셜을 통하여 구한 최단거리가 2이하인 모든 정점들의 합으로 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, a[51][51], r;char b;int main() { scanf("%d", &n); memset(a, 0x3f, sizeof(a)); for (int i = 1; i 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)2660 회장뽑기 문제:icpc.me/2660 두 사람의 친구 관계가 주어질 때 어떤 사람이 가장 먼 친구 관계가 n다리 걸쳐서 친구관계가 된다면 그 사람의 점수는 n점이라 할 때 최소 점수를 갖는 사람들이 회장 후보가 된다. 회장 후보를 출력하는 문제이다. 두사람의 친구 관계를 cost가 1인 간선으로 표현한다면 플로이드 워셜을 통하여 n:n 최단거리를 구해주면 두 사람의 친구 관계가 몇다리 걸쳐있는지 알 수있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int n, x, y, a[51][51], r, b[51];int main().. 더보기
BOJ)13168 내일로 여행 문제: icpc.me/13168 최단 거리로 각각의 도시들을 순서대로 여행 다닐 때 내일로 티켓을 구매할지 안할지 결정해 주면 된다. 내일로 티켓을 구매 했을 경우와 구매하지 않았을 경우에 대하여 각각 그래프를 만들어 준 후 n이 100밖에 안되니 플로이드 워셜을 돌려주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #include #include #include #define INF 987654321using namespace std.. 더보기

티스토리툴바