#1817. 彩虹航线
彩虹航线
彩虹航线
题目描述
标题: 彩虹航线 - Problem - QOJ.ac
#7977. 彩虹航线
The problem was used in the following contests:
A 国和 B 国各有 n 个机场,两国间有 m 条航线。
每条航线都有 k 种不同的备选颜色。保证所有机场起飞的航线数量不超过 k。
第 i 条航线往返于 A 国的机场 ui 和 B 国的机场 vi,其第 j 种备选颜色为 ci,j。
给每条航线选择一种备选颜色,使得同一个机场起飞的航线的颜色互不相同。
输入格式
第一行三个整数 n,m,k。
接下来 m 行,第 i 行 k+2 个整数 ui,vi,ci,1,ci,2,⋯,ci,k。
输出格式
一行 m 个整数 a1,a2,⋯,am,表示第 i 条航线的颜色为 ai。
如果有多种方案,给出任意一种即可。保证存在至少一种合法方案。
样例输入
2 4 2
1 1 1 2
1 2 2 3
2 1 1 3
2 2 2 3
样例输出
2 3 3 2
数据范围
保证 1≤n,k≤150,1≤m≤n2,1≤ci,j≤min(106,mk),1≤ui,vi≤n。
保证不存在两条航线重合的情况,即不存在 i≠j 满足 (ui,vi)=(uj,vj)。
子任务编号特殊性质分值1k=112k=2n23k=2114m=n2,k=n+1375m=n2216无28
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 4 2
1 1 1 2
1 2 2 3
2 1 1 3
2 2 2 3
2 3 3 2