#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define fi first
#define se second
vector<ll> v;
map<ll,ll> id;
bool cmp(pii x,pii y){return x.se<y.se;}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	ll n,A,B;cin>>n>>A>>B;
	for(ll i=1,d,x;i<=n;i++){
		cin>>x>>d;
		id[d]=x;
		v.push_back(d);
	}
	sort(v.begin(),v.end());
    ll ans=0;
	for(auto x:v){
		ll pa=A-x,pb=B-x;
		if(id[pb]>0&&pb>=0){//应该优先匹配pb 
			if(pb==x) ans+=id[pb]/2,id[pb]%=2;
			else{
				int mi=min(id[x],id[pb]);
				ans+=mi;
				id[x]-=mi,id[pb]-=mi;
			}
		} 
		if(id[pa]>0&&pa>=0){
			if(pa==x) ans+=id[pa]/2,id[pa]%=2;
			else {
				int mi=min(id[x],id[pa]);
				ans+=mi;
				id[x]-=mi,id[pa]-=mi; 
			}
		}
	}
	cout<<ans;
	return 0;
}

题意

有 $N$ 个不同的号码，对于每一个唯一号码 $d_i$，有 $n_i$ 头奶牛共享它。

当两头不同的奶牛的号码和为 $A$ 或 $B$ 时可以通话，且每头奶牛只能参加一个通话。

求最多有多少对通话。

思路

考虑建图连边。

那么每头奶牛出度最多为 $2$，可以连向号码为 $A-d_i$ 或 $B-d_i$ 的奶牛。当 $A=B$ 是时连 一条。

我们可以发现这个图除自环外无其他环，证明如下。

我们设三个点构成了环分别是 $a$，$b$，$c$。设 $a+b=A$，因为号码是唯一的，所以三个点互不相同，所以 $b+c=B$，但 $a+c$ 无论等于多少都会出现相同的情况，所以不成立。

最优方案显然是先让入度为 $0$ 的点先配对，然后依次往上，所以用拓扑排序的思想即可实现。

代码

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int M=2e5+10;
int N,A,B,n[M],d[M],ans,in[M];
map<int,int> mp;
vector<int> e[M];
queue<int> q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	freopen("skiing.in","r",stdin);
	freopen("skiing.out","w",stdout);
	cin>>N>>A>>B;
	for(int i=1;i<=N;i++)cin>>n[i]>>d[i],mp[d[i]]=i;//方便后面查询 
	for(int i=1;i<=N;i++){	//最多连两条边 
		//反正后面都会遍历到mp[A-d[i]]/mp[A-d[i]]，随便谁朝谁连都可以 
		if(d[i]<=A&&mp[A-d[i]])e[i].push_back(mp[A-d[i]]),in[mp[A-d[i]]]++;
		if(A==B)continue;
		if(d[i]<=B&&mp[B-d[i]])e[i].push_back(mp[B-d[i]]),in[mp[B-d[i]]]++;
	}
	//拓扑顺序 
	for(int i=1;i<=N;i++)if(in[i]==1)q.push(i);	//只有一条边的优先抵消 
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(auto i:e[cur]){
			if(i==cur){	//自环 
				ans+=n[i]/2;
				n[i]%=2;
				continue;
			}
			if(n[i]){	//有贡献 
				int res=min(n[i],n[cur]);
				ans+=res;
				n[i]-=res,n[cur]-=res;
				q.push(i);//删掉一条边后也只剩一条了 
			}
		}
	}
	cout<<ans; 
	return 0;
}

谢谢！