注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

bzoj1202【HNOI2005】狡猾的商人解题报告  

2014-04-03 14:08:00|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目链接

这题的话……似乎能用差分约束做?(差分约束题解传送门,话说我连什么是差分约束都不知道汗)

当然,更常见的解法是扩展并查集,利用前缀和,设v[x]为第一个月~第x个月的利润总和(其实根据程序是到第x个月月底的利润总和),然后如果读进来的两个月如果在一个集合里那么就判它们之间的利润差是否符合要求,否则把它们所在的集合合并。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

#define maxn 1010
int f[maxn],v[maxn];
int n,m;
bool flag;

int fa(int t)
{
   if (f[t]==treturn t;
   int tmp=fa(f[t]);
   v[t]+=v[f[t]];
   f[t]=tmp;
   return f[t];
}

void work(int l,int r,int q)
{
   int fl=fa(l),fr=fa(r);
   if (fl!=fr)
   {
       f[fl]=fr;
       v[fl]=v[r]-v[l]-q;
   } else
   if (v[r]-v[l]!=q)
   {
       flag=false;
       return;
   }
}

int main()
{
   int test;
   scanf("%d",&test);
   while (test--)
   {
       scanf("%d%d",&n,&m);
       memset(v,0,sizeof(v));
       for (int i=0;i<=n;i++f[i]=i;
       flag=true;
       for (int i=1;i<=m;i++)
       {
           int x,y,v;
           scanf("%d%d%d",&x,&y,&v);
           work(x-1,y,v);
           if (!flagbreak;
       }
       if (flagprintf("true\n");else printf("false\n");
   }
   return 0;
}

  评论这张
 
阅读(1)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017