NOI2015 T1 程序自动分析

Posted by

集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。 如果数据过大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。 了解完并查集后,让我们看看NOI2015的签到题:程序自动分析 题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4195 题目的大概意思,就是给你n行数据,每一行有三个数组成,前两个是数据,第三个是状态。若第三个为1,则判定的是前两个相等,反之亦然。

为什么要用并查集?
我们在看到这道题的数据范围后便感到。。。。。。 1<=n<=10*5;1<=x<=10*9 所以在这么大的数据范围面前,我们在用并查集的同时我们还需使用离散化,即用map映射。(不懂map映射的可以去了解了解) 代码如下:
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
map <int,int> mp,s;
int Father[2500000],t,num,n,w[2500000];
struct node
{
  int x,y,z;
}a[1500000];
int find(int o)
{
  if(Father[o]!=o) Father[o]=find(Father[o]);
  return Father[o];
}
int main()
{
  scanf("%d",&t);
  while(t--)
  {
    mp.clear();
    s.clear();
    num=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
      scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
      if(!s[a[i].x]) s[a[i].x]=1,w[++num]=a[i].x;
      if(!s[a[i].y]) s[a[i].y]=1,w[++num]=a[i].y;
    }
    sort(w+1,w+1+num);
    for(int i=1;i<=num;i++) mp[w[i]]=i;
    for(int i=1;i<=n;i++)
    {
      a[i].x=mp[a[i].x];
      a[i].y=mp[a[i].y];
    }
    for(int i=1;i<=num;i++) Father[i]=i;
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
      int u=find(a[i].x),v=find(a[i].y);
      if(a[i].z)
      {
        if(u!=v) Father[u]=v;
      }
      else
      {
        if(u==v)
        {
          flag=false;
          break;
        }
      }
    }
    if(!flag)
    {
      printf("NO\n");
      continue;
    }
    for(int i=1;i<=n;i++)
    {
      int u=find(a[i].x),v=find(a[i].y);
      if(u==v&&!a[i].z)
      {
        flag=false;
        break;
      }
      if(u!=v&&a[i].z)
      {
        flag=false;
        break;
      }
    }
    if(!flag) printf("NO\n");
    else printf("YES\n");
  }
  return 0;
}
]]>

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注