自动搬运

查看原文

来自洛谷，原作者为

	Masterwei **

搬运于2025-08-24 22:36:27，当前版本为作者最后更新于2025-06-27 17:03:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先可以将行的限制干掉，全部转到列上来。

我们设 $g_{i,j}$ 表示第 $i$ 列和第 $j$ 列之间任意一个使得点 $(k,i)$ 和 $(k,j)$ 都没被标记的 $k$，如果没有就是 $0$。

把 $g_{i,j}$ 不为 $0$ 看成 $i,j$ 之间连边，那么最后会形成若干个连通块，对于每个连通块可以直接找生成树，设 $u$ 是生成树上 $v$ 的父亲，贡献就是将 $a_{g_{u,v},v}$ 加上 $B_v$，将 $a_{g_{u,v},u}$ 减去 $B_v$，$B_u$ 加上 $B_v$。

#include<bits/stdc++.h>
#define int long long
#define fir first
#define sec second
using namespace std;
int plen,ptop,pstk[40];
char rdc[1<<20],out[1<<20],*rS,*rT;
#define gc() (rS==rT?rT=(rS=rdc)+fread(rdc,1,1<<20,stdin),(rS==rT?EOF:*rS++):*rS++)
#define pc(x) out[plen++]=(x)
#define flush() fwrite(out,1,plen,stdout),plen=0
template<class T=int>inline T read(){
    T x=0;char ch;bool f=1;
    while(!isdigit(ch=gc()))if(ch=='-')f^=1;
    do x=(x<<1)+(x<<3)+(ch^48);while(isdigit(ch=gc()));
    return f?x:-x;
}
inline int read(char*const s){
	char *t=s,ch;
    while(!isgraph(ch=gc()));
	do(*(t++))=ch;while(isgraph(ch=gc()));
	return (*t)='\000',t-s;
}
template<class T=int>inline void write(T x){
	if(plen>=1000000)flush();
	if(!x)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	for(;x;x/=10)pstk[++ptop]=x%10;
	while(ptop)pc(pstk[ptop--]+'0');
}
inline void write(const char*s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
inline void write(char*const s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
const int Maxn=2005;
int n,m,a[Maxn],b[Maxn],bb[Maxn];
int s[Maxn][Maxn];
bitset<Maxn>vis[Maxn];
int g[Maxn][Maxn];
int f[Maxn];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}

int head[Maxn*2],to[Maxn*Maxn*2],nxt[Maxn*Maxn*2],w[Maxn*Maxn*2],cnt1;
inline void add(int u,int v,int w1){
	to[++cnt1]=v;nxt[cnt1]=head[u];
	w[cnt1]=w1;head[u]=cnt1;
}
int Vis[Maxn];
void dfs(int x){
	if(Vis[x])return;
	Vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];if(Vis[y])continue;
		dfs(y);
		s[w[i]][x]-=b[y];b[x]+=b[y];
		s[w[i]][y]+=b[y];b[y]=0;
	}
}
inline void solve(){
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read(),Vis[i]=0;
	for(int i=1;i<=n;i++)bb[i]=b[i]=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)vis[i][j]=1,g[i][j]=s[i][j]=0;
	while(m--){
		int val=read(),z=read();
		int x=(val-1)/n+1,y=(val-1)%n+1;
		s[x][y]=z;vis[y][x]=0;
		a[x]-=z;b[y]-=z;bb[y]-=z;
	}bitset<Maxn>tmp;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			tmp=(vis[i]&vis[j]);
			int now=tmp._Find_first();
			if(now<=n)g[j][i]=now;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(vis[j][i]==0)continue;
			s[i][j]=a[i];
			a[i]-=s[i][j];b[j]-=s[i][j];
			bb[j]-=s[i][j];
		}
	}
	int sum=0;for(int i=1;i<=n;i++)sum+=b[i];
	if(sum!=0){write("No Solution\n");flush();return;}sum=0;
	for(int i=1;i<=n;i++)sum+=(a[i]!=0);if(sum!=0){write("No Solution\n");flush();return;}
	for(int i=1;i<=n;i++){
		f[i]=i;
		for(int j=i-1;j;j--){
			if(g[j][i]&&find(j)!=i){bb[i]+=bb[find(j)];bb[find(j)]=0;f[find(j)]=i;}
		}
	}
	int ok=1;
	for(int i=1;i<=n;i++)if(bb[i]!=0)ok=0;
	if(!ok){write("No Solution\n");flush();return;}
	cnt1=0;for(int i=1;i<=n*2;i++)head[i]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(g[j][i])add(j,i,g[j][i]),add(i,j,g[j][i]);
		}
	}
	for(int i=1;i<=n;i++){
		if(find(i)!=i)continue;
		dfs(i);
	}
	write("OK\n");
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)write(s[i][j]),pc(' ');
	}flush();
}
signed main(){
//	freopen("matrix3.in","r",stdin);
//	freopen("matrix.out","w",stdout);
	int T=read();while(T--)solve();
	flush();
	return 0;
}
/*
1
3 2
5 12 11
14 6 8
1 2 0
3 1 8
*/