UVA1416 Warfare And Logistics
链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=36232
【题意】
给出一个无向图，定义C =∑(d[i][j]) ，其中d[][]表示两点间的最短距离，求出C并求出删除一条边后的最大C2。
【思路】
最短路树。
简单地想我们可以用floyd或SPFA求出两点间的最短距离，然后枚举删除m条边再次进行这项工作。
其实这里我们不用重新全部计算，因为如果所删除的边不在scr的最短路树上，那么这棵树不会被破坏。因此我们可以提前在求C的时候记录每一个scr最短路树上的边以及这棵最短路树的总权值，依旧枚举删边，判断是否需要重新计算即可。
理论上时间需要O(n^3)，实践中应该能跑O(n^2)。
需要注意的是有重边的时候应该用次短边代替。
【代码】
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = +,maxm=+;
const int INF=1e9;
struct Edge{
int u,v,w,next;
}; int n,m,L; struct SPFA{
int n;
Edge e[*maxm];
int en,front[maxn];
int inq[maxn],d[maxn];
int p[maxn];
queue<int> q; void init(int n){
this->n=n;
en=-;
memset(front,-,sizeof(front));
}
void AddEdge(int u,int v,int w) {
en++; e[en].u=u; e[en].v=v; e[en].w=w; e[en].next=front[u]; front[u]=en;
}
void solve(int s) {
memset(inq,,sizeof(inq));
memset(p,,sizeof(p));
for(int i=;i<=n;i++) d[i]=INF; d[s]=; inq[s]=; q.push(s);
while(!q.empty()) {
int u=q.front(); q.pop(); inq[u]=;
for(int i=front[u];i>=;i=e[i].next) {
int v=e[i].v,w=e[i].w;
if(w> && d[v]>d[u]+w) { //w<0表示此边已断
d[v]=d[u]+w;
p[v]=i;
if(!inq[v]) {
inq[v]=;
q.push(v);
}
}
}
}
}
}spfa; vector<int> gr[maxn][maxn]; //保存ij之间所有的边
int idx[maxn][maxn]; //边ij在SPFA中对应的编号
int used[maxn][maxn][maxn]; //used[scr][u][v]表示在scr为根的最短路树上边uv是否出现
int sum_single[maxn]; //scr的最短路树的d[]之和 int CALC_C() {
int ans=;
memset(used,,sizeof(used));
FOR(scr,,n)
{
spfa.solve(scr);
sum_single[scr]=;
FOR(v,,n)
{
if(v!=scr) {
int u=spfa.e[spfa.p[v]].u;
used[scr][u][v]=used[scr][v][u]=;
}
sum_single[scr] += spfa.d[v]==INF? L : spfa.d[v];
}
ans += sum_single[scr];
}
return ans;
}
int CALC_C2(int a,int b) {
int ans=;
FOR(scr,,n)
{
if(!used[scr][a][b]) ans+=sum_single[scr];
//如果边ij没有出现在i的最短路树上则无须重新计算
else
{
spfa.solve(scr);
FOR(v,,n) ans += spfa.d[v]==INF?L: spfa.d[v];
}
}
return ans;
} int main()
{
while(scanf("%d%d%d",&n,&m,&L)==) //==3 否则会TLE
{
int u,v,w;
spfa.init(n);
FOR(i,,n) FOR(j,,n) gr[i][j].clear();
while(m--) {
scanf("%d%d%d",&u,&v,&w);
gr[u][v].push_back(w);
gr[v][u].push_back(w);
}
FOR(i,,n) FOR(j,i+,n) if(!gr[i][j].empty()){
sort(gr[i][j].begin(),gr[i][j].end());
spfa.AddEdge(i,j,gr[i][j][]);
idx[i][j]=spfa.en;
spfa.AddEdge(j,i,gr[i][j][]);
idx[j][i]=spfa.en;
}
int c=CALC_C(),c2=-;
FOR(i,,n) FOR(j,i+,n) if(!gr[i][j].empty()){
int& e1=spfa.e[idx[i][j]].w;
int& e2=spfa.e[idx[j][i]].w;
if(gr[i][j].size()==) e1=e2=-;
else e1=e2=gr[i][j][]; //用次短边代替
c2=max(c2,CALC_C2(i,j)); //"删除" ij之间的边之后计算c2
e1=e2=gr[i][j][];
}
printf("%d %d\n",c,c2);
}
return ;
}