codeforces 1475 C Ball in Berland

原题链接

题意

有n个男的m个女的,还有k对关系(a,b)表示第a个男的可以和第b个女的跳舞.现在要求你从k对关系里选出两对不干扰的男女,不干扰即是指同一个人不能出现在两对关系里,问选出两对关系的方案数有多少个.

思路

1. 我们可以选出一对，来枚举另一对，然后求出总和，因为枚举也会计算另一对，所以结果/2
2. 如何枚举另一对，对于另一对，不能和a,b相同，即不能与a,b有关，可以利用补集来求，（a,b）在k对关系中，统计与a出现的次数cnta，b出现的次数cntb，那么cnta+cntb-1就是除去要枚举的这对，k对中与a,b有关系的对数，然后k-(cnta+cntb-1)就是与(a,b)没有关系的对数

代码

#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;
}