BZOJ 4727 Turysta

发表于 | 更新于

Link

题意是每个点至多经过一次，“没有重复经过同一个点两次以上的简单路径”感觉怪怪的。

Solution

这是一张竞赛图 这样的问题肯定是要缩点DP的，问题是如何构造路径。

竞赛图

两点之间有且只有一条有向边 结论来了：强连通的竞赛图一定有蛤密顿回路

首先要证明任意竞赛图都有蛤密顿路径，因为需要用来构造蛤密顿回路 n==2n==2，结论成立 设n=kn=k，结论成立，需要证明在n=k+1n=k+1时结论也成立 对于原有的路径P=V1V2V3...VkP=V_1V_2V_3...V_k 如果存在<Vi,Vk+1>,<Vk+1,Vi+1>< V_i,V_{k+1} >,< V_{k+1},V_{i+1} >，那么存在。 否则， 如果有<Vk+1,V1>< V_{k+1},V_1 >或者<Vk,Vk+1>< V_k,V_{k+1} >，那么存在。 假设上面的情况都不符合，那么有<V1,Vk+1>< V_1,V_{k+1} >，<Vk+1,Vk>< V_{k+1},V_k >，中间的点无论怎么连边都会有一个转折点，就符合了第一种情况，所以假设不成立。 所以结论成立。

关于一些扩展内容

有了蛤密顿路，来构造蛤密顿回路，主要思路是扩展已有的环 对于蛤密顿路径PP的前kk个点组成的环CkC_k，现在要加入Vk+1V_{k+1}得到Ck+1C_{k+1} (实现的时候把环拆开，维护断点，设为首尾)

  1. 存在<Vk+1,V1>< V_{k+1},V_1 >，直接加入，把环尾设置为Vk+1V_{k+1}
  2. 存在<Vi,Vk+1>,<Vk+1,Vi+1>< V_i,V_{k+1} >,< V_{k+1},V_{i+1} >，先把环首尾接起来，然后在Vi+1V_{i+1}处把环拆开，把VkV_k接在ViV_i上，把首尾设置为Vi+1,Vk+1V_{i+1},V_{k+1}
  3. 以上都不存在，那么肯定存在Vh,h>k+1V_h,h> k+1有<Vh,Vs>,s≤k< V_h,V_s >,s\le k，否则就不是强连通图了。那就找到这个点，同样先把环接起来，从VsV_s处拆环，把Vs−1V_{s-1}与Vk+1V_{k+1}连接，把环的首尾设置为Vs,VhV_s,V_h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int ce=he;Add(he,pts);
while(ce!=ta) {
    int cur=hsuc[ce];
    if(map[cur][he]) {
        Add(cur,pts);
        ce=cur;
    }
    else {
        bool found=0;
        for(int u=he;u!=ce;u=hsuc[u])
            if(map[u][cur] && map[cur][hsuc[u]]) {
                hsuc[ce]=he;
                he=hsuc[u];
                hsuc[u]=cur;
                ce=cur;
                found=1;
                break;
            }

        if(!found) {
            int boss,brp,brpred=0;
            for(int u=cur;assert(u),1;u=hsuc[u]) 
                if(reach[u] && !ud[u]) {
                    boss=u;
                    break;
                }
            for(int u=he;assert(u!=cur),1;brpred=u,u=hsuc[u]) 
                if(map[boss][u]) {
                    brp=u;
                    break;
                }
            brpred=brpred==0?ce:brpred;
            hsuc[ce]=he;
            hsuc[brpred]=cur;
            he=brp;
            ce=boss;
            for(int u=cur;u!=hsuc[boss];u=hsuc[u])
                Add(u,pts);

        }
    }
}
hsuc[ta]=he;

这样先SCC，然后对于每个SCC都构造蛤密顿回路。 缩点之后，SCC之间的连边也一定是竞赛图的形式，如果有两条有向边，就成了一个SCC。也就是说，如果对于两个SCCS1,S2S_1,S_2，存在边<S1,S2>< S_1,S_2 >，那就一定不存在<S2,S1>< S_2,S_1>，且一定有∀u∈S1,v∈S2\forall u\in S_1,v\in S_2，存在边<u,v>< u,v >。 然后缩点图上进行DP，最后构造答案输出即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
//Code by Lucida
#include<bits/stdtr1c++.h>
typedef long long int64;
namespace IO
{
	template <class T> inline void get(T &x) {
		static bool f;static char ch;
		for(f=0,ch=0;ch<'0' || '9'<ch;ch=getchar()) f|=ch=='-';
		for(x=0;'0'<=ch && ch<='9';ch=getchar()) (x*=10)+=ch-'0';
		x=f?-x:x;
	}
	template <> inline void get<char>(char &x) {
		while(x=getchar(),((x<'0' || '9'<x) && (x<'a' || 'z'<x) && (x<'A' || 'Z'<x)));
	}
	template <> inline void get<char*>(char *&x) {
		char *cp=x;
		while(*cp++=getchar(),(*cp!=' ' && *cp!='\r' && *cp!='\n' && *cp!=EOF));
		*--cp=0;
	}

	template <class T> inline void put(T x) {
		if(!x)
			putchar('0');
		else {
			if(x<0) {
				putchar('-');
				x=-x;
			}
			static char stack[30]={0};
			char *top=stack;
			for(;x;x/=10) *++top=x%10+'0';
			while(*top) putchar(*top--);
		}
	}
	template <> inline void put<char>(char x) {
		putchar(x);
	}
	template <> inline void put<char*>(char* x) {
		while(*x)
			putchar(*x++);
	}
}

template <class T> inline bool chkmx(T &a,const T &b) {
	return a<b?a=b,1:0;
}
template <class T> inline bool chkmn(T &a,const T &b) {
	return a>b?a=b,1:0;
}

using std::swap;
using std::max;
using std::min;
using IO::get;
using IO::put;


using std::vector;

const int MAXN=2e3+11;
int n,scnt,sn[MAXN],hsuc[MAXN],f[MAXN],dsuc[MAXN];
vector<int> scc[MAXN];
bool map[MAXN][MAXN],cot[MAXN][MAXN];
namespace _Tarjan_ {
	int dc,dfn[MAXN],low[MAXN],stack[MAXN],top;
	bool instack[MAXN];
	void DFS(int pos,int fa) {
		instack[stack[++top]=pos]=1;
		dfn[pos]=low[pos]=++dc;
		for(int u=1;u<=n;++u)
			if(map[pos][u] && u!=fa) {
				if(!dfn[u]) {
					DFS(u,pos);
					chkmn(low[pos],low[u]);
				} else if(instack[u])
					chkmn(low[pos],dfn[u]);
			}
		if(dfn[pos]==low[pos]) {
			++scnt;
			while(stack[top+1]!=pos) {
				int u=stack[top];
				sn[u]=scnt;
				instack[u]=0;
				scc[scnt].push_back(u);
				top--;
			}
		}
	}
	void Tarjan() {
		for(int i=1;i<=n;++i)
			if(!dfn[i])
				DFS(i,0);
	}
}using _Tarjan_::Tarjan;

namespace _Hamilton_ {
	bool ud[MAXN],reach[MAXN];
	void Add(int pos,vector<int> &pts) {
		ud[pos]=1;
		for(unsigned int i=0;i<pts.size();++i)
			reach[pts[i]]|=map[pts[i]][pos];
	}
	void Hamilton(int css) {
		vector<int> &pts=scc[css];
		int he=pts[0],ta=pts[0],sz=pts.size();
		//构造哈密顿路
		for(int i=1;i<=sz-1;++i) {
			int cur=pts[i];
			if(map[cur][he]) {
				hsuc[cur]=he;
				he=cur;
			} else if(map[ta][cur]) {
				hsuc[ta]=cur;
				ta=cur;
			} else {
				for(int u=he;assert(u!=ta),1;u=hsuc[u]) {
					if(map[u][cur] && map[cur][hsuc[u]]) {
						hsuc[cur]=hsuc[u];
						hsuc[u]=cur;
						break;
					}
				}
			}
		}
		//变成哈密顿回路
		int ce=he;Add(he,pts);
		while(ce!=ta) {
			int cur=hsuc[ce];
			if(map[cur][he]) {
				Add(cur,pts);
				ce=cur;
			}
			else {
				bool found=0;
				for(int u=he;u!=ce;u=hsuc[u])
					if(map[u][cur] && map[cur][hsuc[u]]) {
						hsuc[ce]=he;
						he=hsuc[u];
						hsuc[u]=cur;
						ce=cur;
						found=1;
						break;
					}

				if(!found) {
					int boss,brp,brpred=0;
					for(int u=cur;assert(u),1;u=hsuc[u]) 
						if(reach[u] && !ud[u]) {
							boss=u;
							break;
						}
					for(int u=he;assert(u!=cur),1;brpred=u,u=hsuc[u]) 
						if(map[boss][u]) {
							brp=u;
							break;
					  	}
					brpred=brpred==0?ce:brpred;
					hsuc[ce]=he;
					hsuc[brpred]=cur;
					he=brp;
					ce=boss;
					for(int u=cur;u!=hsuc[boss];u=hsuc[u])
						Add(u,pts);
					
				}
			}
		}
		hsuc[ta]=he;
	}
}using _Hamilton_::Hamilton;
void Walk(int pos,int *s,int &cnt) {
	s[++cnt]=pos;
	for(int u=hsuc[pos];u!=pos;u=hsuc[u])
		s[++cnt]=u;
	if(dsuc[sn[pos]]) 
		Walk(scc[dsuc[sn[pos]]][0],s,cnt);
}
int DP(int css) {
	if(f[css]) return f[css];
	for(int c=1;c<=scnt;++c) 
		if(cot[css][c] && chkmx(f[css],DP(c))) 
			dsuc[css]=c;
	return f[css]+=scc[css].size();
}
int main() {
//	freopen("input","r",stdin);
	get(n);
	for(int i=2;i<=n;++i)
		for(int j=1;j<=i-1;++j) {
			int b;get(b);
			map[j][i]=b;
			map[i][j]=b^1;
		}
	Tarjan();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			cot[sn[i]][sn[j]]|=(sn[i]!=sn[j] && map[i][j]);
	for(int i=1;i<=scnt;++i) {
		f[i]=DP(i);
		Hamilton(i);
	}
	static int s[MAXN];
	
	for(int i=1;i<=n;++i) {
		int Ans=f[sn[i]];
		put(Ans),put(' ');
		int cnt=0;
		Walk(i,s,cnt);
		for(int j=1;j<=cnt;++j) {
			put(s[j]),put(j==cnt?'\n':' ');
		}
	}
	/*
	for(int i=1;i<=n;++i)
		put(f[sn[i]]),putchar('\n');
	*/	
	return 0;
}