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

30807번 - TSM 스페셜 저지다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
8 초 1024 MB3731038930.690%

문제

가중치 있는 그래프가 주어졌을 때, 최소 스패닝 트리(MST)의 비용을 구하는 문제는 잘 알려져 있습니다. 최소 스패닝 트리의 비용이 주어졌을 때, 그래프의 간선에 가중치를 부여하는 문제를 해결하세요.

자세한 설명은 아래와 같습니다.

  • 최소 스패닝 트리란, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 비용이 최소인 트리를 뜻합니다. 스패닝 트리의 비용은 트리에 포함된 간선의 가중치 합으로 정의합니다.
  • 주어지는 그래프는 $N$개의 정점과 $M$개의 간선을 가진 무방향 연결 그래프입니다. 각 정점과 각 간선에는 1ドル$번부터 순서대로 번호가 붙어 있습니다. $i$번 간선은 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에는 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있습니다.
  • 각 간선에 적절한 가중치를 부여해서 최소 스패닝 트리의 비용이 $K$가 되도록 만드세요.

입력

첫 번째 줄에 그래프의 정점의 수 $N$과 간선의 수 $M,ドル 최소 스패닝 트리의 비용 $K$가 공백으로 구분되어 주어집니다. $(2 \le N \le 100,円 000;\ N-1 \le M \le 200,円 000;\ 0 \le K \le 10^{10})$

다음 $M$개의 줄의 $i$번째 줄에 정수 $u_i, v_i, l_i, r_i$가 공백으로 구분되어 주어집니다. $i$번 간선이 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있음을 의미합니다. $(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 0 \le l_i \le r_i \le 100,円 000)$

주어지는 그래프는 연결 그래프이며, 서로 다른 간선은 같은 정점 쌍을 잇지 않습니다.

출력

스패닝 트리의 비용이 $K$가 되도록 가중치를 부여할 수 있다면 첫 줄에 YES, 불가능하다면 NO를 출력합니다.YES를 출력한 경우 추가로 $M$개의 줄을 출력합니다. 그중 $i$번째 줄에는 $i$번째 간선에 부여할 가중치를 출력합니다.

제한

예제 입력 1 

4 5 10
1 2 0 5
1 3 7 9
1 4 1 6
2 4 3 4
3 4 2 2

예제 출력 1 

YES
5
7
4
4
2

예제 입력 2 

4 5 12
1 2 0 5
1 3 7 9
1 4 1 6
2 4 3 4
3 4 2 2

예제 출력 2 

NO

힌트

W3sicHJvYmxlbV9pZCI6IjMwODA3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiVFNNIiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMDBcdWM5MTFcdWNlNTggXHVjNzg4XHViMjk0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWMxOGMgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhYyhNU1QpXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHViMjk0IFx1Yzc5OCBcdWM1NGNcdWI4MjRcdWM4MzggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWNkNWNcdWMxOGMgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWMwNFx1YzEyMFx1YzVkMCBcdWFjMDBcdWM5MTFcdWNlNThcdWI5N2MgXHViZDgwXHVjNWVjXHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzEzOFx1ZDU1YyBcdWMxMjRcdWJhODVcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWNkNWNcdWMxOGMgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yjc4MCwgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHViNGU0XHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCBcdWJkODBcdWJkODQgXHVhZGY4XHViNzk4XHVkNTA0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjZDVjXHVjMThjXHVjNzc4IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWI3M2JcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWNcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzQwIFx1ZDJiOFx1YjlhY1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWMwMFx1YzkxMVx1Y2U1OCBcdWQ1NjlcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTY5XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVhZGY4XHViNzk4XHVkNTA0XHViMjk0ICROJFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWFjZmMgJE0kXHVhYzFjXHVjNzU4IFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWFjMDBcdWM5YzQgXHViYjM0XHViYzI5XHVkNWE1IFx1YzVmMFx1YWNiMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWM4MTBcdWFjZmMgXHVhYzAxIFx1YWMwNFx1YzEyMFx1YzVkMFx1YjI5NCAkMSRcdWJjODhcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1YjQgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiAkaSRcdWJjODggXHVhYzA0XHVjMTIwXHVjNzQwICR1X2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1YWNmYyAkdl9pJFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVjNzc0XHVjNzNjXHViYTcwLCAkaSRcdWJjODggXHVhYzA0XHVjMTIwXHVjNWQwXHViMjk0ICRsX2kkIFx1Yzc3NFx1YzBjMSAkcl9pJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4IFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWJkODBcdWM1ZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YWMwNFx1YzEyMFx1YzVkMCBcdWM4MDFcdWM4MDhcdWQ1NWMgXHVhYzAwXHVjOTExXHVjZTU4XHViOTdjIFx1YmQ4MFx1YzVlY1x1ZDU3NFx1YzExYyBcdWNkNWNcdWMxOGMgXHVjMmE0XHVkMzI4XHViMmRkIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgJEskXHVhYzAwIFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWI5Y2NcdWI0ZGNcdWMxMzhcdWM2OTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHVjMjE4ICROJFx1YWNmYyBcdWFjMDRcdWMxMjBcdWM3NTggXHVjMjE4ICRNJCwgXHVjZDVjXHVjMThjIFx1YzJhNFx1ZDMyOFx1YjJkZCBcdWQyYjhcdWI5YWNcdWM3NTggXHViZTQ0XHVjNmE5ICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gJCgyIFxcbGUgTiBcXGxlIDEwMFxcLCAwMDA7XFwgTi0xIFxcbGUgTSBcXGxlIDIwMFxcLCAwMDA7XFwgMCBcXGxlIEsgXFxsZSAxMF57MTB9KSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjICRNJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NTggJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWMyMTggJHVfaSwgdl9pLCBsX2ksIHJfaSRcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICRpJFx1YmM4OCBcdWFjMDRcdWMxMjBcdWM3NzQgJHVfaSRcdWJjODggXHVjODE1XHVjODEwXHVhY2ZjICR2X2kkXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc0NCBcdWM3NzRcdWM3M2NcdWJhNzAsICRpJFx1YmM4OCBcdWFjMDRcdWMxMjBcdWM1ZDAgJGxfaSQgXHVjNzc0XHVjMGMxICRyX2kkIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMTggXHVhYzAwXHVjOTExXHVjZTU4XHViOTdjIFx1YmQ4MFx1YzVlY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU2OVx1YjJjOFx1YjJlNC4gJCgxIFxcbGUgdV9pLCB2X2kgXFxsZSBOO1xcIHVfaSBcXG5lIHZfaTtcXCAwIFxcbGUgbF9pIFxcbGUgcl9pIFxcbGUgMTAwXFwsIDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgXHVjNWYwXHVhY2IwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc3NFx1YmE3MCwgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjMDRcdWMxMjBcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzgxMCBcdWMzMGRcdWM3NDQgXHVjNzg3XHVjOWMwIFx1YzU0YVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMyYTRcdWQzMjhcdWIyZGQgXHVkMmI4XHViOWFjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCAkSyRcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWJkODBcdWM1ZWNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWNjYWIgXHVjOTA0XHVjNWQwIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ZRVM8XC9jb2RlPjxcL3NwYW4+LCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTRcdWJhNzQgPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPk5PPFwvY29kZT48XC9zcGFuPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPllFUzxcL2NvZGU+PFwvc3Bhbj5cdWI5N2MgXHVjZDljXHViODI1XHVkNTVjIFx1YWNiZFx1YzZiMCBcdWNkOTRcdWFjMDBcdWI4NWMgJE0kXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YzkxMSAkaSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0ICRpJFx1YmM4OFx1YzlmOCBcdWFjMDRcdWMxMjBcdWM1ZDAgXHViZDgwXHVjNWVjXHVkNTYwIFx1YWMwMFx1YzkxMVx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA4MDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUU00iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBwcm9ibGVtIG9mIGZpbmRpbmcgYSBNaW5pbXVtIFNwYW5uaW5nIFRyZWUoTVNUKSBpbiBhIHdlaWdodGVkIGdyYXBoIGlzIHdlbGwta25vd24uIFNvbHZlIHRoZSBwcm9ibGVtIG9mIGFzc2lnbmluZyB3ZWlnaHRzIHRvIHRoZSBlZGdlcyBvZiBhIGdyYXBoLCBnaXZlbiB0aGUgY29zdCBvZiB0aGUgTWluaW11bSBTcGFubmluZyBUcmVlLjxcL3A+XHJcblxyXG48cD5UaGUgZGV0YWlscyBvZiB0aGUgcHJvYmxlbSBhcmUgYXMgZm9sbG93czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIE1pbmltdW0gU3Bhbm5pbmcgVHJlZSBpcyBhIHN1YmdyYXBoIHRoYXQgY29ubmVjdHMgYWxsIG5vZGVzIG9mIHRoZSBnaXZlbiBncmFwaCBpbiB0aGUgZm9ybSBvZiBhIHRyZWUgd2l0aCBtaW5pbXVtIGNvc3QuIFRoZSBjb3N0IG9mIHRoZSB0cmVlIGlzIGRlZmluZWQgYXMgdGhlIHN1bSBvZiB0aGUgd2VpZ2h0cyBvZiB0aGUgZWRnZXMuPFwvbGk+XHJcblx0PGxpPlRoZSBnaXZlbiBncmFwaCBpcyBhbiB1bmRpcmVjdGVkIGdyYXBoIHdpdGggJE4kIG5vZGVzIGFuZCAkTSQgZWRnZXMuIEVhY2ggbm9kZSBhbmQgZWFjaCBlZGdlIGlzIG51bWJlcmVkIGluIG9yZGVyIHN0YXJ0aW5nIGZyb20gJDEkLiBUaGUgJGkkLXRoIGVkZ2UgY29ubmVjdHMgbm9kZXMgJHVfaSQgYW5kICR2X2kkLCBhbmQgYSB3ZWlnaHQgYmV0d2VlbiAkbF9pJCBhbmQgJHJfaSQgaW5jbHVzaXZlIGNhbiBiZSBhc3NpZ25lZCB0byB0aGUgJGkkLXRoIGVkZ2UuPFwvbGk+XHJcblx0PGxpPkJ5IGFzc2lnbmluZyBzdWl0YWJsZSB3ZWlnaHRzIHRvIHRoZSBlZGdlcywgc2V0ICRLJCBhcyB0aGUgY29zdCBvZiB0aGUgTWluaW11bSBTcGFubmluZyBUcmVlLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kLCAkTSQsIGFuZCAkSyQsIGRlbm90aW5nIHRoZSBudW1iZXIgb2Ygbm9kZXMsIHRoZSBudW1iZXIgb2YgZWRnZXMsIGFuZCB0aGUgY29zdCBvZiB0aGUgTWluaW11bSBTcGFubmluZyBUcmVlIG9mIHRoZSBncmFwaCwgcmVzcGVjdGl2ZWx5LiAkKDIgXFxsZSBOIFxcbGUgMTAwXFwsIDAwMDtcXCBOLTEgXFxsZSBNIFxcbGUgMjAwXFwsIDAwMDtcXCAwIFxcbGUgSyBcXGxlIDEwXnsxMH0pJDxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBmb2xsb3dpbmcgJE0kIGxpbmVzIG9mIGlucHV0IGNvbnRhaW5zIGZvdXIgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICR1X2ksIHZfaSwgbF9pLCByX2kkLCBkZW5vdGluZyB0aGF0IHRoZSAkaSQtdGggZWRnZSBjb25uZWN0cyBub2RlcyAkdV9pJCBhbmQgJHZfaSQsIGFuZCBhIHdlaWdodCBiZXR3ZWVuICRsX2kkIGFuZCAkcl9pJCBpbmNsdXNpdmUgY2FuIGJlIGFzc2lnbmVkIHRvIHRoZSAkaSQtdGggZWRnZS4gJCgxIFxcbGUgdV9pLCB2X2kgXFxsZSBOO1xcIHVfaSBcXG5lIHZfaTtcXCAwIFxcbGUgbF9pIFxcbGUgcl9pIFxcbGUgMTAwXFwsIDAwMCkkPFwvcD5cclxuXHJcbjxwPkl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgZ2l2ZW4gZ3JhcGggaXMgY29ubmVjdGVkIGFuZCBubyB0d28gZWRnZXMgY29ubmVjdCB0aGUgc2FtZSBwYWlyIG9mIG5vZGVzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZXJlIGV4aXN0cyBhbiBhc3NpZ25tZW50IG9mIHdlaWdodHMgc3VjaCB0aGF0IHRoZSBjb3N0IG9mIHRoZSBNaW5pbXVtIFNwYW5uaW5nIFRyZWUgaXMgJEskLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+WUVTPFwvY29kZT48XC9zcGFuPiBpbiB0aGUgZmlyc3QgbGluZS4gT3RoZXJ3aXNlLCBwcmludCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Tk88XC9jb2RlPjxcL3NwYW4+LjxcL3A+XHJcblxyXG48cD5JZiB0aGUgYW5zd2VyIGlzIDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ZRVM8XC9jb2RlPjxcL3NwYW4+LCBwcmludCBhbiBhZGRpdGlvbmFsICRNJCBsaW5lcyBvZiBvdXRwdXQuIFRoZSAkaSQtdGggb2YgdGhlICRNJCBsaW5lcyBzaG91bGQgY29udGFpbiB0aGUgd2VpZ2h0IHRvIGJlIGFzc2lnbmVkIHRvIHRoZSAkaSQtdGggZWRnZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > solved.ac > solved.ac Grand Arena #3 > Division 2 F번

Contest > solved.ac > solved.ac Grand Arena #3 > Division 1 B번

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

출처

대학교 대회

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

AltStyle によって変換されたページ (->オリジナル) /