原题链接
题意
有n个男的m个女的,还有k对关系(a,b)表示第a个男的可以和第b个女的跳舞.现在要求你从k对关系里选出两对不干扰的男女,不干扰即是指同一个人不能出现在两对关系里,问选出两对关系的方案数有多少个.
思路
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int t, m, n, k;
int a[N], b[N], cnta[N], cntb[N];
int main() {
cin >> t;
while (t--) {
memset(cnta, 0, sizeof cnta);
memset(cntb, 0, sizeof cntb);
cin >> m >> n >> k;
for (int i = 1; i <= k; i++) {
scanf("%lld", &a[i]);
++cnta[a[i]];
}
for (int i = 1; i <= k; i++) {
scanf("%lld", &b[i]);
++cntb[b[i]];
}
ll sum = 0;
for (int i = 1; i <= k; i++) {
sum += (k - (cnta[a[i]] + cntb[b[i]] - 1));
}
cout << sum / 2 << endl;
}
return 0;
}