圖論-虛擬節點分層建圖

Nya圖最短路

題目鏈接:Virtual Judge Acwing

題意:
題解:\(a,b\)連一個\(w\)的邊,是正常操作,這里有一個重要操作是\(a\)層和\(a+1\)層能直接傳送,如果這里使用笨笨的建圖方式,那么時間復雜度就是\(O(n^2)\),時間復雜度太高,不太行.

這里有一個聰明的建圖方法--->虛擬節點分層建圖 具體表示為:將\(a\)層和\(a+1\)層中間建立一個虛擬節點,然后將\(a\)層的所以節點指向虛擬節點,然后虛擬節點指向\(a+1\)層,這樣就能實作在\(O(n)\)的時間復雜度情況下進行建圖,時間可以接受具體可以看圖: 示意圖

code

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-8
#define int128 __int128
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define debug(x...) do { cout<< #x <<" -> "; re_debug(x); } while (0)
void re_debug() { cout<<'\n'; }
template<class T, class... Ts> void re_debug(const T& arg,const Ts&... args) { cout<<arg<<" "; re_debug(args...); }
void cut(){ cout<<'\n'<<"------------"<<'\n';}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const int N=2e5*3;
int e[N],ne[N],h[N],idx;
int w[N];
int dist[N];
int n,m,c;
int t=1;
bool st[N];
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,1});
    dist[1]=0;
    while(q.size())
    {
        auto v=q.top().second;
        q.pop();
        if(st[v]) continue;
        st[v]=true;
        for(int i=h[v];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[v]+w[i])
            {
                dist[j]=dist[v]+w[i];
                q.push({dist[j],j});
                
            }
        }
    }
}
void solve()
{
    idx=0;//注意一定要清零
    scanf("%d%d%d",&n,&m,&c);
    for(int i=0;i<=n*3;i++)//用到了3n這些點
    {
        dist[i]=INF;
        st[i]=0;
        h[i]=-1;
    }
    vector<vector<int>> depth(n+1+1);
    int max_depth=-1;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        depth[x].push_back(i);
        max_depth=max(max_depth,x);
    }
    for(int i=1;i<max_depth;i++)
    {
        //這里用到了3*n以上的點,其實n--2n這一層是a層-->a+1層,2n--3n是a+1到a層,注意這是單向邊
        for(auto &t:depth[i]) add(t,n+i+1,c);//t層連到t+1層
        for(auto &t:depth[i+1]) add(n+i+1,t,0);/
        for(auto &t:depth[i]) add(2*n+i+1,t,0);
        for(auto &t:depth[i+1]) add(t,2*n+i+1,c);
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    if(dist[n]==INF) printf("Case #%d: %d\n",t++,-1);
    else printf("Case #%d: %lld\n",t++,dist[n]);
}
int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--) solve();
    return (0^0);
}

Slipper

杭電多校第四場第三題,其實這里就是n層能跳到n+k層了,那么其實就是板子了

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-8
#define int128 __int128
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a/gcd(a,b)*b
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define debug(x...) do { cout<< #x <<" -> "; re_debug(x); } while (0)
void re_debug() { cout<<'\n'; }
template<class T, class... Ts> void re_debug(const T& arg,const Ts&... args) { cout<<arg<<" "; re_debug(args...); }
void cut(){ cout<<'\n'<<"------------"<<'\n';}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> PII;
const int INF=0x3f3f3f3f;
const ll LNF=0x3f3f3f3f3f3f3f3fll;
const double PI=acos(-1.0);
const int N=2000010*4;
int e[N],ne[N],w[N],h[N],idx;
int depth[N];
ll dist[N];
bool st[N];
int n;
int max_depth=-1;
int s,t;
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int father)//處理出來這個深度
{
    depth[u]=depth[father]+1;
    max_depth=max(max_depth,depth[u]);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        dfs(j,u);
    }
}
void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dist[s]=0;
    q.push({0,s});
    while(q.size())
    {
        auto v=q.top().second;q.pop();
        if(st[v]) continue;
        st[v]=true;
        for(int i=h[v];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[v]+w[i])
            {
                dist[j]=dist[v]+w[i];
                q.push({dist[j],j});
            }
        }
    }
}
void solve()
{
    idx=0;
    cin>>n;
    for(int i=0;i<=n*3+10;i++)
    {
        h[i]=-1;
        dist[i]=LNF;
        st[i]=0;
    }
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    int k,p;
    cin>>k>>p;
    
    dfs(1,-1);
    vector<vector<int>> depths(max_depth+k+1);
    for(int i=1;i<=n;i++)
    {
        depths[depth[i]].push_back(i);
    }
    for(int i=1;i<=max_depth;i++)
    {
        for(auto &t:depths[i]) add(t,n+i+1,p);//t層連到t+k層
        for(auto &t:depths[i+k]) add(n+i+1,t,0);//注意不要重復
        for(auto &t:depths[i]) add(2*n+i+1,t,0);
        for(auto &t:depths[i+k]) add(t,2*n+i+1,p);
    }
    cin>>s>>t;
    dijkstra();
    if(dist[t]==LNF) cout<<"-1"<<'\n';
    else cout<<dist[t]<<'\n';
}
int main()
{
    IOS;
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0^0;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500770.html

標籤：其他

上一篇：「學習筆記」高斯消元

下一篇：主流定時任務解決方案全橫評