自动搬运

查看原文

来自洛谷，原作者为

	determination 敬不完美的明天。

搬运于2025-08-24 23:12:14，当前版本为作者最后更新于2025-06-26 14:27:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

咋全都是拓扑啊，给出一种更加无脑（数据结构学傻了导致的）做法。

看到做匹配，直接想到网络流。但是我只会二分图匹配。所以我们要先证明，如果给可以消除的点连边，最后连出来的都是二分图。

这个是显然的，首先扔掉自环，这个最后考虑就好了。

然后考虑如果出现一个环 $a,b,c$，那么就要求 $a+b,a+c,b+c$ 只有两种不同的数。显然这是不可能的。至于环更长的情况也不可能。

然后我们就可以直接上网络流跑二分图匹配了！

荣获最劣解第一页。

网络流这玩意很玄学，虽然理论复杂度很高，但是实际情况下你可以相信他的常数。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
mt19937 rnd(time(0));
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10,M=2e5+10;
int n,A,B;
int a[N],b[N];
map<int,int>mp;
vector<int>e[N];
int col[N];
void dfs(int x)
{
	for ( auto v:e[x] )
		if(!col[v]){col[v]=3-col[x];dfs(v);}
		else assert(col[v]!=col[x]);
}
namespace FLOW{
	vector<pair<int,int>>e[N];
	vector<int>id[N];
	void add(int u,int v,int w)
	{
//		cerr << "add: " << u << " " <<v << " " <<w  << endl;
		id[u].push_back(e[v].size());
		id[v].push_back(e[u].size());
		e[u].push_back({v,w});
		e[v].push_back({u,0});
	}
	int dep[N],gap[N];
	const int S=0,T=N-5;
	queue<int>q;
	void bfs()
	{
		memset(dep,0x3f,sizeof(dep));
		dep[T]=0,q.push(T);
		while(!q.empty())
		{
			int x=q.front();q.pop();
			gap[dep[x]]++;
			for ( auto v:e[x] )if(dep[v.first]>dep[x]+1)dep[v.first]=dep[x]+1,q.push(v.first);
		}
	}
	int dfs(int x,int flow)
	{
		if(x==T)return flow;
		int used=0;
		for ( int i = 0 ; i < e[x].size() ; i++ )
		{
			int v=e[x][i].first,w=e[x][i].second;
			if(!w||dep[v]!=dep[x]-1)continue;
			int f=dfs(v,min(w,flow-used));
			used+=f;
			e[x][i].second-=f;
			e[v][id[x][i]].second+=f;
			if(used==flow)return used;
		}
		gap[dep[x]]--;
		if(!gap[dep[x]])dep[S]=T+5;
		dep[x]++;
		gap[dep[x]]++;
		return used;
	}
	void solve()
	{
		bfs();
		int maxflow=0;
		while(dep[S]<T+5)
		{
			maxflow+=dfs(S,inf);
//			cerr << maxflow << endl;
		}
		for ( auto i:e[S] )
		{
			int v=i.first,w=i.second;
			if(b[v]+b[v]==A||b[v]+b[v]==B)maxflow+=w/2;
		}
		for ( auto i:e[T] )
		{
			int v=i.first,w=i.second;
			if(b[v]+b[v]==A||b[v]+b[v]==B)maxflow+=(a[v]-w)/2;
		}
		cout << maxflow << endl;
	}
	//todo
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin >>n >> A>>B;
	for ( int i = 1 ; i <= n ; i++ )
	{
		cin >> a[i] >> b[i];
		mp[b[i]]=i;
	}
	for ( int i = 1 ; i <= n ; i++ )
	{
		if(mp[A-b[i]]&&mp[A-b[i]]!=i)
//			cerr << "add " << i << " " << mp[A-b[i]] << endl,
			e[i].push_back(mp[A-b[i]]);
		if(mp[B-b[i]]&&mp[B-b[i]]!=i)
//			cerr << "add " << i << " " << mp[B-b[i]] << endl,
			e[i].push_back(mp[B-b[i]]);
	}
	for ( int i = 1 ; i <= n ; i++ )if(!col[i]){col[i]=2;dfs(i);}
	for ( int i = 1 ; i <= n ; i++ )
	{
		if(col[i]==1)FLOW::add(FLOW::S,i,a[i]);
		else FLOW::add(i,FLOW::T,a[i]);
		if(col[i]==1)for ( auto v:e[i] )FLOW::add(i,v,inf);
	}
	FLOW::solve();
	return 0;
}