抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

initalResult

去年考场上本题考虑过多, 喜提60变20、1=变2=、省队变差8分, 草(砸电脑.gif


本题解几乎全为代码, 请静下心阅读. 我相信我的代码的可读性还是很高的.

题目

NOIP2018.D2T1

Datarange

题解

  回到正题. 首先观察数据. n = 5000, 所以暴力就好了. 我在考场上用邻接矩阵都过了树的subtask.

  现在讨论各个subtask的情况.

n = m - 1

  明显, 此时的图为一棵树. 只需以出边到达点字典序从小到大进行一次不回溯的DFS(树生成), 再判断生成树的字典序即可; 复杂度$\Theta \left ( N \right )$.

  以下为本人去年此subtask的去锅代码.

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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>

const int maxN = 5000;
int n,m,current;
bool isFinal;
int minimalSet[1 + maxN];
bool isCityVisited[1 + maxN];
bool roadIndex[1 + maxN][1 + maxN];

void travel(int nowCity)
{
if(isFinal)
{
return;
}
current++;
minimalSet[current] = nowCity;
isCityVisited[nowCity] = true;
if(current == n)
{
minimalSet[0] = nowCity;
for(int i = 1;i <= n;i++)
{
printf("%i ",minimalSet[i]);
}
isFinal = true;
return;
}
for(int i = 1;i <= n;i++)
{
if(isCityVisited[i] == false
&&(roadIndex[nowCity][i] || roadIndex[i][nowCity]))
{
travel(i);
}
}
}

int main()
{
std::cin >> n >> m;
for(int i = 1;i <= m;i++)
{
int u,v;
scanf("%i %i",&u,&v);
roadIndex[u][v] = true;
roadIndex[v][u] = true;
}

travel(1);

return 0;
}

n = m

  相应地, 这种情况下的图为有且只有一条环的图.

  去年看到这就放弃了, 毕竟当时连存图都是凭印象瞎搞的. 当然, 现在看来无非两种方式: 找边, 找环. 这里从简(其实还是不会), 只讨论暴力断边的方案.

  这样一张图(基环树/图)有这样的性质: 断环上的任意一条边, 图就变成一棵树. 那么就有以下暴力断开每一条边再进行树生成并判断字典序的代码.

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
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
#include <iostream>

struct Edge
{
int u, v;
bool w;

Edge(int U = 0, int V = 0, bool W = true)
{
(*this).u = U, (*this).v = V, (*this).w = W;
}

void reverse()
{
std::swap((*this).u, (*this).v);
return;
}

Edge getReversed()
{
return Edge((*this).v, (*this).u, (*this).w);
}

Edge operator = (const Edge& inEdge)
{
(*this).u = inEdge.u, (*this).v = inEdge.v, (*this).w = inEdge.w;
return *this;
}
}
emptyEdge;

inline bool cmp(Edge E, Edge e)
{
return E.v < e.v;
}

inline void copy(int n, int* ori, int* des)
{
for(int i = 1; i <= n; i++) des[i] = ori[i];
}

inline void set(int n, bool stat, bool* des)
{
for(int i = 1; i <= n; i++) des[i] = stat;
}

inline bool isMinDic(int n, int* dicOri, int* dicCmp)
{
for(int i = 1; i <= n; i++)
{
if(dicCmp[i] != dicOri[i])
{
if(dicCmp[i] > dicOri[i]) return false;
if(dicCmp[i] < dicOri[i]) return true;
}
}
return false;
}

inline void setEdge(int u, int v, bool w, std::vector<Edge>* graph)
{
for(std::vector<Edge>::iterator it = graph[u].begin(); it != graph[u].end(); it++)
{
if((*it).v == v)
{
(*it).w = w;
return;
}
}
}

void DFS(int now, int& depth, bool* isVisited, std::vector<Edge>* graph, int* dic)
{
isVisited[now] = true;
dic[depth++] = now;
for(std::vector<Edge>::iterator it = graph[now].begin(); it != graph[now].end(); it++)
{
if(!isVisited[(*it).v] && (*it).w)
DFS((*it).v, depth, isVisited, graph, dic);
}
}

inline void subtask(int n, std::vector<Edge>* graph, bool* isVisited, int* dic)
{
for(int k = 1;k <= n;k++)
{
for(std::vector<Edge>::iterator it = graph[k].begin(); it != graph[k].end(); it++)
{
(*it).w = false/*, setEdge((*it).v, (*it).u, false, graph)*/;

int tDic[1 + n]; tDic[0] = 0; int depth = 1;
for(int i = 1; i <= n; i++){tDic[i] = 5000 + 1; isVisited[i] = false;}

DFS(1, depth, isVisited, graph, tDic);
if(isMinDic(n, dic, tDic)) copy(n, tDic, dic);

(*it).w = true/*, setEdge((*it).v, (*it).u, true, graph)*/;
}
}
}

int main()
{
int n, m;
std::cin >> n >> m;
std::vector<Edge> graph[1 + n];
for(int i = 1; i <= m; i++)
{
int u, v;
scanf("%i %i", &u, &v);
graph[u].push_back(Edge(u, v));
graph[v].push_back(Edge(v, u));
}
for(int i = 1; i <= n; i++)
{
std::sort(graph[i].begin(), graph[i].end(), cmp);
}

int dic[1 + n]; for(int i = 1;i <= n;i++){dic[i] = 5000 + 1;} dic[0] = 0;
bool isVisited[1 + n]; memset(isVisited, false, sizeof(isVisited));
int depth = 1;
n != m ? DFS(1, depth, isVisited, graph, dic)
: subtask(n, graph, isVisited, dic);

for(int i = 1; i <= n; i++)
{
printf("%i ", dic[i]);
}

return 0;
}

TLE

  我交了, 吸氧了, 多50ms T了, 那咋办嘛 QAQ

  很明显, 这个简单暴力方法的复杂度为$\Theta\left(N^{2}\right)$, 所以T了也不奇怪.

剪枝

  相应地, 这时就需要剪枝了.

  这里只讲最优化剪枝. 当当前搜索所得序列劣于已得最佳序列时就可选择剪枝. 修改上述程序, 最终得到以下代码, 复杂度$\Omega\left(n\right)$, $O\left(N^{2}\right)$.

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
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <cstdio>
#include <iostream>

struct Edge
{
int u, v;
bool w;

Edge(int U = 0, int V = 0, bool W = true)
{
(*this).u = U, (*this).v = V, (*this).w = W;
}

void reverse()
{
std::swap((*this).u, (*this).v);
return;
}

Edge getReversed()
{
return Edge((*this).v, (*this).u, (*this).w);
}

Edge operator = (const Edge& inEdge)
{
(*this).u = inEdge.u, (*this).v = inEdge.v, (*this).w = inEdge.w;
return *this;
}
}
emptyEdge;

inline bool cmp(Edge E, Edge e)
{
return E.v < e.v;
}

inline void copy(int n, int* ori, int* des)
{
for(int i = 1; i <= n; i++) des[i] = ori[i];
}

inline void set(int n, bool stat, bool* des)
{
for(int i = 1; i <= n; i++) des[i] = stat;
}

inline bool isMinDic(int n, int* dicOri, int* dicCmp)
{
for(int i = 1; i <= n; i++)
{
if(dicCmp[i] != dicOri[i])
{
if(dicCmp[i] > dicOri[i]) return false;
if(dicCmp[i] < dicOri[i]) return true;
}
}
return false;
}

inline void setEdge(int u, int v, bool w, std::vector<Edge>* graph)
{
for(std::vector<Edge>::iterator it = graph[u].begin(); it != graph[u].end(); it++)
{
if((*it).v == v)
{
(*it).w = w;
return;
}
}
}

void DFS(int now, int& depth, bool* isVisited, std::vector<Edge>* graph, int* dic, int* cmpDic, bool& wasEqual, bool& isBestSolution, bool& notBestSolution)
{
if(notBestSolution) return;
isVisited[now] = true;
dic[depth] = now;
if(wasEqual && !isBestSolution)
{
dic[depth] != cmpDic[depth] ? (dic[depth] < cmpDic[depth] ? isBestSolution = true : false),
(dic[depth] > cmpDic[depth] ? notBestSolution = true : false),
wasEqual = false
: wasEqual = true;
}
depth++;
for(std::vector<Edge>::iterator it = graph[now].begin(); it != graph[now].end(); it++)
{
if(!isVisited[(*it).v] && (*it).w)
DFS((*it).v, depth, isVisited, graph, dic, cmpDic, wasEqual, isBestSolution, notBestSolution);
}
}

inline void subtask(int n, int& depth, bool* isVisited, std::vector<Edge>* graph, int* dic, int* resultDic, bool& wasEqual, bool& isBestSolution, bool& notBestSolution)
{
for(int k = 1;k <= n;k++)
{
for(std::vector<Edge>::iterator it = graph[k].begin(); it != graph[k].end(); it++)
{
(*it).w = false/*, setEdge((*it).v, (*it).u, false, graph)*/;

int tDic[1 + n];
tDic[0] = 0, depth = 1, wasEqual = true, isBestSolution = false, notBestSolution = false;
for(int i = 1; i <= n; i++) {tDic[i] = 5000 + 1; isVisited[i] = false;}

DFS(1, depth, isVisited, graph, tDic, resultDic, wasEqual, isBestSolution, notBestSolution);
if(isBestSolution) copy(n, tDic, resultDic);

(*it).w = true/*, setEdge((*it).v, (*it).u, true, graph)*/;
}
}
}

int main()
{
//freopen("in","r",stdin);
int n, m;
std::cin >> n >> m;
std::vector<Edge> graph[1 + n];
for(int i = 1; i <= m; i++)
{
int u, v;
scanf("%i %i", &u, &v);
graph[u].push_back(Edge(u, v));
graph[v].push_back(Edge(v, u));
}
for(int i = 1; i <= n; i++)
{
std::sort(graph[i].begin(), graph[i].end(), cmp);
}

int dic[1 + n]; for(int i = 1;i <= n;i++){dic[i] = 5000 + 1;} dic[0] = 0;
bool isVisited[1 + n]; memset(isVisited, false, sizeof(isVisited));
int depth = 1; bool wasEqual = true, isBestSolution = false, notBestSolution = false;
n != m ? DFS(1, depth, isVisited, graph, dic, dic, wasEqual, isBestSolution, notBestSolution)
: subtask(n, depth, isVisited, graph, dic, dic, wasEqual, isBestSolution, notBestSolution);

for(int i = 1; i <= n; i++)
{
printf("%i ", dic[i]);
}

return 0;
}

Comments