题解 P1948 【[USACO08JAN]电话线Telephone Lines】

· · 题解

本题有两种做法，二分+bfs和分层图最短路

二分的已经很多人讲了，这里主要讲分层图最短路。

分层图就是把图中节点分开，变成许多不同的状态。

本题可以仿照动态规划的思想，用D[x,p]表示1号到x号图中已经指定了p条免费电缆是，最贵的经过的电缆最小是多少。若有一条从x到y长度为z的无向边，应该用max(D[x,p],z)更新D[y,p]的最小值，用D[x,p]更新D[y,p+1]的最小值。

很显然这种做法是有有效性的，但是，我们可以用spfa或dij来跑一遍，使得D数组不能更新。这样也解决了后效性。用spfa来做时间复杂度为 O(tNP)，其中t为常数。这道题没有卡spfa。

代码

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1001;
const int M = 20001;
int n,m,k;
struct EDGE{
    int next;
    int to;
    int len;
}edge[M];
struct NODE{
    int pos;
    int free;
};
queue <NODE> q;
int head[N];
bool vis[N][N];
int cnt = 0;
int dist[N][N];
void add_edge(int x,int y,int len)
{
    edge[++cnt].to = y;
    edge[cnt].len = len;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
void spfa()
{
    memset(dist,0x3f,sizeof dist);
    q.push((NODE){1,0});
    vis[1][0] = 1;
    dist[1][0] = 0;
    while(!q.empty())
    {
        NODE top = q.front();
        q.pop();
        vis[top.pos][top.free] = 0;
        for(int i=head[top.pos];i;i=edge[i].next)
        {
            int y = edge[i].to;
            if(max(dist[top.pos][top.free],edge[i].len) < dist[y][top.free])
            {
                dist[y][top.free] = max(dist[top.pos][top.free],edge[i].len);
                if(!vis[y][top.free])
                {
                    vis[y][top.free] = 1;
                    q.push((NODE){y,top.free});
                }
            }

            if(top.free < k && dist[y][top.free+1] > dist[top.pos][top.free])
            {
                dist[y][top.free+1] = dist[top.pos][top.free];
                if(!vis[y][top.free+1])
                {
                    q.push((NODE){y,top.free+1});
                    vis[y][top.free+1] = 1;
                }
            }
        }
    }

}

// dist[next][top.free] --> max(dist[top.pos][top.free] , edge[i].len
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int x,y,l;
        scanf("%d%d%d",&x,&y,&l);
        add_edge(x,y,l);   //无向图加条边
        add_edge(y,x,l);
    }
    spfa();
    if(dist[n][k] == 0x3f3f3f3f)
        printf("-1\n");
    else
        printf("%d\n",dist[n][k]);
}

以上内容部分借鉴与算法竞赛进阶指南。