自动搬运

查看原文

来自洛谷，原作者为

	Lele_Programmer Ad Astra Per Aspera || F1 车迷 || Love Miku

搬运于2025-08-24 23:13:43，当前版本为作者最后更新于2025-06-10 22:49:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P12209 题解

思路

记交易编号为 $i$ 的第 $j$ 个输出为 $d_{i,j}$，其是否被使用过为 $g_{i,j}$。

每一次处理输入的时候，如果 $fromTxId$（下文称 $id$）和 $fromTxOutNumber$（下文称 $num$） 均为 $-1$，则标记 $flag$ 为 $1$，表示出现特殊交易，否则的话，如果 $id<i$ 即引用的输出必须在此之前并且 $g_{id,num}$ 为 $0$ 即还未用过，则将 $d_{id,num}$ 加入 $add$ 中，并将 $g_{id,num}$ 标为 $1$，如果至此还不能成为合法输入，则标记为不合法。

至此，如果合法，那么来处理交易输出，读入用户的 $account$ 压根没用，读入 $val$，则从 $add$ 中减去 $val$，并将 $d_{i,j}$ 设置为 $val$。

处理完输出，如果已经 $flag$ 为 $1$ 即存在特殊交易，则无需判定无解，如果 $add$ 不是等于 $0$，则无解。

代码

const int N=105;
const int M=1005;

int T,n,m;
int d[M][N];
bool g[M][N];

int main() {
    read(T);
    while (T--) {
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        read(n),read(m);
        bool yes=true;
        _rep(i,0,m-1) {
            int inc;
            read(inc);
            bool flag=false;
            bool ok=true;
            int add=0;
            _rep(j,0,inc-1) {
                int id,num;
                read(id),read(num);
                if (!~id && !~num) flag=true;
                else if (id<i && !g[id][num]) add+=d[id][num],g[id][num]=true;
                else ok=false;
            }
            if (!ok) yes=false;
            int ouc;
            read(ouc);
            _rep(j,0,ouc-1) {
                int acc,val;
                read(acc),read(val);
                add-=val,d[i][j]=val;
            }
            if (flag) continue;
            if (add!=0) yes=false;
        }
        if (yes) puts("YES");
        else puts("NO");
    }
    return 0;
}