HDU4694 未AC

mark一下，免得忘了，估计是题意理解错了，写成了双连通分量，估计是单向边。

未AC的代码，用的双连通分量。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<iostream>

using namespace std;

#define ForEdge(i,u)  for(int i=head[u];i!=-1;i=edge[i].next)
#define For(i,forN) for(int i=0;i<forN;i++)
#define sf  scanf
#define pf  printf
#define mp  make_pair

#define _clr(x,y)   memset(x,(y),sizeof(x))

const int Maxn=51000*2,Maxe=101000*2*2;

struct Edge
{
    int to,next;
    bool bvis;
}edge[Maxe];
int head[Maxn],etot;
vector < int > Scc[Maxn];
int n,m;

inline void add_edge(int u,int v)
{
    edge[etot].to=v;
    edge[etot].next=head[u];
    edge[etot].bvis=false;
    head[u]=etot++;
   // cout<<u<<" to "<<v<<endl;
}

void init_edge()
{
    etot=0; _clr(head,-1);
}

bool vis[Maxn];
int scc,dfsn[Maxn],low[Maxn],vtime,stk[Maxn],top,bleg[Maxn];

void tjdfs(int u)
{
    vis[u]=true;    stk[top++]=u;
    low[u]=dfsn[u]=vtime++;
    ForEdge(i,u)
    {
        if(edge[i].bvis)    continue;
        edge[i].bvis=edge[i^1].bvis=true;
        int v=edge[i].to;
        if(!vis[v])
        {
            tjdfs(v);
            low[u]=min(low[u],low[v]);
        }
        else if(bleg[v]==-1)
            low[u]=min(dfsn[v],low[u]);
    }
    if(dfsn[u]==low[u])
    {
        Scc[scc].clear();
        do
        {
            bleg[stk[--top]]=scc;
            Scc[scc].push_back(stk[top]);
        }while(stk[top]!=u);
        scc++;
    }
}

void tarjan()
{
    _clr(vis,false);    _clr(bleg,-1);
    scc=vtime=top=0;
    for(int i=1;i<=n;i++)
    if(!vis[i])
    tjdfs(i);
}

void buildMoreEdge()
{
    for(int i=1;i<=n;i++)
    {
        ForEdge(j,i)
        {
            int v=edge[j].to;
            if(bleg[i]!=bleg[v])
            {
                add_edge(bleg[i],bleg[v]);
                add_edge(bleg[v],bleg[i]);
            }
        }
    }
}

int Ans[Maxn];

void debug()
{
    /*
    for(int i=1;i<=n;i++)
    cout<<bleg[i]<<" ";cout<<endl;
    for(int i=1;i<=n;i++)
    cout<<low[i]<<" ";cout<<endl;
    */
}

void solve()
{
    tarjan(); //缩点，找到在同一爽连通分支的点。
    debug();
    _clr(vis,false);    _clr(Ans,0);
    queue < int > q;
    q.push(n);  Ans[n]=n;    vis[n]=true;
    while(!q.empty())
    {
        int u=q.front();    q.pop();
        //对于同一连通分支的点，他们的重要节点都是u，因为从n开始必须先到u再到v。
        //假设还存在另外一点z，使得n先到z再到v，那么z，n，u，v必然属于同一连通分支。
        for(int i=0;i<Scc[bleg[u]].size();i++)
        {
            int v=Scc[bleg[u]][i];
            if(v==u)    continue;
            Ans[v]=Ans[u]+v;
            vis[v]=true;
        }
        for(int i=0;i<Scc[bleg[u]].size();i++)
        {
            int v=Scc[bleg[u]][i];
            ForEdge(j,v)
            {
                int vv=edge[j].to;
                if(!vis[vv])
                {
                    vis[vv]=true;
                    Ans[vv]=Ans[v]+vv;
                    q.push(vv);
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=1)    printf(" ");
        pf("%d",Ans[i]);
    }
    puts("");
}

pair < int ,int > e[Maxe];

int main()
{
    while(~sf("%d%d",&n,&m))
    {
        int u,v;
        For(i,m)    sf("%d%d",&e[i].first,&e[i].second);
        sort(e,e+m);
        int last=min(m,1);
        for(int i=1;i<m;i++)
        if(e[i]!=e[last-1])
            e[last++]=e[i];
        m=last;
        init_edge();
        For(i,m)    add_edge(e[i].first,e[i].second),add_edge(e[i].second,e[i].first);
        solve();
    }
    return 0;
}