自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 21:49:03，当前版本为作者最后更新于2021-12-19 22:29:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

*P3443 [POI2006]LIS-The Postman

POI 合集。

每条路径片段的限制形如在片段中出现的相邻两条边必须先后走，因为一条边有向边仅出现一次。

所有限制形成一条边先后走的关系的链（有点像 CSP2019 T4 树上的数），将这条链缩成从起点到终点的一条边，然后跑欧拉回路即可，最后输出这条边时要再展开成链，因此要记录每条链上的结点顺序。

若限制关系出现环或分叉则无解，这可以通过并查集或链表维护。时间复杂度线性对数或线性。

const int N = 5e5 + 5;
int n, m, q, node, cur[N], fa[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
int u[N], v[N], in[N], deg[N];
int vis[N], vert, top, stc[N];
vpii e[N], E[N];
vint G[N], pa[N];
gp_hash_table <ll, int> mp, buc;
ll hsh(int a, int b) {return 1ll * a * N + b;}

void dfs(int id) {
	if(!vis[id]) vert++, vis[id] = 1;
	for(int &i = cur[id]; i < E[id].size(); ) {
		pii it = E[id][i++]; dfs(it.fi);
		if(it.se > n) stc[++top] = it.se;
	} stc[++top] = id;
}

bool Med;
int main(){
	cin >> n >> m, node = m;
	for(int i = 1; i <= m; i++) {
		u[i] = read(), e[u[i]].pb(v[i] = read(), i);
		mp[hsh(u[i], v[i])] = fa[i] = i;
	} q = read();
	for(int i = 1; i <= q; i++) {
		static int p[N]; int k = read();
		for(int j = 1; j <= k; j++) p[j] = read();
		for(int j = 1; j + 1 < k; j++) {
			int u = mp[hsh(p[j], p[j + 1])], v = mp[hsh(p[j + 1], p[j + 2])];
			if(!u || !v) puts("NIE"), exit(0);
			if(buc.find(hsh(u, v)) != buc.end()) continue;
			if(G[u].size() || deg[v] || find(u) == find(v)) puts("NIE"), exit(0);
			buc[hsh(u, v)] = 1, G[u].pb(v), deg[v]++, fa[fa[u]] = fa[v];
		}
	} for(int i = 1; i <= m; i++)
		if(G[i].size() && !deg[i]) {
			int cur = u[i], p = i, x = ++node;
			while(1) {
				cur = v[p];
				if(!G[p].size()) break;
				else pa[x].pb(v[p]), p = G[p][0];
			} E[u[i]].pb(cur, x);
		}
	for(int i = 1; i <= n; i++) for(pii it : e[i])
		if(!G[it.se].size() && !deg[it.se]) E[i].pb(it);
	for(int i = 1; i <= n; i++) for(pii it : E[i]) in[it.fi]++;
	for(int i = 1; i <= n; i++)
		if(E[i].size() != in[i]) puts("NIE"), exit(0);
		else if(!E[i].size()) vert++;
	dfs(1);
	if(vert != n) puts("NIE"), exit(0);
	puts("TAK");
	while(top) {
		if(stc[top] > n) for(int it : pa[stc[top]]) cout << it << "\n";
		else cout << stc[top] << "\n"; top--;
	} return  0;
}