poj 3160 Father Christmas flymouse（强连通缩点+最长路）

题目地址：http://poj.org/PRoblem?id=3160

思路：将所有点权值为负数的点设为0,，同一强连通分量中的点可全部选择，因此将其看做一点。在新图中求最长路径即可。最长路径：由于为给定起点，（1）从所有入度为0的点开始，进行DFS；（2）设置一虚拟节点，将其与入度为0的点相连，SPFA求最长路径。

SPFA版

#include<cstdio>#include<vector>#include<queue>#include<cstring>#include<iostream>#include<algorithm>using  namespace std;const int  maxn=30000+50;const int maxm=150000+50;const int INF=0x3f3f3f3f;struct Node{    int x,y;};queue<int> q;Node e[maxm];int all,n,m,top,cnt;int s[100000],d[maxn];int vw[maxn],v[maxn];int vis[maxn],sc[maxn];int dfn[maxn],low[maxn];int scvw[maxn],dist[maxn];vector<int> g[maxn],scg[maxn];void init(){    top=all=cnt=0;    memset(s,0,sizeof(s));    memset(d,0,sizeof(d));    memset(sc,0,sizeof(sc));    memset(vis,0,sizeof(vis));    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(scvw,0,sizeof(scvw));    for(int i=1; i<=n; i++) g[i].clear(),scg[i].clear();}void Tarjan(int u){    all++,dfn[u]=low[u]=all;    top++,s[top]=u,vis[u]=1;    for(int i=0; i<g[u].size(); i++)    {        int nt=g[u][i];        if(!dfn[nt])        {            Tarjan(nt);            low[u]=min(low[u],low[nt]);        }        else        {            if(vis[nt])                low[u]=min(low[u],dfn[nt]);        }    }    if(low[u]==dfn[u])    {        cnt++;        while(s[top+1]!=u)        {            sc[s[top]]=cnt;            vis[s[top]]=0;            top--;        }    }}int SPFA(int s){    memset(v,0,sizeof(v));    while(!q.empty()) q.pop();    for(int i=1;i<=cnt;i++) dist[i]=-INF;    v[s]=1,q.push(s),dist[s]=0;    while(!q.empty())    {        int now=q.front();        q.pop(),v[now]=0;        for(int i=0;i<scg[now].size();i++)        {            int nt=scg[now][i];            if(dist[nt]<dist[now]+scvw[nt])            {                dist[nt]=dist[now]+scvw[nt];                if(!v[nt])                {                    v[nt]=1;                    q.push(nt);                }            }        }    }    int ans=-INF;    for(int i=1;i<=cnt;i++) ans=max(ans,dist[i]);    return ans;}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        init();        for(int i=1; i<=n; i++) scanf("%d",&vw[i]);        for(int i=0; i<m; i++)        {            int x,y;            scanf("%d%d",&x,&y);            x++,y++;            e[i].x=x,e[i].y=y;            g[x].push_back(y);        }        for(int i=1; i<=n; i++)            if(!dfn[i]) Tarjan(i);        for(int i=1; i<=n; i++)            scvw[sc[i]]+=(vw[i]>0?vw[i]:0);        for(int i=0; i<m; i++)        {            int x=sc[e[i].x],y=sc[e[i].y];            if(x!=y)            {                d[y]++;                scg[x].push_back(y);            }        }        for(int i=1; i<=cnt; i++)        {            if(!d[i]) scg[0].push_back(i);        }        printf("%d/n",SPFA(0));    }    return 0;}DFS版
#include<cstdio>#include<vector>#include<cstring>#include<iostream>#include<algorithm>using  namespace std;const int  maxn=30000+50;const int maxm=150000+50;const int INF=0x3f3f3f3f;struct Node{    int x,y;};int ans;Node e[maxm];int all,n,m,top,cnt;int s[100000],d[maxn];int vw[maxn],v[maxn];int vis[maxn],sc[maxn];int dfn[maxn],low[maxn];int scvw[maxn],dist[maxn];vector<int> g[maxn],scg[maxn];void init(){    ans=-INF;    top=all=cnt=0;    memset(s,0,sizeof(s));    memset(d,0,sizeof(d));    memset(sc,0,sizeof(sc));    memset(vis,0,sizeof(vis));    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(scvw,0,sizeof(scvw));    for(int i=1; i<=n; i++) g[i].clear(),scg[i].clear();}void Tarjan(int u){    all++,dfn[u]=low[u]=all;    top++,s[top]=u,vis[u]=1;    for(int i=0; i<g[u].size(); i++)    {        int nt=g[u][i];        if(!dfn[nt])        {            Tarjan(nt);            low[u]=min(low[u],low[nt]);        }        else        {            if(vis[nt])                low[u]=min(low[u],dfn[nt]);        }    }    if(low[u]==dfn[u])    {        cnt++;        while(s[top+1]!=u)        {            sc[s[top]]=cnt;            vis[s[top]]=0;            top--;        }    }}int dfs(int u,int tmp){    int maxx=tmp;    for(int i=0;i<scg[u].size();i++)    {        int nt=scg[u][i];        maxx=max(maxx,dfs(nt,tmp+scvw[nt]));    }    return maxx;}int main(){    while(scanf("%d%d",&n,&m)!=EOF)    {        init();        for(int i=1; i<=n; i++) scanf("%d",&vw[i]);        for(int i=0; i<m; i++)        {            int x,y;            scanf("%d%d",&x,&y);            x++,y++;            e[i].x=x,e[i].y=y;            g[x].push_back(y);        }        for(int i=1; i<=n; i++)            if(!dfn[i]) Tarjan(i);        for(int i=1; i<=n; i++)        {            scvw[sc[i]]+=(vw[i]>0?vw[i]:0);            ans=max(ans,scvw[sc[i]]);        }        for(int i=0; i<m; i++)        {            int x=sc[e[i].x],y=sc[e[i].y];            if(x!=y)            {                d[y]++;                scg[x].push_back(y);            }        }        for(int i=1; i<=cnt; i++)        {            if(!d[i]) ans=max(ans,dfs(i,scvw[i]));        }        printf("%d/n",ans);    }    return 0;}