There is a programing contest named SnakeUp, 2n people want to compete for it. In order to attend this contest, people need to form teams of exactly two people. You are given the strength of each possible combination of two people. All the values of the strengths aredistinct.
Every contestant hopes that he can find a teammate so that their team’s strength is as high as possible. That is, a contestant will form a team with highest strength possible by choosing a teammate from ones who are willing to be a teammate with him/her. More formally, two people A and B may form a team if each of them is the best possible teammate (among the contestants that remain unpaired) for the other one.
Can you determine who will be each person’s teammate?
There are 2n lines in the input.
The first line contains an integer n (1 ≤ n ≤ 400) — the number of teams to be formed.
The i-th line (i > 1) contains i - 1 numbers ai1, ai2, ... , ai(i - 1). Here aij (1 ≤ aij ≤ 106, all aij are distinct) denotes the strength of a team consisting of person i and person j (people are numbered starting from 1.)
Output a line containing 2n numbers. The i-th number should represent the number of teammate of i-th person.
2 6 1 2 3 4 5
2 1 4 3
3 487060 3831 161856 845957 794650 976977 83847 50566 691206 498447 698377 156232 59015 382455 626960
6 5 4 3 2 1
In the first sample, contestant 1 and 2 will be teammates and so do contestant 3 and 4, so the teammate of contestant 1, 2, 3, 4 will be2, 1, 4, 3 respectively.
题目大意：有2n个人，要每两人一组把他们分成n队去参加比赛，给出每种可能的组合的实力，保证不同组合的实力不会相等。组队的策略是从还没有组队的人里选出两人，如果对于他们来说都选择了最好的队友（即找不到一个人来替换他们中的一个以得到更高的实力），那么他们组成一队。求每个人分别和谁组队。
因为实力值不会重复，所以在没有组队的人里有且只有一支符合给出策略的队伍。
把所有可能的组合按实力从小到大排序，枚举所有组合，如果两人都还未组队，他们就组成一队。
代码在此。
评论 (0)
