ผลต่างระหว่างรุ่นของ "Apr23 steiner"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'ให้กราฟ '''G''' แบบมีทิศทาง ที่มีโหนด '''N''' โหนด ('''N''' <= 1 000) ม...') |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
ให้กราฟ '''G''' แบบมีทิศทาง ที่มีโหนด '''N''' โหนด ('''N''' <= 1 000) มีเส้นเชื่อมที่มีทิศทางและมีน้ำหนัก '''M''' เส้น ('''M''' <= 50 000) (ระหว่างโหนดคู่หนึ่ง อาจมีเส้นเชื่อมได้มากกว่าหนึ่งเส้น) โหนดในกราฟมีหมายเลข 0, 1, ..., '''N''' - 1 | ให้กราฟ '''G''' แบบมีทิศทาง ที่มีโหนด '''N''' โหนด ('''N''' <= 1 000) มีเส้นเชื่อมที่มีทิศทางและมีน้ำหนัก '''M''' เส้น ('''M''' <= 50 000) (ระหว่างโหนดคู่หนึ่ง อาจมีเส้นเชื่อมได้มากกว่าหนึ่งเส้น) โหนดในกราฟมีหมายเลข 0, 1, ..., '''N''' - 1 | ||
| − | ให้เซตของจุดยอด '''T''' | + | ให้เซตของจุดยอด '''T''' ที่มีขนาด '''K''' ('''K''' <= 10) เราต้องการหาต้นไม้ที่มีทิศทาง (arborescence) ที่เป็น subgraph ของ '''G''' ที่มีโหนด 0 เป็นโหนดราก และเชื่อมไปยังทุก ๆ โหนดใน '''T''' (อาจจะมีโหนดอื่นร่วมด้วยได้) ที่มีน้ำหนักน้อยที่สุด (นิยามน้ำหนักของต้นไม้เท่ากับผลรวมของนำหนักของเส้นเชื่อมในต้นไม้ทั้งหมด) |
'''ข้อมูลนำเข้า''' | '''ข้อมูลนำเข้า''' | ||
| แถว 7: | แถว 7: | ||
* บรรทัดแรกระบุจำนวนเต็ม '''N''' และ '''M''' แทนจำนวนโหนดและจำนวนเส้นเชื่อม | * บรรทัดแรกระบุจำนวนเต็ม '''N''' และ '''M''' แทนจำนวนโหนดและจำนวนเส้นเชื่อม | ||
* อีก M บรรทัดระบุเส้นเชื่อม โดยระบุจำนวนเต็ม '''A''' '''B''' และ '''C''' เพื่อระบุว่ามีเส้นเชื่อมจากโหนด '''A''' ไปยังโหนด '''B''' ที่มีน้ำหนัก '''C''' | * อีก M บรรทัดระบุเส้นเชื่อม โดยระบุจำนวนเต็ม '''A''' '''B''' และ '''C''' เพื่อระบุว่ามีเส้นเชื่อมจากโหนด '''A''' ไปยังโหนด '''B''' ที่มีน้ำหนัก '''C''' | ||
| + | * บรรทัดถัดไประบุจำนวนเต็ม '''K''' แทนขนาดของ '''T''' | ||
| + | * บรรทัดถัดไประบุจำนวนเต็ม '''K''' จำนวน แทนหมายเลขโหนดในเซต '''T''' | ||
'''ข้อมูลส่งออก'' | '''ข้อมูลส่งออก'' | ||
| แถว 28: | แถว 30: | ||
Output: | Output: | ||
<pre>3 | <pre>3 | ||
| + | </pre> | ||
| + | |||
| + | '''ตัวอย่าง 2''' | ||
| + | |||
| + | Input: | ||
| + | <pre>6 6 | ||
| + | 0 1 10 | ||
| + | 1 3 10 | ||
| + | 3 5 10 | ||
| + | 0 2 1 | ||
| + | 2 4 1 | ||
| + | 5 4 1 | ||
| + | 2 | ||
| + | 4 5 | ||
| + | </pre> | ||
| + | |||
| + | Output: | ||
| + | <pre>31 | ||
| + | </pre> | ||
| + | |||
| + | '''ตัวอย่าง 3''' | ||
| + | |||
| + | Input: | ||
| + | <pre>5 8 | ||
| + | 0 1 1 | ||
| + | 1 2 1 | ||
| + | 1 3 1 | ||
| + | 2 0 2 | ||
| + | 3 0 2 | ||
| + | 3 2 2 | ||
| + | 3 4 2 | ||
| + | 0 4 10 | ||
| + | 3 | ||
| + | 1 2 4 | ||
| + | </pre> | ||
| + | |||
| + | Output: | ||
| + | <pre>5 | ||
</pre> | </pre> | ||
รุ่นแก้ไขเมื่อ 05:10, 31 พฤษภาคม 2557
ให้กราฟ G แบบมีทิศทาง ที่มีโหนด N โหนด (N <= 1 000) มีเส้นเชื่อมที่มีทิศทางและมีน้ำหนัก M เส้น (M <= 50 000) (ระหว่างโหนดคู่หนึ่ง อาจมีเส้นเชื่อมได้มากกว่าหนึ่งเส้น) โหนดในกราฟมีหมายเลข 0, 1, ..., N - 1
ให้เซตของจุดยอด T ที่มีขนาด K (K <= 10) เราต้องการหาต้นไม้ที่มีทิศทาง (arborescence) ที่เป็น subgraph ของ G ที่มีโหนด 0 เป็นโหนดราก และเชื่อมไปยังทุก ๆ โหนดใน T (อาจจะมีโหนดอื่นร่วมด้วยได้) ที่มีน้ำหนักน้อยที่สุด (นิยามน้ำหนักของต้นไม้เท่ากับผลรวมของนำหนักของเส้นเชื่อมในต้นไม้ทั้งหมด)
ข้อมูลนำเข้า
- บรรทัดแรกระบุจำนวนเต็ม N และ M แทนจำนวนโหนดและจำนวนเส้นเชื่อม
- อีก M บรรทัดระบุเส้นเชื่อม โดยระบุจำนวนเต็ม A B และ C เพื่อระบุว่ามีเส้นเชื่อมจากโหนด A ไปยังโหนด B ที่มีน้ำหนัก C
- บรรทัดถัดไประบุจำนวนเต็ม K แทนขนาดของ T
- บรรทัดถัดไประบุจำนวนเต็ม K จำนวน แทนหมายเลขโหนดในเซต T
'ข้อมูลส่งออก
- มีหนึ่งบรรทัดเป็นน้ำหนักของต้นไม้ที่มีทิศทางที่น้อยที่สุด ที่มีโหนด 0 เป็นโหนดรากและมีทุกโหนดใน T
ตัวอย่าง 1
Input:
6 6 0 1 10 1 3 10 3 5 10 0 2 1 2 4 1 4 5 1 2 4 5
Output:
3
ตัวอย่าง 2
Input:
6 6 0 1 10 1 3 10 3 5 10 0 2 1 2 4 1 5 4 1 2 4 5
Output:
31
ตัวอย่าง 3
Input:
5 8 0 1 1 1 2 1 1 3 1 2 0 2 3 0 2 3 2 2 3 4 2 0 4 10 3 1 2 4
Output:
5
