《高手训练》解题报告 3.4 差分约束系统

差分约束系统的练习题。

对应 OJ 的 传送门

《高手训练》解题报告集合:信息学奥赛一本通·高手训练

差分约束系统

差分约束系统是一种特殊的 \(n\) 元一次不等式组。差分约束系统包含 \(n\) 个变量 \( x _ 1 , x _ 2 , \cdots , x _ n \) 以及 \( m \) 个约束条件,每个约束条件是由两个其中的变量做差构成的,形如 \( x _ i – x _ j \leq c _ k \),其中 \( 1 \leq i , j \leq n , i \ne j \) 并且 \( c _ k \) 是常数(可以是非负数,也可以是负数)。我们要解决的问题是:求一组解 \( x _ 1 = a _ 1 , x _ 2 = a _ 2 , \cdots , x _ n = a _ n\),使得差分约束系统的约束条件得到满足,否则判断出无解。

差分约束系统中的每个约束条件 \( x _ i – x _ j \leq c _ k \) 都可以变形成 \( x _ i \leq x _ j + c _ k \),这与单源最短路中的三角形不等式 \( \texttt {dis} _ y \leq \texttt {dis} _ x + z \) 非常相似。因此,我们可以把每个变量 \( x _ i \) 看做图中的一个结点,对于每个约束条件 \( x _ i – x _ j \leq c _ k \),从结点 \( j \) 向结点 \( i \) 连一条长度为 \( c _ k \) 的有向边。这样就转化了差分约束系统。

注意到,如果 \( \{ a _ 1 , a _ 2 , \cdots , a _ n \} \) 是该差分约束系统的一组解,那么对于任意的常数 \( d \),\( \{ a _ 1 + d , a _ 2 + d , \cdots ,a _ n +d \} \) 显然也是该差分约束系统的一组解,因为这样做差后 \( d \) 刚好被消掉。

设 \( \texttt {dis} _ 0 = 0 \) 并向每一个点连一条权重为 \( 0 \) 边,跑单源最短路,若图中存在负环,则给定的差分约束系统无解,否则,\( x _ i = \texttt {dis} _ i \) 为该差分约束系统的一组解。

一般使用 Bellman-Ford 算法或队列优化的 Bellman-Ford(俗称 SPFA,在某些随机图跑得很快)判断图中是否存在负环,最坏时间复杂度为 \( O ( n m ) \)。

小 K 的农场 BZOJ3436

时空限制:\( 1 \texttt {s} , 128 \texttt {MiB} \)。

题目描述

小 K 建立了 \( n \) 个农场,他忘记了每个农场中种植作物的具体数量,只记得一些含糊的信息(共 \( m \) 个),以下列三种形式描述:

  1. 农场 \( a \) 比农场 \( b \) 至少多种植了 \( c \) 个单位的作物;
  2. 农场 \( a \) 比农场 \( b \) 至多多种植了 \( c \) 个单位的作物;
  3. 农场 \( a \) 与农场 \( b \) 种植的作物数一样多。

但是,由于小 K 的记忆有些偏差,所以他想要知道存不存在一种情况,使得农场的种植作物数量与他记忆中的所有信息吻合。

数据范围

对于 \( 100 \% \) 的数据保证:\( 1 \leq n , m , a , b , c \leq 10 ^ 4 \)。

题解

  1. 农场 \( a \) 比农场 \( b \) 至少多种植了 \( c \) 个单位的作物,即 \( f _ a \geq f _ b + c \),转化为 \( f _ b \leq f _ a – c \);
  2. 农场 \( a \) 比农场 \( b \) 至多多种植了 \( c \) 个单位的作物,即 \( f _ a \leq f _ b + c \),转化为 \( f _ a \leq f _ b + c \);
  3. 农场 \( a \) 与农场 \( b \) 种植的作物数一样多,即 \( f _ a = f _ b \),转化为 \( f _ a \leq f _ b + 0 \),\( f _ b \leq f _ a + 0 \)。

直接套用差分约束系统,用 \( \texttt {spfa} \) 求负环即可。

#include <cstdio> //头文件

const int MAXN = 10000 + 5; //数据范围

bool inStack[MAXN], vis[MAXN];									   //inStack[i] 表示 i 是否在栈中
int n, m;														   //
int cnt, head[MAXN], to[MAXN << 2], w[MAXN << 2], Next[MAXN << 2]; //邻接表存图
int dis[MAXN];

void Add_Edge(int, int, int); //加边的函数
bool SPFA(int);				  //dfs 版 spfa

int main(void)
{
	register int i;
	scanf("%d%d", &n, &m);	 //读入 n,m
	for (i = 1; i <= n; ++i) //加边
	{
		Add_Edge(i, 0, 0);
		Add_Edge(n + 1, i, 0);
	}
	for (i = 1; i <= m; ++i) //按题目要求读入差分约束系统的约束条件
	{
		static int opt, a, b, c;
		scanf("%d%d%d", &opt, &a, &b);
		if (opt == 3)
		{
			Add_Edge(a, b, 0); //差分约束系统
			Add_Edge(b, a, 0); //差分约束系统
		}
		else
		{
			scanf("%d", &c);
			if (opt == 1)
				Add_Edge(a, b, c); //差分约束系统
			if (opt == 2)
				Add_Edge(b, a, -c); //差分约束系统
		}
	}
	puts(SPFA(n + 1) ? "Yes" : "No"); //输出答案
	return 0;
}

void Add_Edge(int u, int v, int len)
{ //加边的函数
	Next[++cnt] = head[u];
	to[cnt] = v;
	w[cnt] = len;
	head[u] = cnt;
	return;
}

bool SPFA(int ID)
{ //dfs 版 spfa 判负环,压了行
	register int i;
	for (inStack[ID] = true, i = head[ID]; i; i = Next[i])
		if ((!vis[to[i]] || dis[to[i]] < dis[ID] + w[i]) && (inStack[to[i]] || (vis[to[i]] = true, dis[to[i]] = dis[ID] + w[i], !SPFA(to[i]))))
			return false;
	return !(inStack[ID] = false); //没找到负环返回 false
}

账本核算 trader

时空限制:\( 1 \texttt {s} , 162 \texttt {MiB} \)。

题目描述

小 D 接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了 \( n \) 个月以来的收入情况,其中第 \( i \) 个月的收入额为 \( A _ i ( i = 1 , 2 , 3 , \cdots , n − 1 , n ) \)。当 \( A _ i \) 大于 \( 0 \) 时表示这个月盈利 \( A _ i \) 元,当 \( A _ i \) 小于 \( 0 \) 时表示这个月亏损 \( A _ i \) 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。小 D 的任务是秘密进行的,每次查看账本时她都只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。现在,小 D 总共查看了 \( m \) 次账本,当然也就记住了 \( m \) 段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。

数据范围

对于 \( 100 \% \) 的数据,满足 \( T < 100 \),\( n , m < 100 \),\( 1 \leq x \leq y \leq n \)。

题解

定义前缀和数组 \( \text {sum} _ i \),那么显然有 \( \text {sum} _ y – \text {sum} _ { x – 1 } = w \),符合差分约束系统形式。

套用差分约束系统,然后用 \( \texttt {spfa} \) 求负环即可。

#include <bits/stdc++.h> //万能头文件
using namespace std; //命名空间
#define reg register //寄存器变量
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void) //快读
{
	reg bool f = false;
	reg char ch = getchar();
	reg int res = 0;
	while (ch < '0' || '9' < ch)
		f |= (ch == '-'), ch = getchar();
	while ('0' <= ch && ch <= '9')
		res = 10 * res + ch - '0', ch = getchar();
	return f ? -res : res;
}

const int MAXN = 1e3 + 5; //数据范围
const int MAXM = 2e3 + 5; //数据范围

int n, m;
int cnt, head[MAXN], to[MAXM << 1], w[MAXM << 1], Next[MAXM << 1]; //邻接表存图

inline void Add_Edge(reg int u, reg int v, reg int len) //加边函数
{
	Next[++cnt] = head[u];
	to[cnt] = v;
	w[cnt] = len;
	head[u] = cnt;
	return;
}

bool flag;		//是否找到负环
bool vis[MAXN]; //是否在栈中
int f[MAXN];	//最短路

inline void spfa(reg int u)
{
	if (flag)
		return; //剪枝
	vis[u] = true;
	for (reg int i = head[u]; i; i = Next[i])
	{
		reg int v = to[i];
		if (f[v] > f[u] + w[i])
		{
			if (vis[v]) //如果在栈中且能松弛
			{
				flag = true; //存在负环
				return;		 //直接返回
			}
			f[v] = f[u] + w[i];
			spfa(v); //递归
		}
	}
	vis[u] = false;
	return;
}

int main(void)
{
	reg int T = read(); //多组数据
	while (T--)
	{
		cnt = 0, memset(head, 0, sizeof(head)); //初始化
		memset(f, 0, sizeof(f));				//初始化
		memset(vis, false, sizeof(vis));		//初始化
		n = read(), m = read();
		for (reg int i = 1; i <= m; ++i)
		{
			static int x, y, w;
			x = read(), y = read(), w = read();
			Add_Edge(x - 1, y, w); //差分约束系统
			Add_Edge(y, x - 1, -w); //差分约束系统
		}
		flag = false;
		for (reg int i = 0; i <= n; ++i)
			if (!f[i])
				spfa(i);			   //从每一个顶点开始寻找负环
		puts(flag ? "false" : "true"); //输出答案
	}
	return 0;
}

矩阵 matrix

时空限制:\( 2 \texttt {s} , 256 \texttt {MiB} \)。

题目描述

有一个 \( n \times m \) 的矩阵,初始每个格子的权值都为 \( 0 \),可以对矩阵执行两种操作:

  1. 选择一行,该行每个格子的权值加 \( 1 \) 或减 \( 1 \);
  2. 选择一列,该列每个格子的权值加 \( 1 \) 或减 \( 1 \)。

现在有 \( K \) 个限制,每个限制为一个三元组 \( ( x , y , c ) \),代表格子 \( ( x , y ) \) 权值等于 \( c \)。问是否存在一个操作序列,使得操作完后的矩阵满足所有的限制。如果存在输出 Yes,否则输出 No

数据范围

对于 \( 100 \% \) 的数据,\( 1 \leq n , m , k \leq 10 ^ 3 , k \leq n \times m \)。

题解

设第 \( i \) 行加(减)的值为 \( a _ i \),第 \( j \) 列加(减)的值为 \( b _ j \)。那么对于矩阵中的 \( ( x , y ) \) 对应点的值为 \( c \) 可以表示为 \( a _ x + b _ y = c \),在差分约束系统等价于 \( a _ x + b _ y \leq c \) 和 \( a _ x + b _ y \geq c \),进一步转化为 \( a _ x \leq – b _ y + c \) 和 \( – b _ y \leq a _ x – c \)。

考虑到实际上数值的正负没什么关系,我们令 \( b _ j = – b _ j \) 即可。

套用差分约束系统,再用 \( \texttt {spfa} \) 求解负环即可。

#include <bits/stdc++.h> //万能头文件
using namespace std; //命名空间
#define reg register //寄存器变量
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void) //快读
{
	reg bool f = false;
	reg char ch = getchar();
	reg int res = 0;
	while (ch < '0' || '9' < ch)
		f |= (ch == '-'), ch = getchar();
	while ('0' <= ch && ch <= '9')
		res = 10 * res + ch - '0', ch = getchar();
	return f ? -res : res;
}

const int MAXN = 1e3 + 5;	  //题目给出的数据范围
const int MAXM = 1e3 + 5;	  //题目给出的数据范围
const int MAXK = 1e3 + 5;	  //题目给出的数据范围
const int MAXV = MAXN + MAXM; //图的点数
const int MAXE = MAXK * 2;	  //图的边数
const int inf = 0x3f3f3f3f;	  //正无穷

int n, m, k;
int cnt, head[MAXV], to[MAXE], w[MAXE], Next[MAXE]; //邻接表存图

inline void Add_Edge(reg int u, reg int v, reg int len) //加边函数
{
	Next[++cnt] = head[u];
	to[cnt] = v;
	w[cnt] = len;
	head[u] = cnt;
	return;
}

bool flag;		//是否存在负环
bool vis[MAXV]; //是否在栈中
int f[MAXV];	//最短路

inline void spfa(reg int u) //dfs 版 spfa 求负环
{
	if (flag) //剪枝
		return;
	vis[u] = true;
	for (reg int i = head[u]; i; i = Next[i])
	{
		reg int v = to[i];
		if (f[v] > f[u] + w[i])
		{
			if (vis[v]) //如果在栈中仍能松弛
			{
				flag = true; //找到了负环
				vis[u] = false;
				return;
			}
			f[v] = f[u] + w[i];
			spfa(v); //递归寻找
		}
	}
	vis[u] = false;
	return;
}

int main(void)
{
	reg int T = read(); //多组数据
	while (T--)
	{
		cnt = 0, memset(head, 0, sizeof(head)); //初始化
		n = read(), m = read(), k = read();
		for (reg int i = 1; i <= k; ++i)
		{
			static int x, y, c;
			x = read(), y = read(), c = read();
			Add_Edge(y + n, x, c); //差分约束系统
			Add_Edge(x, y + n, -c); //差分约束系统
		}
		flag = false;
		memset(f, 0x3f, sizeof(f)); //初始化 f 数组
		for (reg int i = 1; i <= n + m; ++i)
			if (f[i] == inf)
				spfa(i);		   //从每个节点开始寻找负环
		puts(flag ? "No" : "Yes"); //输出结果
	}
	return 0;
}

魔杖 magic

时空限制:\( 1 \texttt {s} , 128 \texttt {MiB} \)。

题目描述

有一个英雄,初始生命值是 \( \text {hp} \)(生命值无上限),在接下来的 \( n \) 秒内,每秒会受到一次伤害,第 \( i \) 秒受到的伤害值为 \( a _ i \)。这个英雄有一个道具“魔杖”,魔杖的初始能量为 \( 0 \),每受到一次伤害,积攒一点能量。在英雄受到伤害后,可以立即释放魔棒中的能量,恢复 \( 15 \times \) 能量点数 的生命值,且魔棒的点数清零。释放能量有施法间隔 \( \text {cd} \)(\( \text {cd} \) 是正整数),即相邻的两次释放的时间间隔至少有 \( \text {cd} \) 秒。任何时刻当 \( \text {hp} \leq 0 \) 时视为死亡,问这个英雄存活下来的前提下,\( \text {cd} \) 的值最大可以是多少?

注意,若 \( a _ i \) 为负,受到“伤害”后实际上生命值是增加的,魔棒仍然积攒能量。

数据范围

对于 \( 100 \% \) 的数据,\( n \leq 500 \),\( | a _ i | \leq 10 ^ 3 \)。

题解

如果英雄要不死,那么我们有 \( \forall i \in [ 1 , n ] \),设这次释放能量点数为 \( \text {pos} \),满足
\[ 15 \text {pos} + \text {hp} – \text {sum} _ { i + 1 } \leq 1 \]

考虑到 \( \text {pos} \) 要尽量小,我们有
\[ \text {pos} = \left \lceil \frac { \text {sum} _ { i + 1 } – \text {hp} + 1 } { 15 } \right \rceil \]

二分答案 + 差分约束系统判断即可。

#include <bits/stdc++.h> //万能头文件
using namespace std; //命名空间
#define reg register //寄存器变量
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
	reg bool f = false;
	reg char ch = getchar();
	reg int res = 0;
	while (ch < '0' || '9' < ch)
		f |= (ch == '-'), ch = getchar();
	while ('0' <= ch && ch <= '9')
		res = 10 * res + ch - '0', ch = getchar();
	return f ? -res : res;
}

const int MAXN = 500 + 5;  //题目中的数据范围
const int MAXV = 4e4 + 5;  //图中的点数
const int MAXE = 3 * MAXN; //图中的边数

int n, hp;	   //hp 表示生命值
int sum[MAXN]; //sum 表示 a 的前缀和

inline int up(reg int x, reg int y)
{ //求 x/y 向上取整的值
	if (x % y == 0)
		return x / y;
	else if (x < 0) //x 为负数的情况要特殊考虑
		return x / y;
	else
		return x / y + 1;
}

int cnt, head[MAXV], to[MAXE], w[MAXE], Next[MAXE]; //邻接表存图

inline void Add_Edge(reg int u, reg int v, reg int len)
{ //加边函数
	Next[++cnt] = head[u];
	to[cnt] = v;
	w[cnt] = len;
	head[u] = cnt;
	return;
}

bool inque[MAXV]; //是否在队列中
int dis[MAXV];	  //距离数组

inline bool spfa(void)
{ //bfs 版 spfa
	queue<int> Q;
	for (int i = 0; i <= n; ++i)
	{ //初始化
		dis[i] = 0;
		inque[i] = false;
		Q.push(i);
	}
	reg int cnt = 0;
	while (!Q.empty())
	{
		reg int u = Q.front();
		Q.pop();
		inque[u] = false;
		for (reg int i = head[u]; i; i = Next[i])
		{
			int v = to[i];
			if (dis[v] > dis[u] + w[i])
			{ //松弛
				dis[v] = dis[u] + w[i];
				if (!inque[v])
				{ //入队
					inque[v] = true;
					Q.push(v);
				}
			}
		}
		if (++cnt > 2e5) //如果总的松弛次数很大,那么说明存在负环
			return false;
	}
	return true;
}

inline bool check(reg int mid)
{ //差分约束系统二分答案
	cnt = 0, memset(head, 0, sizeof(head));
	for (reg int i = 1; i <= n; ++i)
	{
		Add_Edge(i, i - 1, 0);
		reg int pos = up(sum[i + 1] - hp + 1, 15);
		if (pos > 0 && i < n)
			Add_Edge(i, pos - 1, -1); //差分约束系统加边
		if (i - mid >= 0)
			Add_Edge(i - mid, i, 1); //差分约束系统加边
	}
	return spfa(); //是否可行
}

int main(void)
{
	n = read(), hp = read();
	for (reg int i = 1; i <= n; ++i)
		sum[i] = sum[i - 1] + read(); //求前缀和
	if (check(n))					  //如果 cd=n 都能存活,说明可以不需要回血或者只回一次血,无上限
		puts("No upper bound.");
	else if (!check(1))
		puts("-1"); //如果随时回血都活不下来,说明必死无疑
	else
	{
		reg int l = 1, r = n, mid; //二分
		while (l + 1 < r)
		{
			mid = (l + r) >> 1;
			if (check(mid))
				l = mid;
			else
				r = mid;
		}
		if (check(r)) //如果答案为 r
			printf("%d\n", r);
		else if (check(l)) //否则为 l
			printf("%d\n", l);
	}
	return 0;
}

构造序列 BZOJ4383

时空限制:\(1\text{s},128\text{MiB}\)。

题目描述

给定一个长度为 \(n\) 的正整数序列 \(a\),每个数都在 \(1\) 到 \(10^9\) 范围内,告诉你其中 \(s\) 个数,并给出 \(m\) 条信息,每条信息包含三个数 \(l,r,k\) 以及接下来 \(k\) 个正整数,表示 \(a_l,a_{l+1},\cdots,a_{r-1},a_r\) 里这 \(k\) 个数中的任意一个都比任意一个剩下的 \(r−l+1−k\) 个数大(严格大于,即没有等号)。请任意构造出一组满足条件的方案,或者判断无解。

数据范围

对于 \(100\%\) 的数据,\(1\leq s\leq n\leq 10^5\),\(1\leq m\leq 2\times 10^5\),\(\sum k\leq 3\times 10^5\)。

题解

线段树优化建图+差分约束系统的裸题,但实际上是用拓扑排序过的。原题是 POI 的一道差分约束系统的裸题。

#include <bits/stdc++.h>
using namespace std;
#define reg register
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{ //快读
	reg bool f = false;
	reg char ch = getchar();
	reg int res = 0;
	while (ch < '0' || '9' < ch)
		f |= (ch == '-'), ch = getchar();
	while ('0' <= ch && ch <= '9')
		res = 10 * res + ch - '0', ch = getchar();
	return f ? -res : res;
}

inline void Err(void)
{ //如果不存在答案,那么输出 NIE 并结束程序
	puts("NIE");
	exit(0);
	return;
}

inline void cMax(reg int &x, reg int y)
{ //求 max 的函数
	if (x < y)
		x = y;
	return;
}

inline void cMin(reg int &x, reg int y)
{ //求 min 的函数
	if (x > y)
		x = y;
	return;
}

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXK = 3e5 + 5;
const int MAXLOG2K = 19 + 1;			 //线段树优化建图
const int MAXV = (MAXN << 2) + MAXN;	 //图的点数
const int MAXE = MAXK * MAXLOG2K + MAXM; //图的边数
const int inf = 1e9;					 //正无穷

int n, s, m;
int inDeg[MAXV], f[MAXV], Min[MAXV];
int cnt, head[MAXV], to[MAXE], w[MAXE], Next[MAXE];

inline void Add_Edge(reg int u, reg int v, reg int len)
{ //加边函数
	Next[++cnt] = head[u];
	to[cnt] = v;
	w[cnt] = len;
	head[u] = cnt;
	++inDeg[v]; //顺便统计入度,拓扑排序用
	return;
}

int tot, id[MAXN]; //id 表示 1~n 对应的线段树节点编号

namespace SegmentTree
{
#define mid (((l) + (r)) >> 1)
	int lson[MAXV], rson[MAXV];
	inline void build(int k, reg int l, reg int r)
	{
		if (l == r)
		{
			id[l] = k;
			cMax(tot, k);
			return;
		}
		lson[k] = ++tot, build(lson[k], l, mid), Add_Edge(k, lson[k], 0);
		rson[k] = ++tot, build(rson[k], mid + 1, r), Add_Edge(k, rson[k], 0);
		return;
	}
	inline void update(reg int k, reg int l, reg int r, reg int L, reg int R, reg int pos)
	{ //加边函数
		if (L <= l && r <= R)
		{
			Add_Edge(pos, k, 1);
			return;
		}
		if (L <= mid)
			update(lson[k], l, mid, L, R, pos);
		if (R > mid)
			update(rson[k], mid + 1, r, L, R, pos);
		return;
	}
#undef mid
} // namespace SegmentTree

bool flag; //是否有环
bool vis[MAXV], ins[MAXV];

inline void dfs(reg int id)
{ //dfs 求环
	vis[id] = ins[id] = true;
	for (reg int i = head[id]; i && flag; i = Next[i])
	{
		reg int v = to[i];
		if (ins[v])
		{
			flag = false;
			return;
		}
		if (!vis[v])
			dfs(v);
	}
	ins[id] = false;
	return;
}

queue<int> Q;
using namespace SegmentTree;

int main(void)
{
	n = read(), s = read(), m = read();
	tot = 1;		//线段树的根节点
	build(1, 1, n); //建树
	for (reg int i = 1; i <= s; ++i)
	{
		static int p, d;
		p = read(), d = read();	   //读入位置和值
		Min[id[p]] = f[id[p]] = d; //记录初始值
	}
	for (reg int i = 1; i <= m; ++i)
	{
		static int l, r, k;
		l = read(), r = read(), k = read();
		reg int ptr = l;
		++tot;
		for (reg int j = 1; j <= k; ++j)
		{
			static int x;
			x = read();
			Add_Edge(id[x], tot, 0);
			if (ptr <= x - 1)
				update(1, 1, n, ptr, x - 1, tot); //线段树优化建图
			ptr = x + 1;
		}
		if (ptr <= r)
			update(1, 1, n, ptr, r, tot);
	}
	for (reg int i = 1; i <= tot; ++i)
		if (!f[i])
			f[i] = inf;
	for (reg int i = 1; i <= tot; ++i)
		if (!vis[i])
		{
			flag = true;
			dfs(i);
			if (!flag) //有环
				Err(); //答案不存在
		}
	for (int i = 1; i <= tot; ++i)
		if (!inDeg[i])
			Q.push(i); //开始拓扑排序
	while (!Q.empty())
	{
		reg int u = Q.front();
		Q.pop();
		for (reg int i = head[u]; i; i = Next[i])
		{
			int v = to[i];
			--inDeg[v];
			if (Min[v] > f[u] - w[i])
				Err();
			cMin(f[v], f[u] - w[i]);
			if (!inDeg[v])
				Q.push(v);
			if (f[v] < 1) //如果答案小于 1,则不符合题目条件
				Err();
		}
	}
	puts("TAK"); //求得答案
	for (reg int i = 1; i <= n; ++i)
		printf("%d%c", f[id[i]], i == n ? '\n' : ' ');
	return 0;
}