Luogu

LOJ

分析

这垃圾题目竟然调了我半天...

考虑差分约束。设 $a_x$ 表示第 $x$ 行增加了多少,$b_y$ 表示第 $y$ 列减少了多少。

对于每个绿宝石 $(x,y,c)$ ,有 $a_x-b_y=c$ 。

于是从 $y$ 向 $x$ 连边权为 $c$ 的边,从 $x$ 向 $y$ 连边权为 $-c$ 的边即可。

注意到还有一些条件:$a_x\geq 0,b_y\geq 0$ 。建一个 $0$ 点,那么就是 $0-a_x\leq 0,0-b_y\leq 0$ ,从 $x$ 向 $0$ 、从 $y$ 向 $0$ 连边权为 $0$ 的边即可。

那么就只需要判断图中是否存在负环了。

然后这样子不好 SPFA ,可以把所有边反过来,判断图中是否存在正环即可。

我也不知道为什么这是对的,但是既然能过那就是对的吧

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int n,m,k;

struct edge { int v,w,nxt; } e[N<<1];
int head[N],e_cnt=0;

inline void addEdge(int u,int v,int w) {
    e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt;
}

int dis[N],inq[N],cnt[N];
inline int spfa() {
    memset(dis,0xc0,sizeof(dis)),dis[0]=0;
    memset(inq,0,sizeof(inq)),memset(cnt,0,sizeof(cnt));
    queue<int> Q; Q.push(0);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w;
            if (dis[u]+w>dis[v]) {
                dis[v]=dis[u]+w,cnt[v]=cnt[u]+1;
                if (cnt[v]>n+m) return 1;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return 0;
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),e_cnt=0;
        n=read(),m=read(),k=read();
        for (re int i=1;i<=k;++i) {
            int x=read(),y=read()+n,c=read();
            addEdge(x,y,c),addEdge(y,x,-c);
        }
        for (re int i=1;i<=n+m;++i) addEdge(0,i,0);
        puts(spfa()?"No":"Yes");
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 31 PM