题目：
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值c‘最大。不连通两点的最短路长度视为L。（1<=n<=100,1<=m<=1000,1<=L<=10^8）
分析：
因为规模比较小，所以可以考虑删边。主要是删什么边的问题。
这里用到最短路树。在源点确定的情况下，只要最短路树不被破坏，起点到所有点的距离都不会改变。所以对于一个点，只有删掉最短路树上的边，我们才要重新做一次单源最短路。时间复杂度是O（n^2mlogn）。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 110
#define Maxm 1100
#define INF 100000000 struct node
{
int x,y,c,next;
int ans;
bool p;
}t[Maxm*];int len; int first[Maxn],dis[Maxn];
bool inq[Maxn];
bool hp[Maxn];
queue<int > q;
int n,m,L; void ins(int x,int y,int c)
{
t[++len].x=x;t[len].y=y;t[len].c=c;t[len].ans=;
t[len].next=first[x];first[x]=len;
} int mymax(int x,int y) {return x>y?x:y;} void spfa(int s,int l)
{
if(!q.empty()) q.pop();
memset(inq,,sizeof(inq));
memset(dis,,sizeof(dis));
memset(hp,,sizeof(hp));
q.push(s);dis[s]=;hp[s]=;inq[s]=;
while(!q.empty())
{
int x=q.front();inq[x]=;q.pop();
for(int i=first[x];i;i=t[i].next)
{
if(i==l) continue;
if(i==(l%==?l-:l+)) continue;
int y=t[i].y;hp[y]=;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y])
{
q.push(y);
inq[y]=;
}
}
}
}
} int ffind(int s)
{
int now=;
for(int i=;i<=n;i++) if(i!=s)
{
if(hp[i]) now+=dis[i];
else now+=L;
}
return now;
} int main()
{
while(scanf("%d%d%d",&n,&m,&L)!=EOF)
{
memset(first,,sizeof(first));
len=;
for(int i=;i<=m;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
int ft=;
for(int i=;i<=n;i++)
{
spfa(i,);int now=ffind(i);
ft+=now;
for(int j=;j<=len;j++) t[j].p=;
for(int j=;j<=len;j++)
{
if(dis[t[j].x]==dis[t[j].y]+t[j].c) t[j].p=t[j%==?j-:j+].p=;
}
for(int j=;j<=len;j++)
if(t[j].p)
{
spfa(i,j);
t[j].ans+=ffind(i);
}
else t[j].ans+=now;
}
int mx=ft;
for(int i=;i<=len;i++) mx=mymax(mx,t[i].ans);
printf("%d %d\n",ft,mx);
}
return ;
}
[UVA1416]
2016-04-05 14:04:01