【BZOJ 1202】 [HNOI2005]狡猾的商人(枚举区间也可行)

题链：http://www.lydsy.com/JudgeOnline/problem.php?id=1202

其实也可以不使用加权并查集，通过画图可以发现，一个长区间和其包含的区间能够算出一个新区间(即长区间剩余部分),只要这个区间不与已存在的区间冲突，那么这个区间就是正确的，同时将这个新生成的区间记录下来即可，设其为正确区间，从而保证新算出的区间不产生冲突。

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <vector>

#define ll long long

#define inf 0x3f3f3f3f

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=105;

int a[N][N];

struct node

{

    int l,r,c,len;

    bool operator < (const node &an) const{

        return len<an.len;

    }

}b[N];

int main()

{

    int T=read();

    while(T--){

        int n=read(),m=read();

        int u,v,c,flag=0;

        memset(a,0x3f,sizeof(a));

        for(int i=0;i<m;i++){

            u=read();v=read();c=read();

            if(a[u][v]!=inf) flag=1;

            a[u][v]=c;

            b[i].l=u;b[i].r=v;

            b[i].c=c;b[i].len=v-u;

        }

        sort(b,b+m);

        for(int i=1;i<m;i++){

            for(int j=0;j<i;j++){

                if(b[i].l==b[j].l&&b[i].r>b[j].r){

                    u=b[j].r+1;v=b[i].r;

                    c=b[i].c-b[j].c;

                    if(v<u) continue;

                    if(a[u][v]!=inf&&a[u][v]!=c){

                        flag=1;

                        break;

                    }

                    else a[u][v]=c;

                }

                if(b[i].r==b[j].r&&b[i].l<b[j].l){

                    u=b[i].l;v=b[j].l-1;

                    c=b[i].c-b[j].c;

                    if(v<u) continue;

                    if(a[u][v]!=inf&&a[u][v]!=c){

                        flag=1;

                        break;

                    }

                    else a[u][v]=c;

                }

            }

            if(flag) break;

        }

        if(flag) puts("false");

        else puts("true");

    }

    return 0;

}

巴特西

【BZOJ 1202】 [HNOI2005]狡猾的商人(枚举区间也可行)

最新文章

热门文章