题解：P8156 「PMOI-5」奇怪的方程

· · 题解

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

我们设 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
*/