图论习题1
[刷题记录]图论习题1（floyd应用）
- 搞了三道图论入门题，全是$floyd$，记录一下。
题意
- 有一棵二叉树，每个节点代表一个地方的人数，相邻节点之间距离为1，现在要在某个节点设置医院，要求所有人到医院的路程之和最小，求最小路程和。
Sample Input
| 5 //5个节点
13 2 3 //第i个节点的人数 左儿子是2 右儿子是3
4 0 0 // 0代表没有这个儿子
12 4 5
20 0 0
40 0 0
|
Sample Output
思路&题解
- 先$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
45
46
47
48
49
| #include<bits/stdc++.h>
using namespace std;
int dp[105][105],num[105];
int ans=1e9;
int n;
void gao(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) continue;
else dp[i][j]=1e9;
}
}
for(int i=1;i<=n;i++){
cin>>num[i];
int x;
cin>>x;
if(x!=0){
dp[i][x]=1;
dp[x][i]=1;
}
cin>>x;
if(x!=0){
dp[i][x]=1;
dp[x][i]=1;
}
}
gao();
for(int k=1;k<=n;k++){
int temp = 0;
for(int i=1;i<=n;i++){
if(i==k) continue;
temp+=dp[k][i]*num[i];
}
ans = min(ans,temp);
}
cout<<ans<<endl;
return 0;
}
|
题意
- 一个无向无环图，边权都为1，有$n$次询问，每次询问一个点对$(a,b)$，要求输出$a$与$b$之间所有最短路上的点的总个数（注意：可能有多条最短路）。
思路&题解
- $floyd$过后，针对每次询问，开始遍历所有点作为中间节点，判断是否有$dp[a][b] == dp[a][i]+dp[i][b]$即可。
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<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) dp[i][j]=0;
else dp[i][j]=1e9;
}
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
dp[x][y]=dp[y][x]=1;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
int p;
cin>>p;
for(int i=1;i<=p;i++){
int x,y;
cin>>x>>y;
int cnt=0;
for(int i=1;i<=n;i++){
if(dp[x][y]==dp[x][i]+dp[i][y])
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}
|
题意
- 解释过来就是：有一个无向无环有权图（可能有重边），求图中的最小环。（注意：无向图的最小环最小为3个节点组成的环）
思路&题解
- 经典的无向图最小环问题，思路是：在$floyd$求解过程中，在枚举到$k$节点为中间节点时，所有点以第$1…k-1$的作为中间节点的最短路都已经算好了，它们都是不经过$k$节点的最短路，因此可以利用这一点，在更新本次以$k$节点为中间节点的最短路之前，枚举$k$节点之前的所有节点来求最小环大小，状态转移方程：其中，$dis[i][j]$为更新过的$i$到$j$的最短路，$mm$数组为原始图的邻接矩阵。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[105][105];
ll n,m;
ll ans[105][105];
ll anss=1e9;
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<k;i++){
for(int j=i+1;j<k;j++){
anss = min(anss,dp[i][j]+ans[i][k]+ans[k][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
}
int main(){
while(cin>>n>>m){
anss=1e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j) ans[i][j]=dp[i][j]=1e9;
}
}
while(m--){
ll x,y,d;
cin>>x>>y>>d;
dp[x][y]=dp[y][x]=ans[x][y]=ans[y][x]=min(dp[x][y],d);
}
floyd();
if(anss==1e9) cout<<"No solution."<<endl;
else cout<<anss<<endl;
}
return 0;
}
|
- $floyd$代码还是比较好理解的，主要是最小环算法比较巧妙orz，继续加油！