题目大意
一条直线上有 \(n\) 个房子和两个人，房子的坐标 \(d_1,d_2,d_3\dots d_n\)，以及两个人坐标为 \(p_1,p_2\)。
现在会告诉你两个集合 \(S_1=\{|p_1-d_i| ,1 \leq i \leq n\}\) 以及 \(S_2=\{|p_2-d_i|,1 \leq i \leq n\}\)。这个写法可能不是很规范，但为了美观就写成这样了。
现在需要你确定构造一组方案确定 \(p_1,p_2\) 以及 \(d_1,d_2,d_3\dots d_n\) 的值或者宣告无解。
数据范围为 \(n \leq 1000\)。
思路
思路还是比较直接的，考虑找到 \(S_1\) 中的一个元素 \(x\)，在 \(S_2\) 中枚举哪一个元素与之匹配，不难发现这样 \(p_1,p_2\) 的坐标情况数量只有 \(2\) 种。
考虑对于这 \(2\) 种情况分开考虑，考虑剩下的元素怎么配对，假定 \((p_1,p_2)=(a,b)\)。
如果一个元素 \(x \in S_1\) 可以和 \(y \in S_2\) 配对，即算出来的 \(p_1,p_2\) 符合 \(a,b\)，那么向他们之间连一条边。
然后跑网络流，看是否存在符合条件的解。
时间复杂度 \(O(n^2\sqrt n)\)。
代码写的很难看。
#include<bits/stdc++.h>
#define int long long
#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define NO puts("NO")
#define YES puts("YES")
using namespace std;
namespace IO{
inline int read(){
RI X=0, W=0;register char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(int x){write(x), putchar(32);}
inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 4e5+5;
const int mod1 = 998244353;
const int mod2 = 1e9+7;
const int inf = 1e12;
int head[5004], ne[MAXN<<1], to[MAXN<<1], weight[MAXN<<1], cnt=1;
int hd, tl, Q[MAXN], cur[MAXN], de[5004], s, t, len, c[MAXN], now, a[MAXN], b[MAXN], n, sol, h[MAXN];
inline void add(int x, int y, int w){
++cnt;to[cnt]=y;ne[cnt]=head[x];head[x]=cnt;weight[cnt]=w;
return ;
}
inline bool spfa(){
memset(de,0,sizeof de);de[s]=1;
Q[hd=tl=1]=s;int now;
while(hd<=tl){
now=Q[hd++];cur[now]=head[now];
if(now==t) return 1;
for(int i=head[now];i;i=ne[i]){
if(!weight[i] || de[to[i]]) continue;
de[to[i]]=de[now]+1;Q[++tl]=to[i];
}
}
return 0;
}
inline int dinic(int now, int flow){
if(now==t) return flow;
int maxnflow=0, res;
for(int i=cur[now];i && flow;i=ne[i]){
cur[now]=i;
if(weight[i] && de[to[i]]==de[now]+1){
res=dinic(to[i],min(flow,weight[i]));
weight[i]-=res;
weight[i^1]+=res;
flow-=res;
maxnflow+=res;
}
}
if(maxnflow==0) de[now]=0;
return maxnflow;
}
int tmp;
inline int Get(int v){
tmp=lower_bound(b+1,b+1+len,v)-b;
if(b[tmp]==v) return tmp;
return 2e9;
}
inline void Add(int node, int v){
if(v>=1e9 || v<0) return ;
add(node,v,1);
add(v,node,0);
}
inline void output(int p1, int p2, int dis){
h[1]=1e9;int r;
for(int i=2;i<=n;++i){
for(int j=head[i];j;j=ne[j]){
if(to[j]!=s){
if(weight[j]==0){
r=to[j]-n;
if(b[r]==a[i]+dis) h[i]=p1-a[i];
else if(b[r]==a[i]-dis) h[i]=p1+a[i];
else if(b[r]+a[i]==dis) h[i]=p1+a[i];
break;
}
}
}
}
int minn=3e9;minn=min(minn,p1), minn=min(minn,p2);
for(int i=1;i<=n;++i) minn=min(minn,h[i]);
p1-=minn, p2-=minn;
for(int i=1;i<=n;++i) sprint(h[i]-minn);
putchar(10);
sprint(p1), eprint(p2);
}
inline void Judge(int p1, int p2, int dis, int i){
if(p1>p2) return ;
int maxnflow=0;
memset(head,0,sizeof head);cnt=1;
for(int j=2;j<=n;++j){
if(a[j]<=dis) {
Add(j,Get(dis+a[j])+n);
Add(j,Get(dis-a[j])+n);
}
else{
Add(j,Get(dis+a[j])+n);
Add(j,Get(a[j]-dis)+n);
}
Add(s,j);
}
for(int j=1;j<=n;++j){
if(j==i) continue;
add(c[j]+n,j+2*n,1);
add(j+2*n,c[j]+n,0);
add(j+2*n,t,1);
add(t,j+2*n,0);
}
maxnflow=0;
while(spfa()) maxnflow+=dinic(s,inf);
if(maxnflow==n-1){
YES;
sol=1;
output(p1,p2,dis);
return ;
}
}
inline void solve(){
n=read();s=0, t=3*n+1;
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read(), c[i]=b[i];
sort(a+1,a+1+n);sort(b+1,b+1+n);
bool flag=0;
for(int i=1;i<=n;++i){
if(a[i]==b[i]) continue;
flag=1;break;
}
len=unique(b+1,b+1+n)-b-1;
b[0]=b[len+1]=-1;b[len+2]=-1;
for(int i=1;i<=n;++i)
c[i]=lower_bound(b+1,b+1+len,c[i])-b;
if(flag==0){
YES;
for(int i=1;i<=n;++i) sprint((long long)1e9-a[i]);
putchar(10);
sprint(1e9), eprint(1e9);
return ;
}
int p1, p2, pos, dis;
int maxnflow=0;sol=0;
for(int i=1;i<=n;++i){
pos=1e9;
Judge(pos-a[1],pos+b[c[i]],a[1]+b[c[i]],i);
if(sol) return ;
Judge(pos-a[1],pos-b[c[i]],abs(a[1]-b[c[i]]),i);
if(sol) return ;
Judge(pos+a[1],pos+b[c[i]],abs(a[1]-b[c[i]]),i);
if(sol) return ;
}
NO;
return ;
}
signed main(){
int t=read();
while(t--) solve();
return 0;
}