洛谷 P3905 道路重建

Love The Way You Lie 2023-07-15 13:03 17阅读 0赞

## 题目描述 ##

从前，在一个王国中，在nnn个城市间有mmm条道路连接，而且任意两个城市之间至多有一条道路直接相连。在经过一次严重的战争之后，有ddd条道路被破坏了。国王想要修复国家的道路系统，现在有两个重要城市AAA和BBB之间的交通中断，国王希望尽快的恢复两个城市之间的连接。你的任务就是修复一些道路使AAA与BBB之间的连接恢复，并要求修复的道路长度最小。

## 输入格式 ##

输入文件第一行为一个整数nnn（2<n≤1002<n≤1002<n≤100）,表示城市的个数。这些城市编号从111到nnn。

第二行为一个整数mmm（n−1≤m≤12n(n−1)n-1≤m≤\\frac\{1\}\{2\} n(n-1)n−1≤m≤21n(n−1)），表示道路的数目。

接下来的mmm行，每行333个整数i,j,ki,j,ki,j,k（1≤i,j≤n,i≠j,0<k≤1001≤i,j≤n,i≠j,0<k≤1001≤i,j≤n,i=j,0<k≤100），表示城市iii与jjj之间有一条长为kkk的道路相连。

接下来一行为一个整数ddd（1≤d≤m1≤d≤m1≤d≤m），表示战后被破坏的道路的数目。在接下来的ddd行中，每行两个整数iii和jjj，表示城市iii与jjj之间直接相连的道路被破坏。

最后一行为两个整数A和B，代表需要恢复交通的两个重要城市。

## 输出格式 ##

输出文件仅一个整数，表示恢复AAA与BBB间的交通需要修复的道路总长度的最小值。

## 输入输出样例 ##

**输入 \#1**

3
    2
    1 2 1
    2 3 2
    1
    1 2
    1 3

**输出 \#1**

**思路：先用Dijkstra算法或者SPFA算法，求出最短路径，在Dijkstra或者SPFA算法中，使用pre数组记录每个点的前驱节点，以及与前驱结点之间边的权重，所以pre数组的元素是一个结构体。最短路径求出来之后，递归pre数组。**

**例如：pre\[u\] = Node(v,len)。表示u的前驱节点为v，v与u之间的边权是len。**

**随后遍历所有被破坏的道路，看看u--v这条道路是否被破坏，如果被破坏，要修复的道路总长度就加上len。**

**SPFA 算法：**

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    using namespace std;
    const int MAXN = 102; 
    const int MAXM = 10002;
    const int INF = 999999;
    
    struct Node{
    	int v;  //边某一端点的编号 
    	int len; //边的权重 
    	Node(){
    		this->v = -1;
    	}
    	Node(int v,int len){
    		this->v = v;
    		this->len = len;
    	}
    };
    vector<Node> adj[MAXN]; //邻接表，存放道路信息。 
    int dis[MAXN];
    queue<int> que;  
    Node pre[MAXN];  //pre[u] = Node(v,len) 记录了最短路径中，u的前驱节点为v，以及v到u这条路径的权重为len 
    
    /*
    ** 边 
    */
    struct Edge{
    	int u;
    	int v;
    	Edge(int u,int v){
    		this->u = u;
    		this->v = v;
    	}
    };
    vector<Edge> edges; //保存被破坏的道路 
    
    /*
    ** 正常的SPFA算法 
    */
    void SPFA(int s,int n){
    	fill(dis,dis+n+1,INF);
    	dis[s] = 0;
    	que.push(s);
    	while(!que.empty()){
    		int u = que.front();
    		que.pop();
    		for(int i=0;i<adj[u].size();i++){
    			Node node = adj[u][i];
    			int v = node.v;
    			int len = node.len;
    			if(dis[v] > dis[u]+len){
    				dis[v] = dis[u] + len;
    				que.push(v);
    				/*
    				** 就比SPFA算法的模板多了个求前驱节点的过程 
    				*/
    				pre[v].v = u;
    				pre[v].len = len;
    			}	
    		}
    	}
    }
    
    /*
    ** 遍历从A到B之间的路径
    ** 查看所经过的路径是否被破坏 
    */
    int DFS(int u){
    	int ans = 0;
    	int v;
    	//递归遍历pre数组。 
    	while(pre[u].v != -1){ //如果u还有前驱节点的话 
    		v = pre[u].v; //取出u节点的前驱节点v 
    		for(auto it=edges.begin();it!=edges.end();it++){  //遍历被破坏的道路 
    			int a = it->u;
    			int b = it->v;
    			//如果u--v这条道路被破坏 
    			if((a==u&&b==v) || (a==v&&b==u)){  
    				ans += pre[u].len; //这条道路需要修理 
    				edges.erase(it);  //这条道路已经修好了，从破损道路中删除。 
    				break;
    			}
    		}
    		u = v; //前往前驱节点。 
    	}
    	return ans;
    }
    
    int main(){
    	int n,m,d;
    	int u,v,len;
    	int s,t;
    	cin>>n;
    	cin>>m;
    	while(m--){
    		cin>>u>>v>>len;
    		adj[u].push_back(Node(v,len));
    		adj[v].push_back(Node(u,len));
    	}
    	cin>>d;
    	while(d--){
    		cin>>u>>v;
    		edges.push_back(Edge(u,v));
    	}
    	cin>>s>>t;
    	SPFA(s,n);
    	cout<<DFS(t)<<endl;
    	return 0; 
    }

**Dijkstra 算法：**

#include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    #include<queue>
    using namespace std;
    const int MAXN = 102; 
    const int MAXM = 10002;
    const int INF = 999999;
    
    struct Node{
    	int v;  //边某一端点的编号 
    	int len; //边的权重 
    	Node(){
    		this->v = -1;
    	}
    	Node(int v,int len){
    		this->v = v;
    		this->len = len;
    	}
    };
    vector<Node> adj[MAXN]; //邻接表，存放道路信息。 
    int dis[MAXN];   //dis[u]:从源点到u的最短路径
    bool vis[MAXN];  //vis[u]=true 表示 从源点到u的最短路径已经求出来了。 
    Node pre[MAXN];  //pre[u] = Node(v,len) 记录了最短路径中，u的前驱节点为v，以及v到u这条路径的权重为len 
    
    /*
    ** 边 
    */
    struct Edge{
    	int u;
    	int v;
    	Edge(int u,int v){
    		this->u = u;
    		this->v = v;
    	}
    };
    vector<Edge> edges; //保存被破坏的道路 
    
    /*
    ** 常规的Dijkstra模板 
    */
    void Dijkstra(int s,int t,int n){
    	fill(dis,dis+n+1,INF);
    	dis[s] = 0;
    	for(int i=0;i<n;i++){
    		int u = -1;
    		int minDis = INF;
    		for(int j=1;j<=n;j++){
    			if(!vis[j] && dis[j] < minDis){
    				minDis = dis[j];
    				u = j;
    			}
    		}
    		if(u == t){
    			return ;
    		}
    		vis[u] = true;
    		for(int j=0;j<adj[u].size();j++){
    			Node node = adj[u][j];
    			int v = node.v;
    			int len = node.len;
    			if(!vis[v]){
    				if(dis[v] > dis[u]+len){
    					dis[v] = dis[u] + len;
    					/*
    					** 就比Dijkstra算法的模板多了个求前驱节点的过程 
    					*/
    					pre[v].v = u;
    					pre[v].len = len;
    				}	
    			}
    		}
    	}
    }
    
    /*
    ** 遍历从A到B之间的路径
    ** 查看所经过的路径是否被破坏 
    */
    int DFS(int u){
    	int ans = 0;
    	int v;
    	//递归遍历pre数组。 
    	while(pre[u].v != -1){ //如果u还有前驱节点的话 
    		v = pre[u].v; //取出u节点的前驱节点v 
    		for(auto it=edges.begin();it!=edges.end();it++){  //遍历被破坏的道路 
    			int a = it->u;
    			int b = it->v;
    			//如果u--v这条道路被破坏 
    			if((a==u&&b==v) || (a==v&&b==u)){  
    				ans += pre[u].len; //这条道路需要修理 
    				edges.erase(it);  //这条道路已经修好了，从破损道路中删除。 
    				break;
    			}
    		}
    		u = v; //前往前驱节点。 
    	}
    	return ans;
    }
    
    int main(){
    	int n,m,d;
    	int u,v,len;
    	int s,t;
    	cin>>n;
    	cin>>m;
    	while(m--){
    		cin>>u>>v>>len;
    		adj[u].push_back(Node(v,len));
    		adj[v].push_back(Node(u,len));
    	}
    	cin>>d;
    	while(d--){
    		cin>>u>>v;
    		edges.push_back(Edge(u,v));
    	}
    	cin>>s>>t;
    	Dijkstra(s,t,n);
    	cout<<DFS(t)<<endl;
    	return 0; 
    }