思路
- 超绝恶心题
- 最大的坑点,正零和负零。因为cin读入负零和正零都是零,所以直接用int读入是不可以的
- 封装整合的应用,因为存在大量的相似操作,所以我们写成函数,减少重复的代码,使得思路更加清晰
#include <bits/stdc++.h>
//#define int long long
const int N = 1e3 + 10;
using namespace std;
double g[N][N];
vector<int> man;
vector<int> woman;
int st[N];
void get_max(int x, int sex, vector<int>& res, double& max_)
{
vector<int> p;
// 男生
if(sex == 1) p = woman;
else p = man;
// 遍历x和异性的最大亲密度
for(int i = 0; i < p.size(); i ++)
{
int y = p[i];
//cout << wo << endl;
if(g[x][y] > max_)
{
res.clear();
res.push_back(y);
max_ = g[x][y];
}
else if(g[x][y] == max_)
{
res.push_back(y);
}
}
}
void print(vector<int>& vec, int x, int sex)
{
sort(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i ++)
{
if(sex == 0) cout << '-' << x << ' '<< vec[i] << endl;
else cout << x << ' ' << '-' << vec[i] << endl;
}
}
signed main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i ++)
{
int k; cin >> k;
vector<int> male, fmale;
for(int j = 0; j < k; j ++)
{
int x;
string name;
cin >> name;
x = stoi(name);
if(name[0] == '-')
{
x = -x;
fmale.push_back(x);
if(st[x] == 0) woman.push_back(x);
st[x] = 1;
}
else
{
male.push_back(x);
if(st[x] == 0) man.push_back(x);
st[x] = 1;
}
}
for(int i = 0; i < male.size(); i ++)
{
for(int j = 0; j < fmale.size(); j ++)
{
int a = male[i], b = fmale[j];
double t = 1.0 / k;
g[a][b] += t;
g[b][a] += t;
}
}
}
int a, b;
string aa, bb;
cin >> aa >> bb;
int sexa = 1, sexb = 1;// 女的为零
a = abs(stoi(aa));
b = abs(stoi(bb));
if(aa[0] == '-') sexa = 0;
if(bb[0] == '-') sexb = 0;
double max_a = 0, max_b = 0;
int is_b = 0, is_a = 0;
vector<int> resa, resb;
// 找a的最大亲密度
get_max(a, sexa, resa, max_a);
for(int i = 0; i < resa.size(); i ++)
{
//cout <<"hehe: " <<resa[i] << endl;
if(resa[i] == abs(b))
{
is_b = 1;
break;
}
}
// 遍历b的最大亲密度
get_max(b, sexb, resb, max_b);
for(int i = 0; i < resb.size(); i ++)
{
if(resb[i] == abs(a))
{
is_a = 1;
break;
}
}
if(is_a && is_b)
{
if(sexa == 0) cout << '-' << a << ' ';
else cout << a;
if(sexb == 0) cout << '-' << b << ' ';
else cout << b;
}
else
{
print(resa, a, sexa);
print(resb, b, sexb);
}
return 0;
}