题解 P1557 【Kruscal的加法】

2018-03-07 20:21:07


最小生成树Kruscal的加法

本蒟蒻写得很粗鲁,请dalao见谅。

AC须准备:

可以不考虑负数的高精度(加法,乘法,减法),我喜欢叫它Int

Int ans1,ans_1; ans1记录+x,ans_1记录-x

接下来:

把数字按照不同表示方法拿下来,累加到ans1或ans_1

比较ans1与ans_1的大小,处理后输出。

具体请参考代码:

//我喜欢把某一部分的注释写在那一部分下面
#include<cstdio>
#include<cstring>
#include<algorithm>
#define TT 10000

using namespace std;

char s[2005];

class Int
{
public:
    int a[505],len;
    Int()
    {
        memset(a,0,sizeof(a));
        len=0;
    }
    Int(int x)
    {
        memset(a,0,sizeof(a));
        len=0;
        while(x)
        {
            a[++len]=x%TT;
            x/=TT;
        }
    }
    Int operator +(Int b)
    {
        Int c;
        c.len=max(len,b.len);
        for(int i=1;i<=c.len;++i)
        {
            c.a[i]+=a[i]+b.a[i];
            c.a[i+1]=c.a[i]/TT;
            c.a[i]%=TT;
        }
        if(c.a[c.len+1])
            c.len++;
        return c;
    }
    //高精度加法不解释
    Int operator *(Int b)
    {
        Int c;
        c.len=len+b.len;
        for(int i=1;i<=len;++i)
        {
            for(int j=1;j<=b.len;++j)
            {
                c.a[i+j-1]+=a[i]*b.a[j];
                c.a[i+j]+=c.a[i+j-1]/TT;
                c.a[i+j-1]%=TT;
            }
        }
        while(!c.a[c.len])
            c.len--;
        return c;
    }
    //高精度乘法不解释
    Int operator -(const Int b)
    {
        Int c;
        c.len=max(len,b.len);
        for (int i=1;i<=c.len;i++)
        {
            c.a[i]+=a[i]-b.a[i]+TT;
            c.a[i+1]+=c.a[i]/TT-1;
            c.a[i]%=TT;
        }
        while (c.len>1&&!c.a[c.len]) c.len--;
        return c;
    }
    //高精度减法不解释
    bool operator <(Int b)const
    {
        if(b.len>len)
            return true;
        else if(len>b.len)
            return false;
        for(int i=len;i>0;--i)
        {
            if(b.a[i]>a[i])
                return true;
            if(b.a[i]<a[i])
                return false;
        }
        return false;
    }
    //小于不解释
    void write()
    {
        printf("%d",a[len]);
        for(int i=len-1;i>=1;--i)
            printf("%04d",a[i]);
        printf("\n");
    }
    //输出
}ans1,ans_1;
//ans1记录+x,ans_1记录-x

void ToInt64(int &i)
{
    Int ret=0,cs=0,p=10;
    int f=1;
    if(s[i]=='-')
        f=-1;
    if(s[i+1]=='(')
    {
    //如果按+(2)33表达
        i+=2;
        while(s[i]>='0'&&s[i]<='9')
        {
            Int res=(int)s[i]-'0';
            cs=cs*p+res,++i;
        }
        //拿下括号内数字
        i++;
        while(s[i]>='0'&&s[i]<='9')
        {
            Int res=(int)s[i]-'0';
            ret=ret*p+res,++i;
        }
        //取走要加上的数字
        Int c=ret*cs;
        //这次运算的结果
        if(f==-1)
            ans_1=ans_1+c;
        else
            ans1=ans1+c;
    }
    else if(s[i+1]>='0'&&s[i+1]<='9')
    {
    //如果直接按照+233表达
    //这段里面有个防抄袭用的"错误"
        i++;
        while(s[i]>='0'&&s[i]<='9')
        {
            Int res=(int)s[i]-'0';
            ret=ret*p+res,++i;
        }
        //取走数字
        int c=ret;
        if(f==-1)
            ans_1=ans_1+c;
        else
            ans1=ans1+c;
    }
    else
    {
    //如果是+++233的形式
        i++,cs=1;
        Int res=1;
        while(s[i]=='-'||s[i]=='+')
        {
            cs=cs+res,++i;
        }
        //数一下符号个数
        while(s[i]>='0'&&s[i]<='9')
        {
            Int res=(int)s[i]-'0';
            ret=ret*p+res,++i;
        }
        //拿走数字
        Int c=ret*cs;
        if(f==-1)
            ans_1=ans_1+c;
        else
            ans1=ans1+c;
    }
    //话说+233与+++233是可以并到一起的,这里是我写的过于粗鲁了
}

int main()
{
//不要在luogu配文件!自行遮蔽
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
//不要在luogu配文件!自行遮蔽

    scanf("%s",s+1);
    int i=1;
    while(s[i])
        ToInt64(i);
    if(!(ans1<ans_1)&&!(ans_1<ans1))
    {
        printf("0");
    }
    //如果Σx>0=Σx<0,输出0
    else if(ans1<ans_1)
    {
        ans_1=ans_1-ans1;
        printf("-");
        ans_1.write();
    }
    //如果减数大于被减数,输出一个负号以及ans_1-ans1
    else
    {
        ans1=ans1-ans_1;
        ans1.write();
    }
    //被减数大于减数,直接输出ans1-ans_1
    return 0;
}