T1

T559。

T2(带权并查集）

1380。
把行和列的取值看成变量，其中行取1代表+1,列取1代表-1,为了凑x - y = c,这样可以拿并查集来做了。
维护d[x]，到根的距离，我们把边定义为+,反向走为-。这样就行了，如果在一个集合，那么判断距离是不是c。
还可以差分约束，dfs（直接遍历一遍，遇到环就判断).

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m, k;
int p[N << 1], d[N];

int find(int x)
{
    if (p[x] == x) return x;
    
    int fa = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = fa;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n + m; i ++ ) p[i] = i;
    while (k -- )
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        y += n;
        int px = find(x), py = find(y);
        if (px != py)
        {
            p[py] = px;
            d[py] = d[x] + c - d[y];
        }
        else if (d[y] - d[x] != c)
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}

T3（带权并查集，与上题类似）

换成乘。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 20010;

int p[N];
double d[N];
int n, m;

int find(int x)
{
    if (p[x] == x) return x;
    int fa = find(p[x]);
    d[x] *= d[p[x]];
    return p[x] = fa;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) p[i] = i, d[i] = 1;
    while (m -- )
    {
        int x, y, a, b;
        scanf("%d%d%d%d", &x, &y, &a, &b);
        int px = find(x), py = find(y);
        if (px != py)
        {
            p[py] = px;
            d[py] = d[x] * a / b / d[y]; 
        }
        else
        {
            if (abs(d[x] - (d[y] * b / a)) >= 1e-5)
            {
                puts("No");
                return 0;
            }
        }
    }
    puts("Yes");
    return 0;
}

T4（差分约束，不等式及相对关系->差分约束）

1129。 https://www.luogu.com.cn/problem/P2474
这个题首先要想到枚举，然而我们不知道他们之间的关系，无法判断。求解相对关系，我们发现a+b = c+d 加法不好处理，这个等式实际上就是a - c = d - b，这样就转化为了求差值的范围，其实就是差分约束。不等式是啥呢？根据给定的图，a-b的关系就给了，floyd求差分约束就行了。最后暴力枚举判断。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int mind[N][N], maxd[N][N];
int n, A, B;
char g[N][N];

void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
            {
                mind[i][j] = max(mind[i][j], mind[i][k] + mind[k][j]);
                maxd[i][j] = min(maxd[i][j], maxd[i][k] + maxd[k][j]);
            }
}

int main()
{
    freopen("balance.in", "r", stdin);
	freopen("balance.out", "w", stdout);
    scanf("%d%d%d", &n, &A, &B);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%s", g[i] + 1);
        for (int j = 1; j <= n; j ++ )
            if (i != j)
            {
                if (g[i][j] == '+') mind[i][j] = 1, maxd[i][j] = 2;
                else if (g[i][j] == '?') mind[i][j] = -2, maxd[i][j] = 2;
                else if (g[i][j] == '-') mind[i][j] = -2, maxd[i][j] = -1;
            }
    }
    floyd();
    int c1 = 0, c2 = 0, c3 = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = i + 1; j <= n; j ++ )
            if (i != j && i != A && i != B && j != A && j != B)
            {
                if (mind[A][i] > maxd[j][B] || mind[A][j] > maxd[i][B]) c1 ++ ;
                if ((maxd[A][i] == mind[A][i] && maxd[j][B] == mind[j][B] && mind[A][i] == maxd[j][B])
                || (maxd[A][j] == mind[A][j] && maxd[i][B] == mind[i][B] && mind[A][j] == maxd[i][B]))
                    c2 ++ ;
                if (maxd[A][i] < mind[j][B] || maxd[A][j] < mind[i][B]) c3 ++ ;
            }
    
    printf("%d %d %d\n", c1, c2, c3);
    fclose(stdin);
    fclose(stdout);
    return 0;
}