LP4610 [COCI2011-2012#7] KAMPANJA [最短路/搜索/DP]

Author Avatar
空気浮遊 2018年09月05日
  • 在其它设备中阅读本文章
  • dp
  • 最短路
  • 搜索
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

有向图

求路径 $1\rightarrow 2 \rightarrow 1$ 至少经过几个点

$n,m\leq 200$

Solution

解法 1:

选择直接爆搜到 2 点后跑 dijkstra
剪枝就是爆搜的点超过了 ans 之后就剪掉
显然是能被卡掉的辣(逃)

但把剪枝优化一下还是比较难卡哒

考虑求出 1 ->2->1 中 2 ->1 必须单独算的点的数目
即 1 ->2 的必经点不在 2 ->1 的必经点中

emmm... 支配树?

这个暴力算一下还是可以哒

解法 2(标算):

考虑 $w[i][j]$ 为 $i\rightarrow j$ 的最短路

$dp[i][j]$ 为 $1\rightarrow i\rightarrow j\rightarrow 1$ 至少经过多少点

转移:$dp[i][j]=min(dp[x][y]+w[y][j]+w[j][i]+w[i][x]-1)$

即新增的路径和被重复经过的点 $i$。

dijkstra 跑这个 dp 的话,是 $O(n^2\log n^2)$ 大概。

Code(未优化解法 1):

// Code by ajcxsu
// Problem: kampanja

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;

const int N=210, M=210;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
char vis[N];

int dist[N];
char S[N];
typedef pair<int, int> mpair;
int dij(int s, int t) {
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    CLR(S, 0), CLR(dist, 0x3f);
    dist[s]=0;
    pq.push(mpair(0, s));
    int na;
    while(!pq.empty()) {
        na=pq.top().second, pq.pop();
        if(S[na]) continue;
        S[na]=1;
        if(na==t) break;
        for(int u=h[na];u;u=nexp[u])
            if(!S[to[u]] && dist[to[u]]>dist[na]+(!vis[to[u]]))
                dist[to[u]]=dist[na]+(!vis[to[u]]), pq.push(mpair(dist[to[u]], to[u]));
    }
    return dist[t];
}
int ans=0x3f3f3f3f, nlen;
void dfs(int x, int k) {
    if(k>=ans) return;
    vis[x]=1;
    if(x==2) {
        ans=min(ans, dij(2, 1)+k);
        vis[x]=0;
        return;
    }
    for(int u=h[x];u;u=nexp[u])
        if(!vis[to[u]]) dfs(to[u], k+1);
    vis[x]=0;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) cin>>u>>v, ins(u, v);
    dfs(1, 1);
    cout<<ans<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol-luogu-4610.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material