Codeforces 1475C - Ball in Berland

題目大意

這道題目給我們 a 個男孩和 b 個女孩，有 k 對組合，讓我們找出來兩對，其中并沒有一個人出現過兩次的組合有多少種。

題目分析

容斥原理，我們記錄下每個男孩在配對中出現了 cnt1[i] 次，每個女孩在配對種出現了 cnt2[i] 次，那麼我們周遊這 k 對，對于每一對來說，另一對可以選擇的方案數為：

k - cnt1[i] - cnt2[i] + 1

，減去目前男孩在的組數和目前女孩在的組數，這個男孩和女孩減去了兩次，是以加1.

#include <iostream>

using namespace std;

const int N = 2e5+10;

pair<int,int> edges[N];

void solve()
{
	int cnt1[N] = {0}, cnt2[N] = {0};
	int a , b , k;
	cin >> a >> b >> k;
	for(int i = 1; i <= k; i++) cin >> edges[i].first , cnt1[edges[i].first]++;
	for(int i = 1; i <= k; i++) cin >> edges[i].second , cnt2[edges[i].second]++;
	long long res = 0;
	for(int i = 1; i <= k; i++) 
	{
		int x = edges[i].first , y = edges[i].second;
		res += k - cnt1[x] - cnt2[y] + 1;
	}
	cout << res / 2 << endl;
}

int main()
{
	int t; cin >> t;
	while(t--) solve();
	return 0; 
}