P3128 [USACO15DEC]最大流Max Flow
题面
题目描述
FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。
FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。
输入输出格式
输入格式：
The first line of the input contains NNN and KKK.
The next N?1N-1N?1 lines each contain two integers xxx and yyy (x≠yx \ne yx≠y) describing a pipe
between stalls xxx and yyy.
The next KKK lines each contain two integers sss and ttt describing the endpoint
stalls of a path through which milk is being pumped.
输出格式：
An integer specifying the maximum amount of milk pumped through any stall in the barn.
输入输出样例
输入样例#1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
|
输出样例#1：
Solve
树上差分模板题。
好难，做了一下午
（树咋存来着？）
一开始觉得前向星来存树不好找爸爸。折腾了半天还是用了前向星。
然后LCA也忘了。我还非常沙雕地用tarjan求出每两个点之间的LCA，还开小了数组。结果TLE+MLE。
改用倍增求一直不过样例，后来才发现我一直用的存父亲的数组是放在tarjan LCA里求的。。。
接着只过了一两个点的原因竟然是：
1
2
3
4
5
6
7
8
9
10
11
12
13
| int getLca(int p1,int p2) {
if(depth[p1]<depth[p2]){p1^=p2;p2^=p1;p1^=p2;}
for(int i=H;i>=0;--i){
if(depth[f[p1][i]]>=depth[p2])p1=f[p1][i];}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
if(f[p1][i]!=f[p2][i]){
p1=f[p1][i];
p2=f[p2][i];}
return p1;
}
|
差错的时候写了dfs和bfs两种初始化方法，现在都能AC。
完整代码如下
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
| #include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2e5+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int dad[MAXN];
bool v[MAXN];
int yaLi[MAXN];
int depth[MAXN];
int f[MAXN][16];
int H;
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
void lca(int p);
void getMax(int p);
void bfs(int root);
void dfs(int p,int fat);
int doFind(int x);
int readLca(int p1,int p2);
int getLca(int p1,int p2);
int main(void)
{
scanf("%d%d",&n,&k);
H=1.0*log(n)/log(2);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
bfs(1);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=getLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[f[lca][0]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}
int getLca(int p1,int p2)
{
if(depth[p1]<depth[p2])
{
p1^=p2;
p2^=p1;
p1^=p2;
}
for(int i=H;i>=0;--i)
{
if(depth[f[p1][i]]>=depth[p2])
{
p1=f[p1][i];
}
}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
{
if(f[p1][i]!=f[p2][i])
{
p1=f[p1][i];
p2=f[p2][i];
}
}
return f[p1][0];
}
#include<queue>
void bfs(int root)
{
queue<int> q;
q.push(root);
depth[root]=1;
v[root]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
v[y]=1;
depth[y]=depth[u]+1;
f[y][0]=u;
for(int j=1;j<=H;++j)
{
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
}
void dfs(int p,int fat)
{
depth[p]=depth[fat]+1;
f[p][0]=fat;
for(int i=1;i<=H;++i)
{
f[p][i]=f[f[p][i-1]][i-1];
}
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(y==fat)continue;
else dfs(y,p);
}
}
|
还有一份41分代码（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
| #include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
using namespace std;
const int MAXN=5e4+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int fa[MAXN];
int dad[MAXN];
bool v[MAXN];
int yaLi[MAXN];
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
int doFind(int x);
void lca(int p);
int readLca(int p1,int p2);
void getMax(int p);
int main(void)
{
scanf("%d%d",&n,&k);
doInit();
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
lca(1);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=readLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[dad[lca]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void doInit(void)
{
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
}
void doUnion(int x,int y)
{
x=doFind(x);
y=doFind(y);
fa[x]=y;
}
int doFind(int x)
{
if(fa[x]==x)return x;
else return fa[x]=doFind(fa[x]);
}
void lca(int u)
{
v[u]=1;
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
dad[y]=u;
lca(y);
doUnion(y,u);
}
}
for(int i=1;i<=n;++i)
{
if(i==u)continue;
else
{
if(v[i])
{
zuzong[make_pair(u,i)]=doFind(i);
}
}
}
}
int readLca(int p1,int p2)
{
pair<int,int> pa=make_pair(p1,p2),pb=make_pair(p2,p1);
int z1=zuzong[pa];
if(z1)return z1;
else return zuzong[pb];
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}
|
