HDU 5385 The path-蒲公英云

HDU 5385 The path

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

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

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

// 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;
}