HDU 5385 The path

待我称王封你为后i 2022-08-04 00:47 2阅读 0赞

如果我们知道每个点的*d**i**s*值和最短路径树的话，方案是很容易构造的

我们可以采取贪心做法，一开始将1号点作为最短路径树的根，然后左边从2开始，右边从*n*开始，只要之前加入的点有边连向他们就加入

这样一个点加入的时间就是他的*d**i**s*值，最短路径树上的父亲也可以确定，于是输出时非树边长度为*n*，树边长度为两个端点*d**i**s*之差。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int MAXN=100010;
    
    set<int> st;
    int n,m;
    int vis[MAXN],cost[MAXN];
    struct Edge
    {
        int to,next;
    }e[MAXN<<1];
    int head[MAXN],tot;
    int fa[MAXN],dis[MAXN],idx[MAXN];
    
    void init()
    {
        CLR(fa,-1);CLR(head,-1);
        CLR(vis,0);CLR(cost,0);
        tot=0;st.clear();
    }
    
    void addedge(int u,int v)
    {
        e[tot].next=head[u];
        e[tot].to=v;
        head[u]=tot++;
    }
    
    int main()
    {
        int T;
        read(T);
        while(T--)
        {
            init();
            read(n),read(m);
            for(int i=0,u,v;i<m;i++)
            {
                read(u),read(v);
                  addedge(u,v);
            }
            int cnt=1;
            int now=1,l=1,r=n,v;
            fa[1]=1;dis[1]=0;
            while(cnt<n)
            {
                for(int i=head[now];~i;i=e[i].next)
                {
                    v=e[i].to;
                    if(fa[v]!=-1 || st.find(v)!=st.end()) continue;
                    fa[v]=now;idx[v]=i;
                    st.insert(v);
                }
                //cout<<" :"<<now<<endl;
                cnt++;
                int be=*st.begin();
                if(be==l+1)
                {
                    cost[idx[be]]=cnt-dis[fa[be]]-1;
                    dis[be]=cnt-1;
                    vis[idx[be]]=true;
                    st.erase(be);
                    l=now=be;
                    //cout<<"1:"<<be<<endl;
                }
                else
                {
                    be=*(st.rbegin());
                    cost[idx[be]]=cnt-dis[fa[be]]-1;
                    dis[be]=cnt-1;
                    vis[idx[be]]=true;
                    st.erase(be);
                    now=be;
                    //cout<<"2:"<<be<<endl;
                }
            }
            for(int i=0;i<m;i++)
                if(!vis[i])
                    printf("%d\n",n);
                else
                    printf("%d\n",cost[i]);    
        }
    
        return 0;
    }

换一种姿势，总体思路差不多

#include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<vector>
    #include<set>
    #define maxn 100008
    using namespace std;
    
    struct yyy
    {
        int x,m;
    };
    
    int ans[maxn];
    vector<yyy> g[maxn];
    set<int> s;
    int vis[maxn];
    int pre[maxn];
    int prej[maxn];
    
    int main()
    {
        int T;
        int n,m,i;
        scanf("%d",&T);
    
        while (T--)
        {
            scanf("%d%d",&n,&m);
            for (i = 1 ; i <= n ; i++)
            {
                g[i].clear();
                vis[i] = -1;
                pre[i] = 0;
                prej[i] = 0;
            }
    
            int x,y,cnt = 0;
    
            for (i = 1 ; i <= m ; i++)
            {
                ans[i] = n;
                scanf("%d%d",&x,&y);
                g[x].push_back( (yyy) {y,++cnt} );
            }
    
            int l = 1,r = n;
            int v;
            s.clear();
            s.insert(1);
            vis[1] = 0;
            int dis = -1;
    
            while ( !s.empty() )
            {
                int L = *s.begin(),R = *(--s.end());
               // cout<<L<<' '<<R<<endl;
    
                if (L == l)
                    x = L,l++;
                else x = R,r--;
                s.erase(x);
                dis++;
                if (x != 1)
                {
                    ans[pre[x]] = dis - vis[prej[x]];
    
                    vis[x] = dis;
                }
    
    
                for (i = 0 ; i < g[x].size() ; i++)
                    {
                        v = g[x][i].x;
                        if ( vis[v] == -1 )
                        {
                            vis[v] = 0;
                            pre[v] = g[x][i].m;
                            prej[v] = x;
                            s.insert(v);
                        }
                    }
    
            }
            for (i = 1 ; i <= m ; i++)
                printf("%d ",ans[i]);
            printf("\n");
    
        }
    
    
        return 0;
    }