bzoj 4500: 矩阵差分约束系统

题目:

Description

有一个n*m的矩阵，初始每个格子的权值都为0，可以对矩阵执行两种操作：

选择一行，该行每个格子的权值加1或减1。

选择一列，该列每个格子的权值加1或减1。

现在有K个限制，每个限制为一个三元组(x,y,c)，代表格子(x,y)权值等于c。

问是否存在一个操作序列，使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”，否则输出”No”。

题解:

如果我们将所有的行作为变量$x$,所有的列作为变量$y$.

变量本身代表对这行(列)进行的操作数(x,y可以为负)

所以对于每一个三元限制我们可以列出方程$x_i + y_i = c_i$

然后我们移项得到$x_i - c_i = y_i$

这样我们可以依据这个等式列出两个不等式:

$ x_i - c_i \leq y_i $
$ y_i - (-c_i) \leq x_i $

然后我们建立差分约束系统,dfs判正环即可.

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

    x=0;char ch;bool flag = false;

    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 2048;

const int maxm = 1024*1024;

struct Edge{

    int to,next,dis;

}G[maxm];

int head[maxn],cnt;

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

    G[++cnt].to = v;

    G[cnt].next = head[u];

    head[u] = cnt;

    G[cnt].dis = d;

}

int dis[maxn];bool inq[maxn];

inline void init(){

    memset(head,0,sizeof head);

    memset(dis,-0x3f,sizeof dis);

    memset(inq,false,sizeof inq);

    cnt = 0;

}

#define v G[i].to

bool dfs(int u){

    inq[u] = true;

    for(int i = head[u];i;i=G[i].next){

        if(dis[v] < dis[u] + G[i].dis){

            dis[v] = dis[u] + G[i].dis;

            if(inq[v]) return false;

            if(!dfs(v)) return false;

        }

    }

    inq[u] = false;

    return true;

}

#undef v

int x[maxn],y[maxn],c[maxn];

int work(){

    init();

    int n,m,k;read(n);read(m);read(k);

    for(int i=1;i<=k;++i) read(x[i]),read(y[i]),read(c[i]);

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

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

            if(x[i] == x[j] && y[i] == y[j] && c[i] != c[j]) return puts("No");

            if(x[i] == x[j] && y[i] == y[j]) continue;

            if(x[i] == x[j] && c[i] - c[j] >= 0){

                add(y[j]+n,y[i]+n,c[i]-c[j]);

                add(y[i]+n,y[j]+n,c[j]-c[i]);

            }

            if(y[i] == y[j] && c[i] - c[j] >= 0){

                add(x[j],x[i],c[i]-c[j]);

                add(x[i],x[j],c[j]-c[i]);

            }

        }

    }

    for(int i=1;i<=n+m;++i) if(!dfs(i)) return puts("No");

    return puts("Yes");

}

int main(){

    int T;read(T);

    while(T--) work();

    getchar();getchar();

    return 0;

}

巴特西

bzoj 4500: 矩阵差分约束系统

题目:

题解:

最新文章

热门文章

巴特西

bzoj 4500: 矩阵 差分约束系统

题目:

题解:

最新文章

热门文章

bzoj 4500: 矩阵差分约束系统