题解：P14581 [LNCPC 2025] 海鸥奇遇
匈牙利不是区。
好题，说明了匈牙利算法并非被 dinic 完全偏序，不要再在 QOJ 上 Down 了，写成大模拟是因为做法不对。
这是一个更强悍的做法，比起其他题解，实现难度方面优势极大，且时间复杂度一致，运行速度更快。
与其他题解保持一致，左侧点为食物，右侧点为海鸥，原题目相当于求这个模型的完美匹配，且构造一个海鸥之间不互相依赖的方案。
运行二分图最大匹配。如果有完美匹配，则有解，方案稍后构造。否则都无解。
因为海鸥之间有依赖，所以我们随便找到的这个完美匹配不一定能满足所有要求，因为依赖可能成环。
此时就有两条路线可走：消环，或者使得最开始得到的完美匹配无环。
其余题解使用的是消环的思路，势能分析之后暴力用位移拆环，dinic 时间复杂度
我们走另一条路线：找到一个优秀的初始构造。
想象出现环的时候是什么情况，最基础的（F 代表食物 B 代表鸟）
FBBF出现环的情况是每只鸟和离他最远的食物匹配，这种匹配感觉很繁杂。直觉告诉我们每个食物尽量找离他最近的海鸥。
GPT 声称此时可以最小费用流解决，时间复杂度正确，但这太难了，我们不讨论。
把每份食物的候选海鸥按距离排序，距离进的在前，按此顺序进行匈牙利算法。可以通过增广次数归纳证明：
每轮有序增广结束后，不存在一圈食物，可以循环交换它们匹配的海鸥，让圈内每份食物都得到严格更近的海鸥。
简要的说说：在这一轮搜索时，就存在一条在首次分岔处选择更近海鸥的增广路。有序 DFS 会优先找到它，因此不可能形成这个环。
然后就是说明为什么不存在交换之后分配更近，最终依赖就无环：如果我们有环，其中每个点的匹配是
namespace MYcode{
const int N=5e3+5,TN=N*2,M=N*8;
int vis[TN],frm[M],to[M],D[M],tar[N],tot,In[N];
pii b[N],f[N];
vector<int>e[N],pth[M],g[N];
bool dfs(int x){
for(int id:e[x]){
int v=to[id];
if(vis[v])continue;vis[v]=1;
if(!tar[v]||dfs(frm[tar[v]])){
tar[v]=id;
return 1;
}
}return 0;
}int mp[N][N],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void work(){
int T;in>>T;
for(;T--;){
int n;in>>n;tot=0;
mset(vis,0),mset(frm,0),mset(to,0),mset(tar,0),mset(In,0);
for(int i=1;i<=n;i++)in>>b[i].first>>b[i].second,mp[b[i].first][b[i].second]=i+n;
for(int i=1;i<=n;i++)in>>f[i].first>>f[i].second,mp[f[i].first][f[i].second]=i;
for(int i=1;i<=n;i++){
for(int d=0;d<4;d++){
int x=f[i].first+dx[d],y=f[i].second+dy[d];
vector<int>path;
for(int v=mp[x][y];x>0&&y>0&&x<=5000&&y<=5000;v=mp[x][y]){
if(v==0||v<=n)break;
frm[++tot]=i,to[tot]=v-n,pth[tot]=path,D[tot]=d;
e[i].push_back(tot);
path.push_back(v-n),x+=dx[d],y+=dy[d];
}
}sort(all(e[i]),[](int a,int b){return pth[a].size()<pth[b].size();});
}bool flag=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)vis[j]=0;
if(!dfs(i)){flag=0;break;}
}if(!flag)out<<"No\n";
else{
out<<"Yes\n";
for(int i=1;i<=n;i++)
for(auto j:pth[tar[i]]){
g[i].push_back(j);
In[j]++;
}
queue<int>q;vector<int>ans;
for(int i=1;i<=n;i++)
if(!In[i])q.push(i);
for(;q.size();){
int x=q.front();q.pop();
ans.push_back(x);
for(auto i:g[x])
if((--In[i])==0)q.push(i);
}for(auto i:ans)
out<<i<<" "<<("UDLR"[D[tar[i]]])<<"\n";
}for(int i=1;i<=n;i++)
mp[b[i].first][b[i].second]=mp[f[i].first][f[i].second]=0,e[i].clear(),g[i].clear();
}
}
}::::info[完整代码]
// @author fkxr(luogu uid = 995934)
#define luogu
#ifndef luogu
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#else
#include <bits/stdc++.h>
#endif
//#define int long long
#define all(x) x.begin(),x.end()
#define mset(x,k) memset(x,k,sizeof(x))
#define popct(val) ((int)__builtin_popcountll(val))
#define endl cerr<<"------------------I Love the Olympiad in Informatics------------------\n";
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
using namespace std;
#define times(a,b,m) (c=(ull)a*b-(ull)((long double)a/m*b+0.5L)*m,c<m?c:m+c)
int dx[]={1,-1,0,0},dy[]={0,0,1,-1},dx8[]={1,0,-1,-1,1,1,0,-1},dy8[]={1,1,1,0,0,-1,-1,-1};using pii=pair<int,int>;using ull=unsigned long long;
namespace fastIO {
constexpr bool IsWhiteSpace(char x){return x=='\r'||x=='\n'||x==' ';}
template<typename T> inline void read(T&a){a=0;char ch=gc();bool ok=0;for(;ch<'0'||ch>'9';)ok^=(ch=='-'),ch=gc();for(;ch>='0'&&ch<='9';)a=(a<<1)+(a<<3)+(ch^48),ch=gc();if(ok)a=-a;}inline void read(char&ch){ch=gc();for(;IsWhiteSpace(ch);)ch=gc();}inline void read(string&s){s="";char ch=gc();for(;IsWhiteSpace(ch);)ch=gc();for(;!(IsWhiteSpace(ch)||ch==EOF);)s.push_back(ch),ch=gc();}
template<typename T> inline void write(T a){if(a==0){pc('0');return;}char ch[20];int till=0;if(a<0){pc('-');for(;a;)ch[till++]=-(a%10),a/=10;}else for(;a;)ch[till++]=a%10,a/=10;for(;till;)pc(ch[--till]^48);}inline void write(const char ch){pc(ch);}inline void write(const string s){for(int i=0;i<s.size();i++)pc(s[i]);}inline void write(const char*a){while(*a)pc(*a++);}
struct FIOstream{template<typename T> inline FIOstream operator>>(T&x){read(x);return{};}template<typename T> inline FIOstream operator<<(const T&x){write(x);return{};}}FIO;
template<typename T>void read(T l,T r){for(;l!=r;FIO>>*(l++));}template<typename T>void print(T l,T r,string end="\n"){for(;l!=r;FIO<<*(l++),pc(' '));FIO<<end;}template<typename T>void println(T l,T r,string end=""){for(;l!=r;FIO<<*(l++),pc('\n'));FIO<<end;}
inline void YN(bool ans){FIO<<(ans?"YES\n":"NO\n");}inline void yn(bool ans){FIO<<(ans?"yes\n":"no\n");}inline void Yn(bool ans){FIO<<(ans?"Yes\n":"No\n");}
}using namespace fastIO;auto&in=FIO;auto&out=FIO;auto&eout=cerr;void Freopen(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}template<typename T,typename T1,typename T2>inline bool bt(T l,T2 x,T1 r){return l<=x&&x<=r;}
namespace Maths{const int Suk[]={2,325,9375,28178,450775,9780504,1795265022};inline bool IP1(const int a){if(a<=5)return(a==2||a==3||a==5);if(a%2==0)return 0;for(int i=3;i*i<=a;i+=2)if(a%i==0)return 0;return 1;}inline int power(int a,int b,const int mod=-1){ull c;int ans=1;if(mod==-1){for(;b;b>>=1){if(b&1)ans*=a;a*=a;}return ans;}for(;b;b>>=1){if(b&1)ans=times(ans,a,mod);a=times(a,a,mod);}return ans; }inline bool chk(const int n,int a,int b,int x){if(x>=n)return 1;ull c;int v=power(x,a,n);if(v==1)return 1;int j=1;for(;j<=b&&v!=n-1;++j)v=times(v,v,n);return(j<=b);}inline bool IP(int n){if(n<3||n%2==0)return n==2;if(n<=1e6){return IP1(n);}else{int a=n-1,b=0;for(;a%2==0;a>>=1,b++);for(int k:Suk)if(!chk(n,a,b,k))return 0;return 1;}}template<typename T> inline T gcd(T x,T y){if(!min(x=(x>0?x:-x),y=(y>0?y:-y)))return max(x,y);int i=__builtin_ctz(x),j=__builtin_ctz(y);x>>=i,y>>=j;if(i>j)i=j;for(;x;){if(x<y)swap(x,y);x-=y;x>>=__builtin_ctz(x);}return y<<i;}}using Maths::power;using Maths::IP;using Maths::gcd;
struct bit{vector<int>c0,c1;int n;inline void init(int sz){n=sz;c0.assign(n+2,0);c1.assign(n+2,0);}inline void Add(vector<int>&c,int p,int v){for(;p<=n;p+=p&-p)c[p]+=v;}inline int Sum(const vector<int>&c,int p){int t=0;for(;p;p-=p&-p)t+=c[p];return t;}inline int sum(int l,int r){assert(n!=0);return Sum(c0,r)*r-Sum(c1,r)-Sum(c0,l-1)*(l-1)+Sum(c1,l-1);}inline void add(int l,int r,int v){assert(n!=0);Add(c0,l,v);Add(c0,r+1,-v);Add(c1,l,(l-1)*v);Add(c1,r+1,-r*v);}};
template<typename T>struct st{vector<int>lg;vector<vector<T>>f;inline void init(const vector<T>&c){int len=c.size()-1;lg.resize(len+2);for(int i=2;i<=len;i++)lg[i]=lg[i>>1]+1;f.clear();f.push_back(vector<T>(len+2));for(int i=1;i<=len;i++)f[0][i]=c[i];for(int j=1;(1<<j)<=len;j++){f.push_back(vector<T>(len+2));for(int i=1;i+(1<<j)-1<=len;i++){f[j][i]=max(f[j-1][i],f[j-1][i+(1<<(j-1))]);}}}inline T query(int l,int r){int j=lg[r-l+1];return max(f[j][l],f[j][r-(1<<j)+1]);}};
struct dsu{vector<int>fa;dsu(int n):fa(n){iota(all(fa),0);}inline int find(int x){return fa[x]==x?x:fa[x]=fa[fa[x]]=fa[fa[fa[x]]]=find(fa[fa[fa[x]]]);}inline void unite(int x,int y){fa[find(x)]=find(y);}};
struct range{struct Iterator{int cur,stop,step;int operator*()const{return cur;}Iterator&operator++(){cur+=step;return *this;}Iterator operator++(signed){Iterator tmp=*this;cur+=step;return tmp;}bool operator!=(const Iterator&)const{if(step>0)return cur<stop;return cur>stop;}};int start,stop,step;range(int stop_):start(0),stop(stop_),step(1){}range(int start_,int stop_,int step_=1):start(start_),stop(stop_),step(step_){}Iterator begin()const{return Iterator{start,stop,step};}Iterator end()const{return Iterator{0,stop,step};}};
// #define mid (l+r>>1)
// #define ls (id<<1)
// #define rs (id<<1|1)
// #define LS ls,l,mid
// #define RS rs,mid+1,r
namespace MYcode{
const int N=5e3+5,TN=N*2,M=N*8;
int vis[TN],frm[M],to[M],D[M],tar[N],tot,In[N];
pii b[N],f[N];
vector<int>e[N],pth[M],g[N];
bool dfs(int x){
for(int id:e[x]){
int v=to[id];
if(vis[v])continue;vis[v]=1;
if(!tar[v]||dfs(frm[tar[v]])){
tar[v]=id;
return 1;
}
}return 0;
}int mp[N][N],dx[]={1,-1,0,0},dy[]={0,0,1,-1};
void work(){
int T;in>>T;
for(;T--;){
int n;in>>n;tot=0;
mset(vis,0),mset(frm,0),mset(to,0),mset(tar,0),mset(In,0);
for(int i=1;i<=n;i++)in>>b[i].first>>b[i].second,mp[b[i].first][b[i].second]=i+n;
for(int i=1;i<=n;i++)in>>f[i].first>>f[i].second,mp[f[i].first][f[i].second]=i;
for(int i=1;i<=n;i++){
for(int d=0;d<4;d++){
int x=f[i].first+dx[d],y=f[i].second+dy[d];
vector<int>path;
for(int v=mp[x][y];x>0&&y>0&&x<=5000&&y<=5000;v=mp[x][y]){
if(v==0||v<=n)break;
frm[++tot]=i,to[tot]=v-n,pth[tot]=path,D[tot]=d;
e[i].push_back(tot);
path.push_back(v-n),x+=dx[d],y+=dy[d];
}
}sort(all(e[i]),[](int a,int b){return pth[a].size()<pth[b].size();});
}bool flag=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)vis[j]=0;
if(!dfs(i)){flag=0;break;}
}if(!flag)out<<"No\n";
else{
out<<"Yes\n";
for(int i=1;i<=n;i++)
for(auto j:pth[tar[i]]){
g[i].push_back(j);
In[j]++;
}
queue<int>q;vector<int>ans;
for(int i=1;i<=n;i++)
if(!In[i])q.push(i);
for(;q.size();){
int x=q.front();q.pop();
ans.push_back(x);
for(auto i:g[x])
if((--In[i])==0)q.push(i);
}for(auto i:ans)
out<<i<<" "<<("UDLR"[D[tar[i]]])<<"\n";
}for(int i=1;i<=n;i++)
mp[b[i].first][b[i].second]=mp[f[i].first][f[i].second]=0,e[i].clear(),g[i].clear();
}
}
}
signed main(){
//Freopen("build");
int T=1;//cin>>T;
for(int i=1;i<=T;i++){
//cout<<"Case #"<<i<<": ";
MYcode::work();
}
return 0;
}::::