此题做法多啊
带权并查集，区间dp，前缀和，差分约束
1.自己写的前缀和, 11
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
const int N=;
inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
int T,n,m,l,r,v,sum,s[N];
int main(){
T=read();
while(T--){
int fg=;
n=read();m=read();
rep(i,,m){
l=read();r=read();v=read();
sum=s[r]-s[l-];
if(sum==) s[r]=s[l-]+v;
else if(sum&&sum!=v){printf("false\n");fg=;break;}}
if(fg) printf("true\n");
}return ;
}
2.自己写的区间dp
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
using namespace std; inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
const int N=;
int T,n,m,x,y,z,p,f[N][N];
int main(){
T=read();
while(T--){
n=read();m=read();
rep(i,,m){
x=read();y=read();z=read();
f[x][y]=z;}
p=;
for(int i=;i<n;i++)if(p)
for(int j=i+;j<=n;j++)if(p)
for(int k=i;k<j;k++)if(p)
if(f[i][k]&&f[k+][j])
if(f[i][j]&&f[i][j]!=f[i][k]+f[k+][j]){
p=;break;}
else f[i][j]=f[i][k]+f[k][j];
if(p==) printf("false\n");
else printf("true\n");
}return ;
}
3.区间dp 100
注意枚举时的方向，此题第二层为逆序（没有明白啊啊啊）
#include<bits/stdc++.h>
using namespace std; inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
const int N=;
int f[N][N],w,n,m,p,s,t,v;
int main(){
w=read();
while(w--){
memset(f,,sizeof(f));
n=read(),m=read();
for(int i=;i<=m;i++){
s=read(),t=read(),v=read();
f[s][t]=v;}
p=;
for(int i=;i<=n;i++)if(p)
for(int j=i-;j>=;j--)if(p)
for(int k=j;k<i;k++)
if(f[j][k]&&f[k+][i]){
if(f[j][i]&&f[j][i]!=f[j][k]+f[k+][i])
{p=;break;}
else f[j][i]=f[j][k]+f[k+][i];}
if(p==) printf("false\n");
else printf("true\n");
}
return ;
}
4.带权并查集
Attention!!!!!
f,ff提前取出来，不明原因，惨痛的教训。。。问提交满了一整页是怎样的感受
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define dec(i,x,y) for(register int i=x;i>=y;i--)
#define int long long
using namespace std;
const int N=;
inline int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;}
int T,n,m,x,y,z,fg,xx,yy,fa[N],cha[N];
int find(int x){
if(fa[x]==x) return x;
int f=fa[x],ff=find(fa[x]);cha[x]+=cha[f];
//先推直接父亲权值，再路径压缩
fa[x]=ff;return ff;
}
signed main(){
T=read();
while(T--){
fg=;n=read();m=read();
rep(i,,n) fa[i]=i,cha[i]=;
rep(i,,m){
x=read();y=read();z=read();x--;
xx=find(x),yy=find(y);
if(xx!=yy){
fa[yy]=xx,cha[yy]=cha[x]+z-cha[y];}
//此处 y连接在x 的子树上，y的深度大
else
if(cha[y]-cha[x]!=z) fg=;
}if(fg) printf("true\n");else printf("false\n");
}
}
5.差分约束+spfa判断（实在不想写这道题了啊啊啊）
#include <cstdio>
#include <vector>
using namespace std; const int maxn = ;
const int maxm = ; struct node{
int to, val;
};
vector<node> e[maxn];
int t, n, m, dis[maxn];
bool vis[maxn], flag; void SPFA(int x){ \\其实就是 DFS
vis[x] = ;
for(int i = ; i < e[x].size(); i++){
node v = e[x][i];
if(dis[v.to] > dis[x] + v.val){
if(vis[v.to]){flag = ; return;}
dis[v.to] = dis[x] + v.val;
SPFA(v.to);
}
}
vis[x] = ;
return;
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u-].push_back((node){v, w});
e[v].push_back((node){u-, -*w}); //建图
}
for(int i = ; i <= n; i++){
dis[i] = ;
SPFA(i);
if(flag) { break;}
}
if(flag) printf("false\n");
else printf("true\n");
for(int i = ; i <= n; i++){ \\记得在判断完每一组之后复位
vis[i] = ;
dis[i] = ;
e[i].clear();
}
flag = ;
}
return ;
}