专题七 图论
102400226 石华波
Vjudge账号:DustLi
问题一 Stockbroker Grapevine
问题陈述
城市准备建造一个物流中心，今后所有物流都会由中心向其他物流站分配。
现在有n个站点，站点之间存在着单向的道路，走每条道路都需要花费一些时间，在这些站点中选择一个，使分配最高效。
给出站点数目和道路情况，请输出选择的物流站点编号以及今后所需的分配时间。假设从中转中心同时向其他站分发，所需的分配时间指的是最后一个物流站点接受到物流所花费的总时间。
解题思路
Floyd求最短路。
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
|
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
using ll=long long;
int N;
void Floyd(vector<vector<int>> &Dis,int N) {
for (int k =1;k<=N;++k) for (int i=1;i<=N;++i) for (int j=1;j<=N;++j) Dis[i][j]=min(Dis[i][j],Dis[i][k]+Dis[k][j]);
}
int main() {
int N;
while(cin>>N&&N) {
vector<vector<int>> Dis(N+1,vector<int>(N+1,1e5));
for(int i=1;i<=N;++i) {
int M;
cin>>M;
Dis[i][i]=0;
while(M--) {
int P,T;
cin>>P>>T;
Dis[i][P]=T;
}
}
Floyd(Dis,N);
int Min=1e5,Pos=0;
for(int i=1;i<=N;++i) {
int Max=-1e5;
for(int j=1;j<=N;++j) Max=max(Dis[i][j],Max);
if(Max<Min) {
Min=Max;
Pos=i;
}
}
if(Min==1e5) cout<<"disjoint"<<endl;
else cout<<Pos<<" "<<Min<<endl;
}
return 0;
}
|
问题二 树的直径
问题陈述
一棵树的直径就是这棵树上存在的最长路径。现在有一棵 nn 个节点的树，现在想知道这棵树的直径包含的边的个数是多少？
如图所示的数据，这棵树的直径为 (1−2−3−6−9)(1−2−3−6−9) 这条路径，包含的边的个数为 44 ，所以答案是 44 。
解题思路
双DFS，由第一个节点找到离它最远的节点，再找到离此节点最远的节点即可。
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
|
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
using ll=long long;
int N,C,Cnt;
int Dis[100001];
vector<int> Pat[100001];
void DFS(int U,int F) {
for (int V:Pat[U]) {
if(V==F) continue;
Dis[V]=Dis[U]+1;
if(Dis[V]>Dis[C]) {
C=V;
Cnt++;
}
DFS(V,U);
}
}
int main() {
cin>>N;
for(int i=1;i<N;i++) {
int S,E;
cin>>S>>E;
Pat[S].push_back(E);
Pat[E].push_back(S);
}
DFS(1,0);
Dis[C]=0;
Cnt=0;
DFS(C,0);
cout<<Cnt<<endl;
return 0;
}
|
问题三 Invitation Cards
问题陈述
在电视时代，参加剧院表演的人并不多。马利丁西亚的古董喜剧演员意识到了这一点。他们希望传播剧院，尤其是古董喜剧。他们印制了包含所有必要信息和节目安排的邀请卡。许多学生被雇来在公众中分发这些邀请函。每位学生志愿者被分配了一个特定的公交站，他们整天待在那里，向乘坐公交的人发放邀请函。学生们参加了一门特殊课程，学习如何影响他人，以及影响与抢劫之间的区别。
交通系统非常特别：所有线路都是单向的，并且连接恰好两个站点。公交车每半小时从出发站出发，载着乘客。到达目的地后，公交车空车返回出发站，等待下一个整点半，例如 X:00 或 X:30，其中 ‘X’ 表示小时。两个站点之间的交通费用由特殊表格给出，并且需当场支付。线路的规划方式是，每个往返（即从同一站点出发并返回）都经过一个中央检查站（CCS），每位乘客都必须经过全面检查，包括身体扫描。
所有 ACM 学生成员每天早上从 CCS 出发。每位志愿者都要前往一个预定的站点邀请乘客。志愿者的数量与站点数量相同。一天结束时，所有学生都会返回 CCS。你需要编写一个计算机程序，帮助 ACM 最小化每天为其员工的交通费用。
解题思路
不解绑cin会超时很多很多很多很多很多。
反向建边，先从CCS找去各个站点的最短路，再从各个站点找回CCS。
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
using ll=long long;
const int MaxN=1000001;
int P,Q;
int Dist1[MaxN],Dist2[MaxN];
void Dijkstra(vector<vector<pair<int, int>>> &v,int Dist[MaxN]) {
for(int i=1;i<=P;i++) Dist[i]=INT_MAX;
Dist[1] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> Q;
Q.push({0, 1});
while(!Q.empty()) {
auto [w, S] = Q.top();
Q.pop();
if(Dist[S]<w) continue;
for(auto& [E,weight]:v[S]) {
if(Dist[S]+weight<Dist[E]) {
Dist[E]=Dist[S]+weight;
Q.push({Dist[E],E});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--) {
cin>>P>>Q;
vector<vector<pair<int,int>>> E1(P+1),E2(P+1);
for(int i=1;i<=Q;i++) {
int St,En,Va;
cin>>St>>En>>Va;
E1[St].push_back({En,Va});
E2[En].push_back({St,Va});
}
Dijkstra(E1,Dist1);
Dijkstra(E2,Dist2);
int Ans=0;
for(int i=1;i<=P;i++) Ans+=Dist1[i]+Dist2[i];
cout<<Ans<<endl;
}
return 0;
}
|
问题4 战略游戏
问题陈述
他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。
注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。
请你编一程序，给定一树，帮 Bob 计算出他需要放置最少的士兵。
解题思路
树形DP？
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
|
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
using ll=long long;
const int N = 1501;
int n;
vector<vector<int>> Links(N);
int DP[N][2];
void DFS(int u,int Fa) {
DP[u][1]=1;
DP[u][0]=0;
for (auto v:Links[u]) {
if (v==Fa) continue;
DFS(v,u);
DP[u][0]+=DP[v][1];
DP[u][1]+=min(DP[v][1],DP[v][0]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for (int i=1;i<=n;i++) {
int x,k,y;
cin>>x>>k;
for (int j=1;j<=k;j++) {
cin>>y;
Links[x].push_back(y);
Links[y].push_back(x);
}
}
DFS(1,-1);
cout<<min(DP[1][0],DP[1][1])<<endl;
return 0;
}
|
问题五 飞行路线
问题陈述
Alice 和 Bob 现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在 nn 个城市设有业务，设这些城市分别标记为 00 到 n−1n−1，一共有 mm 种航线，每种航线连接两个城市，并且航线有一定的价格。
Alice 和 Bob 现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多 kk 种航线上搭乘飞机。那么 Alice 和 Bob 这次出行最少花费多少？。
解题思路
分层图最短路。
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
using ll=long long;
const int MAXN=1e5+5;
const int MAXK=25;
int Dis[MAXN][MAXK];
bool Vis[MAXN][MAXK];
int n,m,k,s,t;
vector<vector<pair<int,int>>> Edge;
void Dijkstra() {
fill_n(*Dis,MAXN*MAXK,INT_MAX);
Dis[s][0]=0;
priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
pq.push({0,s,0});
while(!pq.empty()) {
vector<int> state=pq.top();
pq.pop();
int u=state[1],cnt=state[2];
if(Vis[u][cnt]) continue;
Vis[u][cnt]=true;
for(auto& edge:Edge[u]) {
int v=edge.first,w=edge.second;
if(cnt<k && Dis[v][cnt+1]>Dis[u][cnt]) {
Dis[v][cnt+1]=Dis[u][cnt];
pq.push({Dis[v][cnt+1],v,cnt+1});
}
if(Dis[v][cnt]>Dis[u][cnt]+w) {
Dis[v][cnt]=Dis[u][cnt]+w;
pq.push({Dis[v][cnt],v,cnt});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m>>k;
cin>>s>>t;
s++;t++;
Edge.resize(n+1);
for(int i=0;i<m;++i) {
int u,v,w;
cin>>u>>v>>w;
u++;v++;
Edge[u].emplace_back(v,w);
Edge[v].emplace_back(u,w);
}
Dijkstra();
int Ans=INT_MAX;
for(int i=0;i<=k;++i) Ans=min(Ans,Dis[t][i]);
cout<<Ans<<endl;
return 0;
}
|
问题六 二叉苹果树
问题陈述
有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）
这棵树共有 NN 个结点（叶子点或者树枝分叉点），编号为 1∼N1∼N，树根编号一定是 11。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 44 个树枝的树：
1
2
3
4
5
|
2 5
\ /
3 4
\ /
1
|
现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
解题思路
树形DP。
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
|
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
using ll=long long;
const int MaxN=105;
int n,m,DP[MaxN][MaxN],Br[MaxN];
vector<pair<int,int>> Edge[MaxN];
void DFS(int u, int fa) {
for (auto &edge:Edge[u]) {
int v=edge.first;
int w=edge.second;
if(v==fa) continue;
DFS(v,u);
Br[u]+=Br[v] + 1;
for (int j=min(Br[u],m);j>=1;j--)
for (int k=min(Br[v],j-1);k>=0;k--)
DP[u][j]=max(DP[u][j],DP[u][j-k-1]+DP[v][k]+w);
}
}
int main() {
cin>>n>>m;
for(int i=1;i<n;++i) {
int u,v,w;
cin>>u>>v>>w;
Edge[u].emplace_back(v,w);
Edge[v].emplace_back(u,w);
}
DFS(1,-1);
cout<<DP[1][m]<<endl;
return 0;
}
|
学习总结
本专题内容主要为图论，通过学习，提高了自己的能力。