长乐集训DAY5

上午
T2 就是并查集，而且基本是并查集的模板题，然而很难看出来，所以赛时得分为蛋。改题时注意到其实当账本为真时有[a,b]、[b,c]与[a,c]之间的充分必要关系。然后一个并查集模板就把这题带走了。（要注意的有点多，洛谷上输出是true和false，ybt上的是t和f，还有要开longlongint，然后就是要用scanf，int实测TLE）
代码如下

#include
using namespace std;
long long int w,n,m,a,b,c;
long long int bin[1005],sum[1005],cg,bj,pd;
int find(int x)
{
    if(x==bin[x])
    {
        return x;
    }
    else
    {
        cg=find(bin[x]);
        sum[x]+=sum[bin[x]];
        bin[x]=cg;
        return bin[x];
    }
}
int main()
{
    freopen("check.in","r",stdin);
    freopen("check.out","w",stdout);
    scanf("%lld",&w);
    for(int ii=0;ii<w;ii++)
    {
        scanf("%lld%lld",&n,&m);
        for(int j=0;j<=n;j++)
        {
            bin[j]=j;
            sum[j]=0;
        }
        pd=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            a--;            
            if(find(a)!=find(b))
            {
                bj=bin[b];
                sum[bj]=sum[a]-sum[b]-c;
                bin[bj]=bin[a];
            }
            else
            {
                if(sum[a]-sum[b]!=c)
                {
                    pd=1;
                }
            }       
        }
        if(pd==0)
        {
            cout<<"t"<<endl;
        }
        else
        {
            cout<<"f"<<endl;
        }
    }
}

T3 cjx讲过了但是我还是没搞掉
下午
T1 又是模板题，但很难看出来（我是在赛时看输入数据太标准盲猜一波直接敲了一个板子交上去然后AC的）
贴个代码，同时也是最小生成树板子

#include
using namespace std;
int n,a[2005][2005],mx,b[2005],v[2005],poi;
long long int ans,s;
int main()
{
    freopen("cost.in","r",stdin);
    freopen("cost.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j>a[i-1][j];
            a[j][i-1]=a[i-1][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=2147483647;
    }
    for(int i=0;i<=n;i++)
    {
//      cout<<"  -    "<<i<<endl;
        s=4611686018427007904;
        for(int j=0;jb[j])
            {
                s=b[j];
                poi=j;
            }

        }
        v[poi]=1;
        ans+=s;
//          cout<<ans<<"  "v[poi]<<endl;        
        for(int j=0;ja[poi][j])
            {
                b[j]=a[poi][j];
            }
//          cout<<j<<"   "<<b[j]<<endl;
        }
    }
    cout<<ans<<endl;
}