B. Finding Team Member
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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?
Input
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
Output a line containing 2n numbers. The i-th
number should represent the number of teammate of i-th person.
Sample test(s)
input
2 6 1 2 3 4 5
output
2 1 4 3
input
3 487060 3831 161856 845957 794650 976977 83847 50566 691206 498447 698377 156232 59015 382455 626960
output
6 5 4 3 2 1
Note
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.
题目大意：
就是给你 2*n 个人，给一个下三角矩阵，要求选2n组人，每组两人，arr[i][j]表示i和j在一起的分数，每次选的结果都是当前可能的最大值，
(一个人只能在一组里)
解题思路：
暴力做就行只是要考虑一下数组的大小，我一般为了方便起见都把数组开的比较大，
1000*1000的就行，其实805*805应该也行。
上代码：
/**
2015 - 09 - 22 晚上
Author: ITAK
Motto:
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1000;
const int mod = 1e9+7;
const double eps = 1e-7;
struct node
{
int x, y, node;
}arr[maxn*maxn];
bool cmp(node a, node b)
{
return a.node > b.node;
}
int flag[maxn], ret[maxn];
int main()
{
memset(flag, 0, sizeof(flag));
int n, k=0;
cin>>n;
for(int i=2; i<=2*n; i++)
{
for(int j=1; j<i; j++)
{
cin>>arr[k].node;
arr[k].x = i;
arr[k].y = j;
k++;
}
}
sort(arr, arr+k, cmp);
for(int i=0; i<k; i++)
{
if(!flag[arr[i].x] && !flag[arr[i].y])
{
ret[arr[i].x] = arr[i].y;
ret[arr[i].y] = arr[i].x;
flag[arr[i].x] = 1;
flag[arr[i].y] = 1;
}
}
for(int i=1; i<2*n; i++)
cout<<ret[i]<<" ";
cout<<ret[2*n]<<endl;
return 0;
}