-
题意
一个 \(N\) 个点 \(M\) 条边的带边权无向图，要求输出最小的 \(V\) 使得不管去掉哪一条边，都存在从 \(1\) 到 \(n\) 的路径使得边权和不超过 \(V\) 。
-
思路
感觉朴素不太好做，考虑二分。
对于一个二分值，即要判断在关于这个值的生成图中， \(1\) 和 \(n\) 在不在一个边双里。考虑怎么判断一条边要不要加入生成图。现在的主要问题是如何生成这个图。
给出结论：我们的生成图应该有且仅有所有长度不大于二分值的路径所含的边。等价性如下：
- 如果生成图符合边双条件，则断开一条边之后肯定存在一条路径。而如果不存在合法路径，那么可以推出所有路径都通过这条边，矛盾。故可以推出原图符合边双条件。
- 如果原图符合边双条件，则这个边双一定也在生成图中。
而要维护生成图，我们只需要对起点和终点各跑一次最短路就好了。
复杂度 \(O(N^2+M\log{NV})\)
实现：
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read( T &r )
{
r=0; bool w = false; char ch=getchar();
while( ch <'0' || ch>'9' ) w=!(ch^45),ch=getchar();
while( ch >='0' && ch <='9' ) r = (r<<1) + (r<<3) + (ch^48), ch=getchar();
r=w?-r:r;
}
#define MAXN 1000
int n,m;
int w[MAXN+5][MAXN+5];
int dist[2][MAXN+5];
bool vis[MAXN+5];
void dijkstra( int s , int t )
{
memset(dist[t],0x3f,sizeof(dist[t]));
memset(vis,0,sizeof(vis));
dist[t][s] = 0;
vis[s] = true;
for(int i=1;i<=n;i++) if( !vis[i] )
dist[t][i] = min(dist[t][i], dist[t][s] + w[s][i]);
while( true )
{
int tmp = 0;
for(int i=2;i<=n;i++) if( !vis[i] )
{
if( dist[t][tmp] > dist[t][i] )
tmp = i;
}
if( !tmp ) break;
vis[tmp] = true;
for(int j=1;j<=n;j++) if( !vis[j] )
dist[t][j] = min(dist[t][j], dist[t][tmp] + w[tmp][j]);
}
}
struct node
{
int to,nxt;
}edg[MAXN*MAXN+5];
int head[MAXN+5],edg_num;
void add( int u , int v )
{
++edg_num;
edg[edg_num].to = v;
edg[edg_num].nxt = head[u];
head[u] = edg_num;
}
int dfn[MAXN+5],low[MAXN+5],col[MAXN+5],cnum;
int st[MAXN+5];
void tarjan( int u , int fa )
{
dfn[u] = low[u] = ++dfn[0];
st[++st[0]] = u;
for(int i=head[u],v;i;i=edg[i].nxt) if( (v=edg[i].to) != fa )
{
if( !dfn[v] )
{
tarjan(v,u);
low[u] = min(low[v],low[u]);
}
low[u] = min(low[u],dfn[v]);
}
if( dfn[u] == low[u] )
{
++cnum;
int tmp;
do
{
tmp = st[st[0]--];
col[tmp] = cnum;
}
while( tmp != u );
}
}
bool check( int V )
{
memset(head,0,sizeof(head));edg_num=0;
st[0]=0;
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if( min(1ll*dist[0][i] + w[i][j] + dist[1][j],1ll*dist[1][i]+w[i][j]+dist[0][j]) <= 1ll*V )
add(i,j),add(j,i);
}
tarjan(1,0);
return col[1] == col[n];
}
int main()
{
memset(w,0x3f,sizeof(w));
read(n),read(m);
for(int i=1;i<=m;i++)
{
int u,v;
read(u),read(v);
read(w[u][v]), w[v][u] = w[u][v];
}
dijkstra(1,0);
dijkstra(n,1);
int l=1, r=(n-1)*1000, ans=r+1;
while( l <= r )
{
int mid=l+r>>1;
if( check(mid) )
ans = mid, r = mid-1;
else l = mid+1;
}
printf("%d",ans);
return 0;
}