货车运输和商务旅行

正在缓慢进行的刷题过程…然后便是这两个题(怎么感觉我一打字就变得不会说话了呢…)

首先说这个火车运输,这道题我真的写了一个星期了啊!!!真的是死磕了一个星期,冒着数次写不完作业的风险,投入了无数个晚自习,可是这破题就像黑洞一样,怎么也填不满。然而,这主要还是说明我实在是太弱了。

真的,真的很弱。在这将近两个星期里,我犯了许多低级错误(例如忘加括号啥的),也走了许多弯路,然而静下心来仔细想想,这实际上完全可以避免。
比如说,如果我好好读题,我完全可以不走tarjan这条弯路,完全可以不会打成最小生成树。如果我码的时候在认真点儿,我也完全可以不用犯这么多错。
然而最终,在我的不懈努力(实际上并没有什么卵用)和一份标程(这是最主要的)的帮助下,这道题终于被成功解决。

好了,就是这样了。下面是代码:

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
//codevs 3287
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#define maxn 2000000000
using namespace std;
struct edge
{
int u,v,w,ne;
edge (int _u,int _v,int _w):u(_u),v(_v),w(_w){}
edge (){}
} e[110000];
int fa[15000];
bool vis[15000];
int head[15000],t=1;
int n,m;
//int dis[15000];
//vector<int> que[15000];
//int ans[15000];
int deep[15000];
int mdfs[15000][21],dmin[15000][21];
int findf(int u)
{
return (fa[u]!=u)?fa[u]=findf(fa[u]):u;
}
bool comp(const edge &a,const edge &b)
{
return a.w>b.w;
}
/*
void tarjan(int u)
{
for(int i=head[u];i;i=e[i].ne)
{
if (!vis[e[i].v])
{
tarjan(e[i].v);
fa[e[i].v]=u;
vis[e[i].v]=1;
}
}
/*
for(int i=que[u].size();i;i--)
{

}
}

int dfs(int u,int v,int ff)
{
int ans=0;
int i=head[u];
for(;i;i=e[i].ne)
if (!vis[e[i].v])
q.push(e[i].v),vis[e[i].v]=1;
while(!q.empty)
{
ans=max(ans,e[i].w);
}
i=head[v];
for(;e[i].v!=ff;i=e[i].v)
ans=max(ans,e[i].w);
return ans;
}*/


void dfs(int u,int dep)
{
//dfsx[++tt]=u;
//deep[tt]=dep;
vis[u]=1;
deep[u]=dep;
for(int i=head[u];i;i=e[i].ne)
{
if (!vis[e[i].v])
{
mdfs[e[i].v][0]=u;
dmin[e[i].v][0]=e[i].w;
dfs(e[i].v,dep+1);
}
//deep[tt]=dep;
}
}

void init()
{
/* for(int i=1;i<=n;i++)
{
if (!head[i])
e[t].u=i,e[t].v=n+1,e[t].w=0,head[i]=t;
t++;
}*/
memset(dmin,0x7f,sizeof(dmin));
memset(vis,0,sizeof(vis));
//for(int i=1;i<=20;i++)
//lg2[i]=log(i)/log(2);

// for(int i=1;i<=n;i++)
// if (!vis[i])
// {
// mdfs[i][0]=i;
// dfs(i,1);
// }
mdfs[1][0]=1;
dfs(1,1);
for (int i=1;i<=20;i++)
for (int j=1;j<=n;j++)
//if (j+(1<<(i-1))-1<=n)
{
//mdfs[j][i]=min(mdfs[j][i-1],mdfs[j+(1<<(i-1))][i-1]);
mdfs[j][i]=mdfs[mdfs[j][i-1]][i-1];
dmin[j][i]=min(dmin[j][i-1],dmin[mdfs[j][i-1]][i-1]);
}
}/*
int minrmq(int l,int r)
{

int a=mdfs[l][lg2[r-l+1]],b=mdfs[r-(1<<lg2[r-l+1])+1][lg2[r-l+1]];
return deep[a]<deep[b]?a:b;
//return min(mdfs[l][lg2[r-l+1]],mdfs[r-(1<<lg2[r-l+1])+1][lg2[r-l+1]]);
}*/
int lca(int u,int v)
{
int ans=maxn;
if(findf(u)!=findf(v))return ans;
if (deep[u]>deep[v]) swap(u,v);
// int delta=deep[v]-deep[u];
for (int i=20;i>=0;i--)
{
if (deep[mdfs[v][i]]>=deep[u])
{
ans=min(dmin[v][i],ans);
v=mdfs[v][i];
}
}
if (u==v) return ans;
for(int i=20;i>=0;i--)
{
if (mdfs[u][i]!=mdfs[v][i])
{
ans=min(ans,dmin[u][i]);
ans=min(ans,dmin[v][i]);
u=mdfs[u][i],v=mdfs[v][i];
}
}
ans=min(ans,dmin[u][0]);
ans=min(ans,dmin[v][0]);
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++,t++)
scanf("%d%d%d",&e[t].u,&e[t].v,&e[t].w);
int q;
scanf("%d",&q);

for(int i=1;i<=n;i++)
fa[i]=i;
sort(e+1,e+1+m,comp);
for(int i=1,k=0;i<=m;i++)
{
if (findf(e[i].u)!=findf(e[i].v))
{
fa[findf(e[i].u)]=findf(e[i].v);
e[i].ne=head[e[i].u];
head[e[i].u]=i;
e[t]=edge(e[i].v,e[i].u,e[i].w);
e[t].ne=head[e[i].v],head[e[i].v]=t;
t++;
k++;
if (k==n-1)
break;
}
}
//

//for(int i=1;i<=n;i++)
//fa[i]=i;
init();


for(int i=1;i<=q;i++)
{
int u,v;
scanf("%d%d",&u,&v);
//que[u].push_back(v);
//que[v].push_back(u);

int ans=lca(u,v);
if (ans>=200000000) printf("-1\n");
else
printf("%d\n",ans);
}
//init();
//tarjan(1);
/*
init();
while(1)
{
int i,j;
scanf("%d%d",&i,&j);
printf("%d\n",minrmq(i,j));
}*/
return 0;
}

在这一过程的后半段,我一直处于一种根本找不出错来的窘况,于是各种胡改瞎改,又去搜了一份标程。标程中建树的步骤是:for一遍,如果
这一点没被访问,就用这一点建树。这种情况我之前考虑到过,这样做是为了防止是一个森林,有关这个题的ppt里也写着要把什么有根树转为无根树(然而我并不会怎么建),但我觉得这个题肯定只有一棵树啊。
所以这样默认1是树干不就行了么。但当时病急乱投医,就这样改了,结果果然过了(不科学啊!)。现在仔细想想,还是觉得不对,于是又该回去,依然过(不科学啊啊啊!)。现在仔细想想,还是觉得不对,于是又该回去,依然过。
总之很坑啊。大概是之前胡改瞎改然后把什么致命性低级错误给该对了吧.

下面是标程。这份std写得真正规,就连函数名都首字母大写了…

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 10010
#define MAXM 50010
#define MAXD 22
#define inf 200000
using namespace std;
int father[MAXN],n,m,q;
bool visit[MAXN];
int up[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN];
struct saver
{
int s,t,d;
} e[MAXM];

int cmp(saver a,saver b)
{
return a.d>b.d;
}

//并查集
void init()
{
for(int i=0; i<MAXN; i++)father[i]=i;
}
int Find(int x)
{
if(x==father[x])return father[x];
else
{
father[x]=Find(father[x]);
return father[x];
}
}
void Union(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
if(fx!=fy)
{
father[fx]=fy;
}
}
//处理最大生成树后的边的关系
struct edge
{
edge *next;
int t,d;
edge()
{
next=NULL;
}
}*head[MAXN];
void Add(int s,int t,int d)
{
edge *p=new(edge);
p->t=t,p->d=d,p->next=head[s];
head[s]=p;
}
void AddEdge(int s,int t,int d)
{
Add(s,t,d);
Add(t,s,d);
}
//一个dfs过程,对于和v在一棵树上的所有结点计算其在树中的高度以及up[i][0]和Min[i][0]
void BuildTree(int v)
{
visit[v]=true;
for(edge *p=head[v]; p; p=p->next)
{
if(!visit[p->t])
{
up[p->t][0]=v;
Min[p->t][0]=p->d;
h[p->t]=h[v]+1;
BuildTree(p->t);
}
}
}
//得到u和v两分支高度相同的节点,在此基础上开始倍增
int Move(int &v,int H)
{
int rec = inf;
for(int i=MAXD-1; i>=0; i--)
{
if(h[up[v][i]]>=H)
{
rec=min(rec,Min[v][i]);
v=up[v][i];
}
}
return rec;
}
//倍增算法实现询问u和v路径上最小值
int Query(int u,int v)
{
if(Find(u)!=Find(v))return -1;
int rec = inf;
if(h[u]!=h[v])rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]);
if(u==v) return rec;
for(int i=MAXD-1; i>=0; i--)
{
if(up[u][i]!=up[v][i])
{
rec=min(rec,min(Min[u][i],Min[v][i]));
u=up[u][i];
v=up[v][i];
}
}
rec=min(rec,min(Min[u][0],Min[v][0]));
return rec;
}
int main()
{

//输入
memset(head,0,sizeof(head));
memset(up,0,sizeof(up));
scanf("%d %d",&n,&m);
for(int i=0; i<m; i++)scanf("%d %d %d",&e[i].s,&e[i].t,&e[i].d);
//排序后生产最大生成树构成的森林
sort(e,e+m,cmp);
init();
for(int i=0; i<m; i++)
{
if(Find(e[i].s)!=Find(e[i].t))
{
Union(e[i].s,e[i].t);
AddEdge(e[i].s,e[i].t,e[i].d);
}
}
//初始化每一个结点的up[i][0]和Min[i][0],并计算结点在树中高度
memset(visit,false,sizeof(visit));
for(int i=1; i<=n; i++)
{
if(!visit[i])
{
h[i]=0;
BuildTree(i);
Min[i][0]=inf;
up[i][0]=i;
}
}
//预处理出up[i][j]和Min[i][j]数组
for(int i=1; i<MAXD; i++)
{
for(int j=1; j<=n; j++)
{
up[j][i]=up[up[j][i-1]][i-1];
Min[j][i]=min(Min[j][i-1],Min[up[j][i-1]][i-1]);
}
}
//处理询问
scanf("%d",&q);
while(q--)
{
int u,v;
scanf("%d %d",&u,&v);
printf("%d\n",Query(u,v));
}
return 0;
}

然后是商务旅行。这是一个比货车简单的题,不用建树,其他一样。

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
//codevs 1036
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
vector<int> tree [30100];
int depth[30100],mdfs[30100][25];
bool vis[30100];
void dfs(int u,int dep)
{
vis[u]=1;
depth[u]=dep;
for (int i=0;i<tree[u].size();i++)
{
if (!vis[tree[u][i]])
dfs(tree[u][i],dep+1),mdfs[tree[u][i]][0]=u;
}
}
void init()
{
for(int i=1;i<=20;i++)
for(int j=1;j<=n;j++)
{
mdfs[j][i]=mdfs[mdfs[j][i-1]][i-1];
}
}
int lca(int u,int v)
{
if (depth[u]>depth[v]) swap(u,v);
for(int i=20;i>=0;i--)
if (depth[mdfs[v][i]]>=depth[u])
v=mdfs[v][i];
if (u==v) return u;
for(int i=20;i>=0;i--)
{
if (mdfs[u][i]!=mdfs[v][i])
u=mdfs[u][i],v=mdfs[v][i];
}
return mdfs[u][0];
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
tree[u].push_back(v);
tree[v].push_back(u);
}
memset(vis,0,sizeof(vis));
mdfs[1][0]=1;
dfs(1,0);
init();
int m,x,y,ans=0;
scanf("%d%d",&m,&x);
for(int i=1;i<m;i++)
{
scanf("%d",&y);
int fa=lca(x,y);
ans+=depth[x]+depth[y]-2*depth[fa];
x=y;
}
printf("%d",ans);
return 0;
}

这是一份对codevs题解页面最往下的一个题的简单仿造(好吧),相似度高达99%,好吧,我承认我是因为没读懂题然后去翻题解然后就看到了然后就打出来了。
然后,因为懒得打邻接表了于是就学着上面用了一个vector。貌似还不错。总之,20分钟之内就顺利打出来了。结果因为一个>打成<所以没过,
刚刚发现然后顺利AC了。

总之,我感觉我最需要练得便是一种能力,就是能看懂题目的能力,尽量不犯低级错误的能力,尽量考虑周全的能力,尽量在wa的时候能忍住不翻std耐心排错的能力。

总之,我还有很长的路要走。
-
2016/12/30 20:02