试题 历届试题 城市建设
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。
C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。
输入格式
输入的第一行包含两个整数n, m，分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。
接下来m行，每行三个整数a, b, c，表示可以建设一条从地点a到地点b的道路，花费为c。若c为正，表示建设是花钱的，如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。
接下来一行，包含n个整数w_1, w_2, …, w_n。如果w_i为正数，则表示在地点i建设码头的花费，如果w_i为-1，则表示地点i无法建设码头。
输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。
输出格式
输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。
样例输入
5 5
1 2 4
1 3 -1
2 3 3
2 4 5
4 5 10
-1 10 10 1 1
样例输出
9
样例说明
建设第2、3、4条道路，在地点4、5建设码头，总的花费为9。
数据规模和约定
对于20%的数据，1<=n<=10，1<=m<=20，0<=c<=20，w_i<=20；
对于50%的数据，1<=n<=100，1<=m<=1000，-50<=c<=50，w_i<=50；
对于70%的数据，1<=n<=1000；
对于100%的数据，1 <= n <= 10000，1 <= m <= 100000，-1000<=c<=1000，-1<=w_i<=1000，w_i≠0。
改进前：通俗易懂的常规方法的10分代码如下：
#include <iostream>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
struct Way{
int a,b;
int c;
Way(){ }
Way(int aa,int bb,int cc):a(aa),b(bb),c(cc){ }
bool operator <(const Way &W) const {
return c<W.c;
}
}W[100006];
int dock[10006];
int hasDock[10006];
int father[10006];
int n,m;
void init(){
for(int i=1;i<=n;i++)
father[i]=i;
}
int Find(int x){
if(x==father[x])
return x;
return father[x]=Find(father[x]);
}
bool Same(int x,int y){
return Find(x)==Find(y);
}
void unionSet(int x,int y){
int u=Find(x),v=Find(y);
if(u==v)
return;
father[u]=v;
}
void ReadInput(){
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>W[i].a>>W[i].b>>W[i].c;
for(int i=1;i<=n;i++)
cin>>dock[i];
}
void Kruskal(){
init();
memset(hasDock,0,sizeof(hasDock));
sort(W+1,W+1+m);
int cnt=0;
long long totalC=0;
for(int i=1;i<=m;i++){
if( Same(W[i].a,W[i].b) )
continue;
unionSet(W[i].a,W[i].b);
int x=W[i].a, y=W[i].b;
if(dock[x]!=-1 && dock[y]!=-1 ){//若 a,b 两点可建设 码头，
if(hasDock[x]==0 && hasDock[y]==0 && dock[x]+dock[y] < W[i].c ){ // 且a,b之前都没有建设码头，
// 且费用 小于 造路
totalC+=dock[x]+dock[y];
hasDock[x]=1;
hasDock[y]=1;
break;
}
if( hasDock[x]==1 && hasDock[y]==0 && dock[y]<W[i].c ){//且a已建设码头, b之前没有建设码头，
totalC+=dock[y];
hasDock[y]=1;
break;
}
if( hasDock[x]==0 && hasDock[y]==1 && dock[x]<W[i].c ){ //且b已建设码头, a之前没有建设码头，
totalC+=dock[x];
hasDock[x]=1;
break;
}
else{
totalC+=W[i].c;
}
}
else{
totalC+=W[i].c;
}
cnt++;
if(cnt==n-1)
break;
}
cout<<totalC<<endl;
}
int main(int argc, char** argv) {// 用Kruskal算法
ReadInput();
Kruskal();
return 0;
}
改进后：参考大佬解题思路后改进的50分代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
struct Way{
int a,b;
int c;
Way(){ }
Way(int aa,int bb,int cc):a(aa),b(bb),c(cc){ }
bool operator <(const Way &W) const {
return c<W.c;
}
};
int dock[10006];
int hasDock[10006];
int father[10006];
int n,m;
vector<Way> W;
void init(){
for(int i=1;i<=n;i++)
father[i]=i;
}
int Find(int x){
if(x==father[x])
return x;
return father[x]=Find(father[x]);
}
bool Same(int x,int y){
return Find(x)==Find(y);
}
void unionSet(int x,int y){
int u=Find(x),v=Find(y);
if(u==v)
return;
father[u]=v;
}
void ReadInput(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
W.push_back(Way(a,b,c));
}
for(int i=1;i<=n;i++){
cin>>dock[i];
// if(dock[i]!=-1){
// W.push_back( Way(i,n+1,dock[i]) ); // 所有可建码头 的点 都连接到新建的 点n+1 ，构成通路
// }
}
}
long long Kruskal(){
init();
// memset(hasDock,0,sizeof(hasDock));
sort(W.begin(),W.end());
int cnt=0;
long long totalC=0;
for(int i=0;i<=W.size();i++){
if( Same(W[i].a,W[i].b) )
continue;
unionSet(W[i].a,W[i].b);
int x=W[i].a, y=W[i].b;
totalC+=W[i].c;
// if(W[i].c<0 )
// totalC+=W[i].c;
//
// else if(dock[x]!=-1 && dock[y]!=-1 ){//若 a,b 两点可建设 码头，
// if(hasDock[x]==0 && hasDock[y]==0 && dock[x]+dock[y] < W[i].c ){ // 且a,b之前都没有建设码头，
// // 且费用 小于 造路
// totalC+=dock[x]+dock[y];
// hasDock[x]=1;
// hasDock[y]=1;
// break;
// }
// if( hasDock[x]==1 && hasDock[y]==0 && dock[y]<W[i].c ){//且a已建设码头, b之前没有建设码头，
//
// totalC+=dock[y];
// hasDock[y]=1;
// break;
// }
// if( hasDock[x]==0 && hasDock[y]==1 && dock[x]<W[i].c ){ //且b已建设码头, a之前没有建设码头，
//
// totalC+=dock[x];
// hasDock[x]=1;
// break;
// }
// else{
// totalC+=W[i].c;
// }
// }
// else{
// totalC+=W[i].c;
// }
cnt++;
if(cnt==n-1)
break;
}
return totalC;
}
int main(int argc, char** argv) {// 用Kruskal算法
ReadInput();
long long res=Kruskal();
n++;
for(int i=1;i<n;i++){
if(dock[i]!=-1){
W.push_back( Way(i,n,dock[i]) ); // 所有可建码头 的点 都连接到新建的 点n+1 ，构成通路
}
}
res=min(res,Kruskal());
cout<<res<<endl;
return 0;
}
改了的代码一下午，虽然没能跑满分，但总的写点什么，留下点什么，不然都觉得对不住自己，所以写下这篇未完待续的经验贴，待我日后改进润色。。。
手动狗头。。。