UVA - 1416 Warfare And Logistics (最短路)
Description
The army of United Nations launched a new wave of air strikes on terroristforces. The objective of the mission is to reduce enemy's logistical mobility. Each airstrike will destroy a path and therefore increase the shipping cost of the shortest pathbetween
two enemy locations. The maximal damage is always desirable.
Let's assume that there are n enemy locations connected by
m bidirectional paths,each with specific shipping cost. Enemy's total shipping cost is given as
c = path(i,
j). Here path(i, j) is the shortest path between locations
i and j. In case
i and j are not connected,
path(i, j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is noted as
c'. In order to maximizedthe damage to the enemy, UN's air force try to find the maximal
c' - c.
Input
The first line ofeach input case consists ofthree integers:
n, m, and L.
1 < n100,1m1000,
1L108.
Each ofthe following m lines contains three integers:
a,b,
s, indicating length of the path between a and
b.
Output
For each case, output the total shipping cost before the air strike and the maximaltotal shipping cost after the strike. Output them in one line separated by a space.
Sample Input
4 6 1000
1 3 2
1 4 4
2 1 3
2 3 3
3 4 1
4 2 2
Sample Output
28 38
题意:给出一个n节点m条边的无向图,每条边上有一个正权,令c等于每对结点的最短路径之和,要求删除一条边后使得新的c值最大。不连通的两个点距离视为L
思路:每次求单源最短路的同一时候记录下删除边的值,然后计算最小值就是了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 1010;
const int INF = 0x3f3f3f3f; struct Edge {
int from, to, dist;
}; struct HeapNode {
int d, u;
bool operator<(const HeapNode rhs) const {
return d > rhs.d;
}
}; struct Dijkstra {
int n, m;
vector<Edge> edges;
vector<int> G[MAXN];
bool done[MAXN];
ll d[MAXN];
int p[MAXN]; void init(int n) {
this->n = n;
for (int i = 0; i < n; i++)
G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int dist) {
edges.push_back((Edge){from, to, dist});
edges.push_back((Edge){to, from, dist});
m = edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
} void dijkstra(int s, int curEdge) {
priority_queue<HeapNode> Q;
for (int i = 0; i < n; i++)
d[i] = INF;
d[s] = 0;
memset(done, 0, sizeof(done));
memset(p, -1, sizeof(p));
Q.push((HeapNode){0, s});
while (!Q.empty()) {
HeapNode x = Q.top();
Q.pop();
int u = x.u;
if (done[u])
continue;
done[u] = true;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (G[u][i] == curEdge/2*2 || G[u][i] == curEdge/2*2+1)
continue;
if (d[e.to] > d[u] + e.dist) {
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to], e.to});
}
}
}
}
}arr; int pre[MAXN];
int n, m, L;
ll s[MAXN][MAXN], A[MAXN]; int main() {
while (scanf("%d%d%d", &n, &m, &L) != EOF) {
int u, v, w;
arr.init(n);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w);
u--, v--;
arr.AddEdge(u, v, w);
}
ll ans = 0;
memset(s, -1, sizeof(s));
for (int i = 0; i < n; i++) {
arr.dijkstra(i, -100);
ll sum = 0;
for (int j = 0; j < n; j++) {
if (arr.d[j] == INF)
arr.d[j] = L;
sum += arr.d[j];
pre[j] = arr.p[j];
}
A[i] = sum;
ans += sum;
for (int j = 0; j < n; j++) {
if (j == i || pre[j] == -1)
continue;
ll tmp = 0;
arr.dijkstra(i, pre[j]);
for (int k = 0; k < n; k++) {
if (arr.d[k] == INF)
arr.d[k] = L;
tmp += arr.d[k];
}
s[pre[j]/2][i] = tmp;
}
}
ll Max = 0;
for (int i = 0; i < m; i++) {
ll sum = 0;
for (int j = 0; j < n; j++)
if (s[i][j] == -1)
sum += A[j];
else sum += s[i][j];
Max = max(Max, sum);
}
printf("%lld %lld\n", ans, Max);
}
return 0;
}
最新文章
- Divide and conquer:Moo University - Financial Aid(POJ 2010)
- Final-阶段站立会议2
- VirtualBox安装Ubuntu教程
- servlet filter可以用注解
- Java 图形编程 二:布局管理器之边界布局
- XML 实体扩展攻击
- iOS编程修改系统音量
- MVC5中使用SignalR2.0实现实时聊天室
- JDBC第二篇--【PreparedStatment、批处理、处理二进制、自动主键、调用存储过程、函数】
- navicat的简单使用
- 第2次作业:Wechat创作史
- axios传参
- 20175316盛茂淞 2018-2019-2 《Java程序设计》第2周学习总结
- Bisecting KMeans (二分K均值)算法讲解及实现
- 机器学习之Apriori算法和FP-growth算法
- Lerning Entity Framework 6 ------ Defining Relationships
- Executors多线程
- DD_belatedPNG
- vault key 管理工具
- 【Head First Servlets and JSP】笔记2:MVC迷你教程