显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+5;
int n,a,b,ans,tot,v[N],hd[N],nxt[N],_n[N],_d[N],ii[N],vis[N];
map<int,int> f;
void add(int x,int y){
v[++tot]=y;
nxt[tot]=hd[x];
hd[x]=tot;
}
void solve(){
queue<int>q;
for(int i=1;i<=n;i++){
if(ii[i]==1) q.push(i);
}
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=hd[x],y;i;i=nxt[i]){
y=v[i];
if(!vis[y]){
if(y==x){
ans+=(_n[x]>>1);
_n[x]&=1;
}else{
int hs=min(_n[x],_n[y]);
ans+=hs;
_n[x]-=hs;
_n[y]-=hs;
}
ii[y]--;
if(ii[y]==1) q.push(y);
}
}
vis[x]=1;
}
}
signed main(){
//freopen("Compatible.in","r",stdin);
//freopen("Compatible.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a>>b;
for(int i=1;i<=n;i++){
cin>>_n[i]>>_d[i];
f[_d[i]]=i;
}
for(int i=1;i<=n;i++){
if(f.find(a-_d[i])!=f.end()){
add(i,f[a-_d[i]]);
ii[f[a-_d[i]]]++;
}
if(a!=b&&f.find(b-_d[i])!=f.end()){
add(i,f[b-_d[i]]);
ii[f[b-_d[i]]]++;
}
}
solve();
cout<<ans<<"\n";
return 0;
}
/*const int N=1e7,inf=0x3f3f3f3f;
int n,a,b,s,t,tot=1,hd[N];
struct node{
int v,w,nxt;
}e[N];
void add(int x,int y,int z){
e[++tot].v=y;
e[tot].w=z;
e[tot].nxt=hd[x];
hd[x]=tot;
e[++tot].v=x;
e[tot].w=z;
e[tot].nxt=hd[y];
hd[y]=tot;
}
int cur[N],d[N];
bool bfs(){
memset(d,0,sizeof(d));
queue<int> q;
q.push(s);
d[s]=1;
while(!q.empty()){
int f=q.front();
q.pop();
for(int i=hd[f];i;i=e[i].nxt){
int v=e[i].v;
if(d[v]==0&&e[i].w>0){
d[v]=d[f]+1;
q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int mf){
if(u==t) return mf;
int sum=0;
for(int i=cur[u];i&&mf;i=e[i].nxt){
cur[u]=i;
int v=e[i].v;
if(d[v]==d[u]+1&&e[i].w){
int f=dfs(v,min(mf,e[i].w));
if(f==0) d[v]=0;
e[i].w-=f;
e[i^1].w+=f;
sum+=f;
mf-=f;
if(mf==0) break;
}
}
if(sum==0) d[u]=0;
return sum;
}
int Dinic(){
int flow=0;
while(bfs()){
memcpy(cur,hd,sizeof(hd));
flow+=dfs(s,inf);
}
return flow;
}
int _n[N],_f[N],maxn;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a>>b;
a+=4,b+=4,s=0,t=1;
for(int i=1;i<=n;i++){
cin>>_n[i]>>_f[i];
_f[i]+=2;
maxn=max(maxn,_f[i]);
}
for(int i=1;i<=n;i++){
int _a=a-_f[i],_b=b-_f[i];
if(_a!=_f[i]) add(_f[i],_a+maxn,inf);
if(_b!=_f[i]) add(_f[i],_b+maxn,inf);
}
for(int i=1;i<=n;i++){
add(s,_f[i],_n[i]);
add(_f[i]+maxn,t,_n[i]);
}
int ans=Dinic()/2;
for(int i=hd[0];i;i=e[i].nxt){
int v=e[i].v,w=e[i].w;
if(a-v==v||b-v==v) ans+=(w/2);
}
cout<<ans<<"\n";
return 0;
}*/
李奇文