题意

一个n*m的矩阵，初始值全为0，每一行每一列操作一次可以加1或者减1，问能否操作得到给定矩阵。

分析

行和列的分别的加减是可以相互抵消的，因此我们只需要考虑行的加和列的减。
对于给定矩阵每一个数\(x\)，假设对应行\(u\)加上\(r_u\)次，对应列\(v\)减去\(c_v\)次，即\(r_u+c_v=x\)，转化为不等式，即

\[r_u-c_v<=x
\\
c_v-r_u<=-x
\]

对于这样的不等式，使用差分约束系统转化为图论问题，即建边\((v+n,u,x)\)和\((u,v+n,-x)\)，然后判断是否有解，只需用spfa判负环即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=1e5+50;

const int INF=0x3f3f3f3f;

int T,n,m,k,u,v,w;

struct Edge{

    int v,w,next;

}e[N];

int cnt,head[N];

void init(){

    cnt=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v,int w){

    e[cnt]=Edge{v,w,head[u]};

    head[u]=cnt++;

}

int vis[N],dis[N];

bool spfa(int s){

    for(int i=1;i<=s;i++){

        vis[i]=0;

        dis[i]=INF;

    }

    queue<int> q;

    q.push(s);

    vis[s]++;

    dis[s]=0;

    while(!q.empty()){

        int u=q.front();

        q.pop();

        for(int i=head[u];i!=-1;i=e[i].next){

            int v=e[i].v;

            int w=e[i].w;

            if(dis[v]>dis[u]+w){

                dis[v]=dis[u]+w;

                q.push(v);

                vis[v]++;

                if(vis[v]>s+1){

                    return true;

                }

            }

        }

    }

    return false;

}

int main(){

//    freopen("in.txt","r",stdin);

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d",&n,&m,&k);

        init();

        int s=n+m+1;

        for(int i=1;i<s;i++){

            add(s,i,0);

        }

        for(int i=1;i<=k;i++){

            scanf("%d%d%d",&u,&v,&w);

            add(v+n,u,w);

            add(u,v+n,-w);

        }

        if(spfa(s)){

            printf("No\n");

        }else{

            printf("Yes\n");

        }

    }

    return 0;

}

巴特西

luoguP4578_ [FJOI2018]所罗门王的宝藏

题意

分析

代码

最新文章

热门文章