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

ajcxsu
ajcxsu 2018年09月05日
  • 32 次阅读

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://acxblog.site/archives/sol-luogu-4610.html
本文采用 CC BY-NC-SA 3.0 协议进行许可