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;
}
