频道栏目
首页 > 考试 > 其他 > 正文
bzoj1202: [HNOI2005]狡猾的商人
2017-04-08 09:26:13         来源:zyy大蒟蒻的博客  
收藏   我要投稿

边上带权的并查集裸题。
或者直接暴力加边求权值差。

#include
#include
#include
#include
#include
#include 
using namespace std;
int f[105],v[105],fl,T,x,y,z,p,q,n,m;
int get(int x){
    if (f[x]==x) return x;
    int t=get(f[x]);
    v[x]+=v[f[x]];
    return f[x]=t;
}
int main(){
    scanf("%d",&T);
    while (T--){
        memset(v,0,sizeof(v));
        fl=0;
        scanf("%d%d",&n,&m);
        for (int i=0;i<=n;i++) f[i]=i;
        for (int i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z); x--;
            p=get(x); q=get(y);
            if (p!=q){
                f[p]=q;
                v[p]=v[y]-v[x]-z;
            }
            else if (v[y]-v[x]!=z) fl=1;
        }
        puts(fl?"false":"true");
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:HDU 2041 超级楼梯(递推)
下一篇:S-Nim(fromHDU)(博弈)(Sprague-Grundy定理)(nim问题加强版)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站