OI_problem 玛丽卡_洛谷P1186

• 题意

  一个 \(N\) 个点 \(M\) 条边的带边权无向图，要求输出最小的 \(V\) 使得不管去掉哪一条边，都存在从 \(1\) 到 \(n\) 的路径使得边权和不超过 \(V\) 。

• 思路

  感觉朴素不太好做，考虑二分。

  对于一个二分值，即要判断在关于这个值的生成图中， \(1\) 和 \(n\) 在不在一个边双里。考虑怎么判断一条边要不要加入生成图。现在的主要问题是如何生成这个图。

  给出结论：我们的生成图应该有且仅有所有长度不大于二分值的路径所含的边。等价性如下：

  1. 如果生成图符合边双条件，则断开一条边之后肯定存在一条路径。而如果不存在合法路径，那么可以推出所有路径都通过这条边，矛盾。故可以推出原图符合边双条件。
  2. 如果原图符合边双条件，则这个边双一定也在生成图中。

  而要维护生成图，我们只需要对起点和终点各跑一次最短路就好了。

  复杂度 \(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;
}