#P17977. Finances
Finances
Finances
题目描述
有 位朋友需要结清债务。第 位朋友的净余额为 :正值表示应收款,负值表示应付款。所有净余额之和为零,且至少一个余额非零。
他们之间有 对信任关系。第 对关系由 表示:两人可以选择一个方向,进行一笔金额为整数、至多为 的转账,也可以不转账。没有直接信任关系的两人不能直接转账。最终希望每个人实际收到的金额减去转出的金额等于其初始净余额,从而结清所有债务。
令总债务为
保证每条信任关系的上限都满足
信任关系构成连通无向图,无重边、无自环。可以假设每个人都有足够的钱执行安排的转账,无须考虑转账的先后次序。
判断是否存在一种转账方案,使所有债务都得到结清。只需要回答能否实现,不需要输出方案。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例中,第一行两个整数 。
第二行 个整数 。
接下来 行,每行三个整数 ,描述一对信任关系。
输出格式
每个测试用例输出一行:能结清所有债务时输出 TAK,否则输出 NIE。
数据范围
- ;
- ,;
- ,,至少一个 ;
- ,;
- ;
- 图连通且无重边;
- 所有测试用例的 之和不超过 , 之和也不超过 。
样例
输入
3
2 1
20 -20
1 2 10
5 6
0 1 1 1 -3
1 2 2
2 3 3
3 4 5
2 4 7
1 5 2
4 5 2
3 2
1 2 -3
1 2 1000000000000000
2 3 999997235527681
输出
NIE
TAK
TAK
样例说明
第一组需要在两人之间转账 ,但唯一一条信任关系只允许转账至多 ,因此无解。