{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003esection pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\" class\u003d\"\"\u003e\n\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003csection id\u003d\"description\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\u003ch2\u003eDescription\u003c/h2\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003cdiv id\u003d\"problem_description\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\u003cp\u003e농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다.\u003c/p\u003e\r\n\r\n\u003cp\u003e두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최솟값으로 흐르게 된다. 예를 들어 용량이 5인 파이프가 용량이 3인 파이프와 연결되면 한개의 용량 3짜리 파이프가 된다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +---5---+---3---+ -\u0026gt; +---3---+\u003c/pre\u003e\r\n\r\n\u003cp\u003e게다가, 병렬로 연결돼 있는 배수관들은 각 용량의 합만큼의 물을 보낼 수 있다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +---5---+\r\n ---+ +--- -\u0026gt; +---8---+\r\n +---3---+\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e마지막으로, 어떤 것에도 연결돼 있지 않은 파이프는 물을 흐르게 하지 못하므로 제거된다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +---5---+\r\n ---+ -\u0026gt; +---3---+\r\n +---3---+--\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e이로 인해 복잡하게 연결된 모든 배수관들은 한개의 최대 유량을 갖는 배수관으로 만들어진다.\u003c/p\u003e\r\n\r\n\u003cp\u003e주어진 파이프들의 맵으로부터 우물(A)와 외양간(Z) 사이의 유량을 결정하라.\u003c/p\u003e\r\n\r\n\u003cp\u003e각 노드의 이름은 알파벳으로 지어져 있다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +-----------6-----------+\r\n A+---3---+B +Z\r\n +---3---+---5---+---4---+\r\n C D\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e파이프 BC와 CD는 합쳐질 수 있다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +-----------6-----------+\r\n A+---3---+B +Z\r\n +-----3-----+-----4-----+\r\n D\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e그러면 BD와 DZ 역시 합쳐질 수 있다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n +-----------6-----------+\r\n A+---3---+B +Z\r\n +-----------3-----------+\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e병렬 연결된 BZ 역시 합쳐진다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n B\r\n A+---3---+---9---+Z\r\n\u003c/pre\u003e\r\n\r\n\u003cp\u003e그러면 AB와 BZ 역시 합쳐질 수 있고 용량 3인 배수관 하나가 만들어진다.\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n A+---3---+Z\u003c/pre\u003e\r\n\r\n\u003cp\u003e한 파이프들의 집합을 읽고. 두개의 끝점을 가진 파이프로 만들어놓은 뒤 A부터 Z까지 흐르는 최대 유량을 계산하라. 모든 파이프들은 위의 규칙을 적용시켜 줄일 수 있다.\u003c/p\u003e\r\n\r\n\u003cp\u003ei번째 파이프는 두개의 다른 노드 a\u003csub\u003ei\u003c/sub\u003e와 b\u003csub\u003ei\u003c/sub\u003e와 연결돼 있고 F\u003csub\u003ei\u003c/sub\u003e (1 ≤ F\u003csub\u003ei\u003c/sub\u003e ≤ 1,000)만큼의 유량을 갖는다. 알파벳은 같지만, 대소문자가 다르면 다른 문자이다. 파이프는 양방향으로 흐를 수 있다.\u003c/p\u003e\r\n\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\t\u003csection id\u003d\"input\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\t\u003ch2\u003eInput\u003c/h2\u003e\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003cdiv id\u003d\"problem_input\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\u003cp\u003e첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위치에 파이프의 용량이 주어진다.\u003c/p\u003e\r\n\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003c/section\u003e\n\t\t\t\t\u003c/div\u003e\n\t\n\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\t\u003csection id\u003d\"output\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\t\u003ch2\u003eOutput\u003c/h2\u003e\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003cdiv id\u003d\"problem_output\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\u003cp\u003e첫째 줄에 A에서 Z까지의 최대 유량을 출력한다.\u003c/p\u003e\r\n\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003c/section\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\u003csection id\u003d\"limit\" style\u003d\"display:none;\" class\u003d\"problem-section\"\u003e\n\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\u003ch2\u003eLimit\u003c/h2\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\u003cdiv id\u003d\"problem_limit\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\t\u003c/div\u003e\n\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"row\"\u003e\n\t\t\t\t\t\u003cdiv\u003e\u003ch2\u003eSample 1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\nA B 3\nB C 3\nC D 5\nD Z 4\nB Z 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003csection id\u003d\"hint\" style\u003d\"display: none;\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\u003ch2\u003eHints\u003c/h2\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003cdiv id\u003d\"problem_hint\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\u003cdiv style\u003d\"display: none;\"\u003e\n\t\t\t\t\t\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\u003c/div\u003e"}}]}