BZOJ 4500: 矩阵 带权并查集
2024-10-20 15:50:54
这个思路挺巧妙的 ~
定义一行/列的权值为操作后所整体增加的值.
那么,我们会有若干个 $a[x]+b[y]=c$ 的限制条件.
但是呢,我们发现符号是不能限制我们的(因为可加可减)
所以可以将限制条件转化为 $a[x]-b[y]=c$.
这个用带权并查集就可以方便地维护了~
code:
#include <bits/stdc++.h>
#define N 2006
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int p[N],dis[N],z[N],x[N],y[N];
int find(int x)
{
if(p[x]==x) return x;
int rt=find(p[x]);
dis[x]=dis[x]+dis[p[x]];
p[x]=rt;
return rt;
}
void solve()
{
int n,m,k,i,j;
scanf("%d%d%d",&n,&m,&k);
for(i=1;i<=k;++i) scanf("%d%d%d",&x[i],&y[i],&z[i]),y[i]+=n;
for(i=1;i<=n+m;++i) p[i]=i, dis[i]=0;
for(i=1;i<=k;++i)
{
int xx=find(x[i]), yy=find(y[i]);
if(xx!=yy)
{
p[xx]=yy;
dis[xx]=z[i]+dis[y[i]]-dis[x[i]];
}
else if(dis[x[i]]-dis[y[i]]!=z[i]) break;
}
if(i>k) printf("Yes\n");
else printf("No\n");
}
int main()
{
// setIO("input");
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
最新文章
- log4net 添加日志
- javascript中原型(prototype)与原型链
- cocos基础教程(9)声音和音效
- eclipse 向HDFS中创建文件夹报错 permission denied
- BZOJ3827 : [Poi2014]Around the world
- ArrayList调用remove方法需要注意的地方
- CKEditor (Toolbar Definition)工具栏自定义配置
- 简单的圆形图标鼠标hover效果 | CSS3教程
- ajax.abort 终止AJAX请求
- [Locked] Shortest Distance from All Buildings
- oracle监听
- python高级编程 编写一个包1
- jQuery 查找带有某一属性的元素
- vscode 开发工具
- python之闭包与装饰器
- 简述在javascript和jquery中cookie的使用
- js 原生转json 可以v8中运行
- Red hat查找命令所属的rpm包
- 微信 H5 支付流程以及一些坑
- InterBase 数据库与驱动 版本不同