图论入门到入土

图论是信息学竞赛中永远不失特色的一种算法集合。最常见也是相对简单的有：最短路，最小生成树，拓扑排序，部分树上的问题。此外还有深造一些的，如网络流，Tarjan 等。

图的结构

一个图由若干个点和连接点的若干个边组成。点的集合记作 $V$，边的集合记作 $E$，后文若无特殊说明，点集大小是 $n$，边集大小是 $m$。

边有不定向和定向两种。都不定向的图叫无向图，都定向的是有向图，有的定向有的不定向的是混合图。一般情况下，混合图和无向图可以转化为有向图的问题求解。无向图上任意两点之间都有连边的是完全图。

无向图中，所有点之间如果所有点互相可达，叫做无向连通图。有向图中若所有点互相可达，叫强连通图；若所有的有向边改为无向边后，原图变为连通图，则称作弱连通图。一般情况下，连通图在无向图上指无向连通图，在有向图上指强连通图。

树是只有 $n-1$ 条边的连通图，一般是无向的，但是可以人为定向，比如根节点到叶子，或叶子到根。

DAG 也就是有向无环图，环的意思就顾名思义就行。

分层图是一类图，一般是有向图。可以把图分成很多层，各层之间只能由一层的点到达另一层的点，不能回来，且不能跨层连边。一般把没有别的点可以来的那一层叫做第一层，由第一层来到第二层，到第三层……分层图的分层标准一般不是很严格，题目也不会直接丢出来一个分层图，而是要自己建模建分层图。

二分图是一种可以分成两部分的图，满足没有边连接两个同一部分的点。竞赛图是将无向完全图中的每个边定向之后得到的图。

平面图是一种可以画在平面上的图，其中除了每个点之外，所有边都没有交点的图。例如下面两个就是平面图，其中第一个可以画成第二个的形式：

基础

因为过于基础，基本都是简单带过，不过也会有例题。

图的存储

常见的存图方法有：边目录，邻接矩阵，邻接表，链式前向星。比较常用的三个是边目录、邻接矩阵、链式前向星。

边目录主要出现在最小生成树的算法中。存储方法是直接开一个结构体，记录一条边的起点终点边权等信息。当你对边有优先级要求的时候，一般会先用边目录存下来，然后按照某个优先规则排序。

邻接矩阵常用在点数较小的题目里面，方法是开一个二维数组表示边 $(i,j)$ 的权值或之类信息。在 floyd 最短路里比较常见。

链式前向星是最常用的存储方法，我一般写成这样：

struct graph{
	int hd[max_n],nx[max_n],to[max_n],ct;
	graph(){ct=1;} // 初始化为 1，这样 i^1 就是 i 的反边
	
	inline void clear(){
		ct=1,
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v;
	}
}e;

值得注意的是，链式前向星存储后，遍历的时候（i=hd[u];i;i=nx[i]）是按照加边顺序的逆序遍历的。在初赛题目中可能会用到。

最短路

常见的最短路算法有（简写） BF，Dij，SPFA，Floyd，Jon。有的名字比较长我就用了简写。Jon 算法适用于预处理之后多次询问较快地求最短路，Dij 非常常用，是没有负边的时候求最短路，基于贪心，复杂度是 $(n+m)\log(n+m)$，不用 Dij 的时候一般是 SPFA，最慢是 $nm$ 的，但可以处理负权，Floyd 用到了动态规划的思想，可以经过改造后做很多图论。

例题：在一张 $n$ 个点的带权完全图上，依次删掉 $x_1,x_2,\cdots,x_n$ 这些点，每次删掉一个点前，输出当前图存在的点两两之间最短路长度之和。$n\leqslant 500$。

简单考虑一下：如果我即将删掉的点是 $x$，其中有最短路经过了这个点，那么删掉这个点之后，我就必须要找一条新的最短路。改变最短路的点最多可能有 $n$ 个，每删除一个点就跑一次全源最短路，因为是完全图，Floyd 比 Dij 快，但复杂度也是 $n^4$ 的。因为最短路算法的复杂度钉死在这里，而又一定要每次删除都要看一遍，所以无法有任何优化。

根据正难则反的原则，如果考虑的是在一个空图上不断加一些点，原来的最短路没有经过这个点，现在需要做的就是判断这个点是不是可以得出一个新最短路。考虑到别的点的最短路和这个点无关，也就是说只需要考虑这个点为中转点怎么走了。

Floyd 的 $k$ 那一重循环消掉了。总的复杂度是 $n^3$，可过。

Tarjan

Tarjan 是一位叫做 Tarjan 的神仙爷爷发明的算法。具体的就是在跑 dfs 的时候，记录每个点每跑到的顺序 $dfn$ 和可以回溯到的最小 $dfn$：$low$。围绕 $dfn$ 和 $low$ 展开各种判定。常见的有：有向图强连通分量，无向图边双连通分量和点双连通分量，等等。

• 强连通分量：有向图的极大的子图，这里面所有的点互相可达。
• 边双连通分量：无向图的极大的子图，去掉任何一条边都不影响连通性。
• 点双连通分量：无向图的极大的子图，去掉任何一个点都不影响连通性。
• 割点：去掉后原图不再连通的点。
• 割边、桥：去掉后原图不再连通的边。

例题：给定一个 $n$ 点 $m$ 边的无向连通图，求加上一条边后，最少会有多少个桥。$n,m\leqslant 10^5$

枚举去掉的边跑显然是 $n^2$ 的，不可取。如果先 Tarjan 缩点之后，就会得到一个树，显然树上每一条边都是一个桥。添加一条边之后可以得到一个环，环上的所有本来的桥都不是桥了。

因此要让环最大，把边加在树的直径的两头即可，去掉的桥数就是数的直径长度。

最小生成树和最短路径树

最小生成树问题，就是在原图上选择 $n-1$ 条边构成一个 $n$ 个点的树，使得选择的边的边权和最小。

有两种常用的算法：Prim 和 Kruskal。一般不用 Prim，Kruskal 的出现率是 $99.99\%$。主体的思想是贪心，将图按照边权排序后，每次选择最小的，如果选择的边加进去有环（并查集判断）就跳过。

最短路径树问题，就是在原图上选择 $n-1$ 条边构成一个 $n$ 个点的树（给定了根节点），使得根节点到每个点的距离等于原图上这个点到每个点的最短路。

dijkstra 算法进行的时候，把每个点从哪个点更新过来的记录下来，也就是每个点的前驱。前驱关系显然不会构成环，又因为除了源点都有前驱，也就是 $n-1$ 组关系。所以一定能构成树，这就是最短路径树。

拓扑排序

对于一个 DAG，假设我要在这个上面跑 DP，我希望没有后效性（也就是来到一个点之前它的前面的点已经跑完了），这时就需要对图上的点的遍历方法进行一个排序。这种排序就是拓扑排序。

因为是一个 DAG，所以一定存在至少一个没有入度的点和至少一个没有出度的点。那么第一个进行的一定是没有入度的那个点。然后如果我把所有没有入度的点删掉，那么一定会产生新的没有入度的点……按照被删除的顺序从早到晚，就是一个合理的拓扑序。

简单理解一下原因：对于这个点，我期望让它在通往它的所有有向路径上的其他点都遍历完之后才遍历到这个点，而如果存在一条路径没有遍历完，这个点的入度也就不会变成 $0$，因此成立。

例题：对于一个 $4\times 4$ 的屏幕，按顺序从左到右从上到下放上了 $9$ 个 $2\times 2$ 的窗口，并以一定程度覆盖了上去。给出最后屏幕的窗口，判断是否不可能出现。

考虑到以覆盖关系进行判定。本来这个位置可以放 $1,2,4,5$ 窗口，但是现在显示的是 $2$ 窗口，说明 $2$ 把 $1,4,5$ 窗口都覆盖了。从覆盖到没覆盖建边。最后如果出现环就不可以。

至于如何判断出现环，可以选择进行拓扑排序，如果队列的点都删完了，还有的点没有删掉，说明这些点组成了环。

进阶（当前进度）

差分约束

差分约束问题就是，给定若干个形如 $x_i\leqslant x_j+c_k$ （$c$ 是常数）的关系式，判断是否有解，或求出一组可行的解。

不妨将其作为一个关系，关系显然是单向的，以此建立一个有向图。具体而言，对于关系 $x_i\leqslant x_j+c_k$，从 $j$ 向 $i$ 链接一条权值为 $c_k$ 的有向边。我们发现这个关系式和求最短路时的不等式“三角形不等式”（$dis_i\leqslant dis_j+w$）相似，所以用最短路的方法来求解无疑是最好的。

每个点都开始跑一遍有点麻烦，可以建一个超级源点 $0$ 号点，向每一个点连出去一个长度为 $0$ 的边，这样只要从 $0$ 开始跑就行了。如果存在负环，则没有最短路，也就是无解。否则一组可行解就是 $0$ 号点到每个点的最短路。

显然不可以用 dij，我们可以用码量小的 BF 或期望更快的 SPFA。

#include<bits/stdc++.h>
using namespace std;
const int max_n=10004;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
	int ct,nx[max_n],to[max_n],ln[max_n],hd[max_n];
	graph(){ct=1;}

	inline void add(int u,int v,int w){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
	}
}e;

int n,m,dis[max_n],cnt[max_n];

bool in[max_n];
queue<int> q;

inline bool SPFA(int st){ // 最短路
	memset(dis,0x3f,sizeof(dis));
	dis[st]=0;
	q.push(st);
	in[st]=1,++cnt[st];
	while(!q.empty()){
		int u=q.front();q.pop();
		in[u]=0;
		for(register int i=e.hd[u];i;i=e.nx[i]){
			int v=e.to[i],w=e.ln[i];
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				if(in[v]) continue;
				q.push(v);
				in[v]=1,++cnt[v];
				if(cnt[v]>n+1) // 一个点被更新n+1次，有负环
					return 0;
			}
		}
	}
	return 1;
}

signed main(){
	n=read(),m=read();
	for(register int i=1;i<=n;++i)
		e.add(n+1,i,0);
	for(register int i=1;i<=m;++i){
		int a=read(),b=read(),c=read();
		e.add(b,a,c);
	}
	if(SPFA(n+1)) // 有解，解就是dis
		for(register int i=1;i<=n;++i)
			write(dis[i]),putchar(' ');
	else
		puts("NO");
	return 0;
}
// 洛谷模板题代码

差分约束的题目也不一定只是 $x_i\leqslant x_j+c_k$ 这样的形式。常见变式有：

• $x_j\leqslant x_i+c_k$，两边都乘 $-1$，不等号（有向边）方向反过来。
• $x_i=x_j+c_k$，拆成 $x_i\leqslant x_j+c_k$ 和 $x_i\geqslant x_j+c_k$ 两个。

分层图最短路

分层图最短路一般的模型是：给定一个图，有 $k$ 次机会将一个边的权修改为 $0$，求一个点到另一个点的最短路。

考虑建立 $k+1$ 层，为了方便从 $0$ 开始标层号，第 $i$ 层表示了使用了 $i$ 次机会。每层都是 $n$ 个点，每一层内部的图都是原图。随后，原图上的每一条边，记为 $u$ 连向 $v$，建立一条跨层边，从 $u$ 连向下一层图的 $v$，边权为 $0$，表示走这个边的时候使用了一次机会。

如果题目所求是刚好用 $k$ 次机会，则答案就是第 $0$ 层的起始点到第 $k$ 层的目标点最短路。如果是 $k$ 次以内，则答案是第 $0$ 层的起始点到每一层的目标点的最小值。

#include<bits/stdc++.h>
using namespace std;
const int max_n=2000006,max_m=3000006;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
struct graph{
	int ct,hd[max_n],nx[max_m*2],to[max_m*2],ln[max_m*2];
	graph(){ct=1;}

	inline void add(int u,int v,int w){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
	}
}e;

int n,m,k,s,t;

#define P pair<int,int>
#define S second
#define mp(x,y) make_pair(x,y)

int dis[max_n];
bool vis[max_n];
priority_queue< P, vector< P >, greater< P > > q;

inline int dij(int st){ // 普通的 dij
	memset(dis,0x3f,sizeof(dis));
	dis[st]=0;
	q.push(mp(0,st));
	while(!q.empty()){
		int u=q.top().S;q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(register int i=e.hd[u];i;i=e.nx[i]){
			int v=e.to[i];
			if(dis[v]>dis[u]+e.ln[i]){
				dis[v]=dis[u]+e.ln[i];
				q.push(mp(dis[v],v));
			}
		}
	} // 最多 k 次机会，求 min
	int res=dis[t];
	for(register int i=1;i<=k;++i)
		res=min(res,dis[t+i*n]);
	return res;
}
#undef P
#undef S
#undef mp

signed main(){ // 点下标 0 开始
	n=read(),m=read(),k=read(),s=read(),t=read();
	for(register int i=1;i<=m;++i){
		int u=read(),v=read(),w=read();
		e.add(u,v,w),
		e.add(v,u,w);
		for(register int j=1;j<=k;++j){
			e.add(u+n*(j-1),v+n*j,0),
			e.add(v+n*(j-1),u+n*j,0);
			e.add(u+n*j,v+n*j,w),
			e.add(v+n*j,u+n*j,w);
		} // 每层内部复刻+跨层边
	}
	write(dij(s));
	return 0;
}
// 洛谷模板题

分层图的思想十分常用，这也代表分层图思想不一定仅限于做分层图。例如不是分层图最短路的最短路也经常用到分层图思想。例如：

例题：一个无向图，每个边有长度和标记，标记是 $1,2,3,4$ 中的一个，从 $1$ 走到 $n$ 号点，要求走的边按顺序一定是 $123412341234\cdots 4$，一定要以 $1$ 开头 $4$ 结尾。在此基础上，走最短路径。求最短路长度和走过的 $1234$ 循环次数。$n,m\leqslant 1005$。

考虑到用分层图的思想，把状态拆开。一个点拆成四个点，表示目前处在 $1,12,123,1234$ 四种状态。对于一条边根据状态决定从拆出的哪个点连到哪个点。

显然这样做第四层的点会连回第一层，但是运用了分层图的思想。考虑到第一个点出发的时候什么也没有，只能走 $1$ 标记边，不妨新建一个虚拟源点，把 $1$ 的第四个状态连出去的点都连一遍。最后的答案就是虚拟源点走到 $n$ 号点的第四个状态点的最短路。

k 度最小生成树

k 度最小生成树的模板，就是给定一个无向图，在里面做一个最小生成树，但是要求根节点的度数不超过或恰好等于 $k$。

对于恰好等于 $k$ 的问题，常用 wqs 二分解决，并不属于图论的算法，在此直接略过；无论是恰好等于 $k$ 还是小于等于 $k$，都可以用一下算法：

• 考虑先删去根和其连边，将剩下的点构造出若干个最小生成森林，设分成 $s$ 个连通块。
• 若 $s>k$ 则无解。
• 对于每个树找出一条连向根节点的最小的边，加上去，此时根的度恰好为 $s$。
• 预处理根节点到所有点路径的最大边权值，设为 $mx_i$。
• 枚举根节点的出边所到的点，找到一个点使得边权减去 $mx_v$ 最大。
• 若最大是负数，立刻退出循环，否则将这个边加入（删除原树 $mx$ 对应的边）。
• 重新算 $mx_i$，不断循环。

模板代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=1003;
struct graph{
	int ct,nx[max_n*2],to[max_n*2],ln[max_n*2],hd[max_n];
	graph(){ct=1;}

	inline void clear(){
		ct=1;
		memset(hd,0,sizeof(hd));
	}
	inline void add(int u,int v,int w){
		nx[++ct]=hd[u],hd[u]=ct,to[ct]=v,ln[ct]=w;
	}
}e,t;
struct edge{
	int u,v,w,id;
	edge(){u=v=w=id=0;}

	inline void init(int a,int b,int c,int d){
		u=a,v=b,w=c,id=d;
	}
}q[max_n];

inline bool cmp(edge a,edge b){
	return a.w<b.w;
}

struct unionfind{ // 并查集，最小生成树
	int fa[max_n],sz[max_n];

	inline void init(int n){
		for(register int i=1;i<=n;++i)
			fa[i]=i,
			sz[i]=1;
	}
	inline int find(int x){
		if(fa[x]==x) return x;
		return fa[x]=find(fa[x]);
	}
	inline void merge(int x,int y){
		if(sz[x]>sz[y]) swap(x,y);
		fa[x]=y,
		sz[y]+=sz[x];
	}
}uf;

int n,m,tot,col[max_n];

inline void dfs1(int u,int tp){
	col[u]=tp;
	for(register int i=e.hd[u];i;i=e.nx[i]){
		int v=e.to[i];
		if(col[v] || v==1) continue;
		dfs1(v,tp);
	}
}

int dis[max_n*2],wh[max_n*2];
bool del[max_n*2];

inline void dfs2(int u,int fa){ // 找最大边
	for(register int i=t.hd[u];i;i=t.nx[i]){
		int v=t.to[i];
		if(del[i] || v==fa)
			continue;
		if(t.ln[i]>dis[v]){
			dis[v]=t.ln[i],
			wh[v]=i; // wh 是从哪里来的
		}
		if(dis[u]>dis[v]){
			dis[v]=dis[u],
			wh[v]=wh[u];
		}
		dfs2(v,u);
	}
}

bool in[max_n];
int cdis[max_n],gdot[max_n],fr[max_n];

inline int krul(){ // 最小生成森林
	uf.init(n);
	sort(q+1,q+1+m,cmp);
	memset(cdis,0x3f,sizeof(cdis));
	int res=0;

	for(register int i=1;i<=m;++i){
		int u=q[i].u,v=q[i].v,x=q[i].u,y=q[i].v;

		if(col[u]!=col[v] || u==1 || v==1)
			continue;
		u=uf.find(u),v=uf.find(v);
		if(u==v)
			continue;
		uf.merge(u,v);
		res+=q[i].w;
		t.add(x,y,q[i].w), // t 是树，e 是原图
		t.add(y,x,q[i].w);
		in[q[i].id]=in[q[i].id^1]=1;
	}
	for(register int i=e.hd[1];i;i=e.nx[i]){
		int v=e.to[i],c=col[v],w=e.ln[i];
		if(cdis[c]>w){ // 1 到每个连通块
			cdis[c]=w,
			gdot[c]=v,
			fr[c]=i;
		}
	}
	for(register int i=1;i<=tot;++i){
		res+=cdis[i];
		t.add(1,gdot[i],cdis[i]),
		t.add(gdot[i],1,cdis[i]);
		in[fr[i]]=in[fr[i]^1]=1;
	}
	return res;
}

int ans;
map<string,int> mp;
string tmp1,tmp2;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>m;n=1,tot=0;
		e.clear(),t.clear();
		memset(col,0,sizeof(col)),
		memset(del,0,sizeof(del)),
		memset(dis,0,sizeof(dis)),
		memset(in,0,sizeof(in));
		mp.clear(),mp["Park"]=1;

		for(register int i=1;i<=m;++i){
			int w,u,v;

			cin>>tmp1>>tmp2>>w;
			if(!mp[tmp1]) mp[tmp1]=++n;
			if(!mp[tmp2]) mp[tmp2]=++n;
			u=mp[tmp1],v=mp[tmp2];
			e.add(u,v,w),
			e.add(v,u,w);
			q[i].init(u,v,w,e.ct);
		}
		int k;cin>>k;

		for(register int i=2;i<=n;++i)
			if(!col[i])
				dfs1(i,++tot);
		k-=tot;
		ans=krul();
		dfs2(1,1);

		while(k--){ // 最多循环 k 次
			int tmp=-1,j=0;
			for(register int i=e.hd[1];i;i=e.nx[i]){
				int v=e.to[i],w=dis[v],z=e.ln[i];
				if(in[i])
					continue;
				if(w-z>tmp){
					tmp=w-z,
					j=i;
				}
			}
			if(tmp<=0 || !j)
				break;
			ans-=tmp;int v=e.to[j];
			del[wh[v]]=del[wh[v]^1]=1; // 删除本来的边
			in[j]=in[j^1]=1;
			t.add(1,v,e.ln[j]), // 加上新边
			t.add(v,1,e.ln[j]);
			memset(dis,0,sizeof(dis));
			dfs2(1,1); // 重新求出 mx
		}
		cout<<"Total miles driven: "<<ans<<"\n";
		if(T) cout<<"\n";
	}
	return 0;
}

2-SAT

我的博客。

二分图霍尔定理

霍尔定理也写成 Hall 定理，定理的内容如下：

若二分图中存在一个点集 $X$，$X$ 内部不存在任何边，设 $Y$ 为 $X$ 在原图点集的补集。（也就是 $X$，$Y$ 是二分图的两边）。则存在一个匹配使得 $X$ 的点都可以被匹配的充要条件是：$X$ 内的任意 $k$ 个点至少与 $Y$ 内的 $k$ 个点有边连接。

霍尔定理是匈牙利算法的基础。至于匈牙利算法，相比没有人不知道吧。

有 $1$ 到 $n$ 号的鞋子各 $k$ 双。已知 $x$ 号脚的人可以穿 $x$ 到 $x+d$ 的鞋子。有 $m$ 次操作，每次操作包含两个数 $r_i,x_i$，代表来了 $x_i$ 个 $r_i$ 号脚的人。其中 $x_i$ 为负，则代表走了这么多的人。对于每次操作，输出鞋子是否足够。

考虑到把原题目看成人和鞋子进行匹配。用霍尔定理判断是否存在完美匹配。如果不满足霍尔定理，一定出现在相同大小的脚的人都已经选到鞋子了，所以需要判断人是否被全部选择。

考虑到选取人的脚的号码不一定是连续的，不能直接用连续的区间来记录人，对于不连续的部分，我们拆成连续求解。只需要判断每个连续的人形成的段是否满足 Hall 定理。

设选择的人的脚号属于 $[l,r]$，$a_i$ 表示型号为 $i$ 的人有多少个。所以有：$\sum_l^r a_i\leqslant k\times(r-l+1+d)$。所以有：

$\sum_l^r (a_i-k)\leqslant d\times k$

线段树维护最小区建和即可。本题的代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=500005;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}

int n,m,k,d,r;

#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

struct segment_tree{ // 连续区间和
	int L[max_n*4],R[max_n*4];
	int sm[max_n*4],lf[max_n*4],rt[max_n*4],mx[max_n*4];

	inline void pushup(int x){
		sm[x]=sm[ls(x)]+sm[rs(x)],
		mx[x]=max(mx[ls(x)],mx[rs(x)]);
		lf[x]=max(lf[ls(x)],sm[ls(x)]+lf[rs(x)]),
		rt[x]=max(rt[rs(x)],sm[rs(x)]+rt[ls(x)]);
		mx[x]=max(mx[x],lf[rs(x)]+rt[ls(x)]);
	}
	inline void build(int x,int l,int r){
		L[x]=l,R[x]=r;
		if(l==r){
			mx[x]=sm[x]=lf[x]=rt[x]=-k;
			return;
		}
		int mid=(l+r)>>1;
		build(ls(x),l,mid),
		build(rs(x),mid+1,r);
		pushup(x);
	}
	inline void add(int x,int pos,int val){
		if(L[x]==pos && R[x]==pos){
			mx[x]+=val,sm[x]+=val;
			lf[x]+=val,rt[x]+=val;
			return;
		}
		int mid=(L[x]+R[x])>>1;
		if(pos<=mid) add(ls(x),pos,val);
		else add(rs(x),pos,val);
		pushup(x);
	}
}seg;

signed main(){
	n=read(),m=read(),k=read(),d=k*read();
	seg.build(1,1,n);
	for(register int i=1;i<=m;++i){
		int pos=read(),val=read();
		seg.add(1,pos,val);
		puts(seg.mx[1]<=d?"TAK":"NIE");
	}
	return 0;
}