这是我有史以来写得最长的一个程序,前段时间就看了这个题,在网上搜了一下算法,当时看得还有点不太明白,大牛也都说这题代码太长
不好写,开始写了一些,后面发现不会写了,就放下了。昨天又来看这个题,居然写出来了,不过还是花了我一个晚上的时间来调试,开始
交一次结果就RE了,后来在网上找来了官方数据一个一个的运行才发现找圈DFS的时候陷入了死循环,加了一个标志变量,还是WA,后来
反复看解思路才知道换边的时候每一次循环最多只能换一次,而且要换差值最大的那条边,又加了一个优先队列,才终于攻下这道题。
题目大意是:
矮人虽小却喜欢乘坐巨大的轿车,轿车大到可以装下无论多少矮人。某天,N(N≤5000)个矮人打算到野外聚餐。为了集中到聚餐地点,矮人A要么开车到矮人B家中,留下自己的轿车在矮人B家,然后乘坐B的轿车同行;要么直接开车到聚餐地点,并将车停放在聚餐地。
虽然矮人的家很大,可以停放无数量轿车,但是聚餐地点却最多只能停放K辆轿车。现在给你一张加权无向图,它描述了N个矮人的家和聚餐地点,要你求出所有矮人开车的最短总路程。
[输入文件]
第一行是整数M(M<=49000),接下来M行描述了M条道路。每行形式如同:S1 S2 x,S1和S2均是大于0小于5000的整数,x小于等于1000。最后一行包含两个整数k,root。root表示聚餐的地点。
[输出文件]
仅一行,形式如同:Total miles driven: xxxXxx是整数,表示最短总路程。
解题思路:
1)将根节点从图中去除掉
2)对去除根节点的图求MST,注意这里去除根后的图可能是不连通的,所以计算MST的时候要对每个连通图都进行计算
这里我选择用Kruscal算法+并查集求MST.求完后用DFS将属于同一个连通分量的点放在一个数组里面,并得到连通分量的个数。
3)针对每一个连通分量,选择从根节点到这个连通分量里的节点的具有最小权值的边加入图中,假设有deep个连通分
量则一共需要加deep条边
4)由1)2)3)步骤即得到一棵deep最小限度生成树
5)假设题目限定的停车位数是k,那么还需要找k - deep条从根节点出发的边,所以循环k- deep次,每次做
如下操作:
a)假设对于节点k, 边[root, j, w]不在当前树中(权值为w), 那么如果把这条边加入树中就会构成一条环
b)假设这个环中不是与根直接相连的具有最大权值的边为[from, to, weight]
遍历寻找具有最大weight - w值的边,如果这个差值大于0,则将这条边[root, j]加入树中并去除边[from, to],如果差值小于等于0则退出
以下是我的代码:
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
1
#include<iostream>
2
#include<string>
3
#include<vector>
4
#include<algorithm>
5
#include<map>
6
#include<queue>
7
using namespace std;
8
#define N 25
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct node
{
11
int id;
12
int u,v;
13
int len;
14![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
const bool operator<(const node &b)const
{
15
return len<b.len;
16
}
17
}edge[N*N];
18![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
19
map<string,int> name;
20
int pre[N];
21
int data[N][N]; //存储两点之间的距离
22
int num[N];
23
bool dd[N][N]; //标志边是否在生成树中
24
bool mark[N];
25![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
26
int stack[N][N];
27
int n,k,size;
28
int sum,deep;
29![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
30
void init()
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
32
int m,w,u,v;
33
string str1,str2;
34
map<string,int>::iterator mp;
35
name["Park"]=0;
36
memset(link,0,sizeof(link));
37
deep=size=n=0;
38
sum=0;
39
cin>>m;
40![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1;i<=m;i++)
{
41
cin>>str1>>str2>>w;
42![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
43
mp=name.find(str1);
44
if(mp!=name.end())
45
u=mp->second;
46![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
47
n++;
48
name[str1]=n;
49
u=n;
50
}
51
52
mp=name.find(str2);
53
if(mp!=name.end())
54
v=mp->second;
55![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
56
n++;
57
name[str2]=n;
58
v=n;
59
}
60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(u&&v)
{
61
edge[size].u=u;
62
edge[size].v=v;
63
edge[size].len=w;
64
size++;
65
}
66
if(!data[u][v]) //防止重边
67
data[u][v]=data[v][u]=w;
68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
69
data[u][v]=min(w,data[u][v]);
70
data[v][u]=data[u][v];
71
}
72
}
73
cin>>k;
74
}
75![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
76
int find(int i)
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
78
if(i==pre[i]) return i;
79
return pre[i]=find(pre[i]);
80
}
81
//kruskal求最小生成树
82
void mst()
83![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
84
int p,q;
85
sort(edge,edge+size);
86
for(int i=1;i<=n;i++) pre[i]=i;
87![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=0;i<size;i++)
{
88
p=find(edge[i].u);
89
q=find(edge[i].v);
90![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(p!=q)
{
91
dd[edge[i].u][edge[i].v]=true;
92
dd[edge[i].v][edge[i].u]=true;
93
pre[p]=q;
94
sum+=edge[i].len;
95
}
96
}
97
}
98![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
99
void dfs(int i) //寻找连能分量
100![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
101
num[i]=deep;
102
stack[deep][0]++;
103
stack[deep][stack[deep][0]]=i;
104![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=1;j<=n;j++)
{
105
if(dd[i][j]&&!num[j])
106
dfs(j);
107
}
108
}
109![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
110![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool tdfs(int i)
{
111
mark[i]=true;
112
if(i==0) return true;
113![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=0;j<=n;j++)
{
114![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(dd[i][j]&&data[i][j]&&!mark[j])
{
115
pre[j]=i;
116
mark[j]=true;
117
if(tdfs(j))
118
return true;
119
mark[j]=false;
120
}
121
}
122
return false;
123
}
124
void solve()
125![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
126
mst();
127![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1;i<=n;i++)
{
128![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!num[i])
{
129
deep++;
130
dfs(i); //寻找连通分量,将同一个连通分量的点放在stack[deep]中
131
}
132
}
133
134![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1;i<=deep;i++)
{ //在每一个连通分量中找一个离0点最近的点,添加到生成树中
135
int mi=INT_MAX,minj;
136![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=1;j<=stack[i][0];j++)
{
137![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(mi>data[0][stack[i][j]]&&data[0][stack[i][j]])
{
138
mi=data[0][stack[i][j]];
139
minj=stack[i][j];
140
}
141
}
142
dd[0][minj]=true;
143
dd[minj][0]=true;
144
sum+=mi;
145
}
146
priority_queue<node> myque;
147
node stem;
148
int from,to,w;
149![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int i=1;i<=k-deep;i++)
{
150
while(!myque.empty()) myque.pop();
151![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(int j=1;j<=n;j++)
{
152![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(!dd[0][j]&&data[0][j])
{
153
memset(mark,false,sizeof(mark));
154
memset(pre,0,sizeof(pre));
155
from=to=0;
156
int w=0;
157
tdfs(j); //在所形成的圈中找一条data[from][to]-data[0][j]最大的边
158
int tp=0;
159![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(pre[tp])
{ //找到那条边
160![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(data[pre[tp]][tp]>w)
{
161
w=data[pre[tp]][tp];
162
from=pre[tp];
163
to=tp;
164
}
165
tp=pre[tp];
166
}
167![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(from&&to&&data[from][to]>data[0][j])
{
168
stem.id=j;
169
stem.u=from;
170
stem.v=to;
171
stem.len=data[from][to]-data[0][j];
172
myque.push(stem); //将所找到的边添加到优先队列中
173
}
174
}
175
}
176
if(myque.empty()) break;
177
stem=myque.top();
178
sum-=stem.len;
179
dd[stem.v][stem.u]=dd[stem.u][stem.v]=false;
180
dd[0][stem.id]=dd[stem.id][0]=true;
181
} //在找到的边中找出data[from][to]-data[0][j]最大的边
182
cout<<"Total miles driven: "<<sum<<endl;
183
}
184![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
185
int main()
186![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
187
init();
188
solve();
189
return 0;
190
}
191![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)