题目描述
古人云：秀恩爱，分得快。
互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？
输入样例1
10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2
输出样例1
-3 2
2 -5
2 -6
输入样例2
4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2
-3 2
输出样例2
-3 2
分析
由于是不超过1000的最大数据，所以建立一个double 类型的g[N][N]存储每两个人之间的亲密度。 之后要注意可能存在-0（表示女生）但是直接用int输入的话是不会进行特殊区分的，所以需要定义一个read()函数用来输入每一个人的数字。把经过输入的数字的性别存放到sex[N]的数组中。 用一个Print()函数专门用于输出结果，可以节省代码量。
C++ 代码
#include<bits/stdc++.h>
using namespace std
;
const int N
= 1e3+10;
double g
[N
][N
];
int sex
[N
];
int read()
{
bool flag
= 0;
char a
= getchar();
int ans
= 0;
while ((a
<'0' || a
>'9') && a
!= '-')
{
a
= getchar();
}
while (a
== '-' || a
>= '0'&&a
<= '9')
{
if (a
== '-')flag
= 1;
else
{
ans
= ans
* 10 + a
- '0';
}
a
= getchar();
}
sex
[ans
] = flag
;
return ans
;
}
void Print(int a
, int b
)
{
if (sex
[a
])cout
<< '-';
cout
<< a
<< ' ';
if (sex
[b
])cout
<< '-';
cout
<< b
<< endl
;
}
int main()
{
int n
,m
; cin
>>n
>>m
;
int k
;
while(m
--)
{
cin
>>k
;
vector
<int> gender
[2];
for(int i
=0;i
<k
;i
++)
{
int num
=read();
gender
[sex
[num
]].push_back(num
);
}
for (int i
= 0; i
<gender
[0].size(); i
++)
{
for (int j
= 0; j
<gender
[1].size(); j
++)
{
g
[gender
[0][i
]][gender
[1][j
]] += 1.0/k
;
g
[gender
[1][j
]][gender
[0][i
]] += 1.0/k
;
}
}
}
int cp1
=read(),cp2
=read();
double max1
= 0, max2
= 0;
for (int i
= 0; i
<n
; i
++)
{
max1
=max(max1
, g
[cp1
][i
]);
max2
=max(max2
, g
[cp2
][i
]);
}
if (max1
== g
[cp1
][cp2
] && max2
== g
[cp1
][cp2
])
{
Print(cp1
, cp2
);
}
else
{
for(int i
= 0; i
<n
; i
++)
{
if(g
[i
][cp1
] == max1
) Print(cp1
, i
);
}
for(int i
= 0; i
<n
; i
++)
{
if(g
[i
][cp2
] == max2
) Print(cp2
, i
);
}
}
return 0;
}
