cf 1475C - Ball in Berland

1475C - Ball in Berland

// 思維題
每一對配對關系可以看作兩個人之間連接配接了一條邊。
設a[i] 為 編号為i的男孩所有邊的數量，
  b[i] 為 編号為i的女孩所有邊的數量。
枚舉每一對配對關系，
假設選擇目前第x對配對關系，男孩編号為i,女孩編号為j.
第二對 組合可以選擇的方案有：k - a[i] - b[j] + 1;
因為選擇了第i個男孩和第j個女孩，是以第二對組合中不能再出現這兩個人，是以與他們相關的邊全部廢棄。
(a,b) 這條邊被廢棄兩次，是以要加1.

最終答案要除以2，因為每一個方案被計算了兩次。
           

#include<iostream>
#include<cstring>
using namespace std;

typedef long long ll;

const int N = 200010;
int a[N]; // 表示第i個男孩擁有的邊數
int b[N]; // 表示第i個女孩擁有的邊數
int aa[N],bb[N];  // 記錄第i對配對關系

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n,m,k;
        cin >> n >> m >> k;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        for(int i = 1; i <= k; i ++)
        {
            int x;
            cin >> x;
            a[x] ++;
            aa[i] = x;
        }
        for(int i = 1; i <= k; i ++)
        {
            int x;
            cin >> x;
            b[x] ++;
            bb[i] = x;
        }
        
        ll ans = 0;
        for(int i = 1; i <= k; i ++)
        {
            ans = ans + k - a[aa[i]] - b[bb[i]] + 1;
        }
        
        cout << ans / 2 << endl;
    }
}