?id=1179 (题目链接)
题意：给出一张有向图，每个节点有点权。标记一些点，找出一条路径，可以重复经过一条边，使得总点权和最大。重复经过一个点不能重复算点权。
Solution
今日考试题，，Dijkstra不幸Gi烂。
WARNING：Dijkstra处理最长路时会出现一些不好的情况，所以千万不要用！！
既然可以重复经过一些边，那么一旦经过了某个环，我们一定可以把环上所有的点跑遍，所以做法就很显然了。先Tarjan缩点，所以整个图就变成有向无环图，跑DP或者SPFA最长路即可。
代码：
// bzoj1179 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define LL long long #define inf 2147483640 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std; const int maxn=500010; struct data { int num,x; friend bool operator < (const data &x,const data &y) { return x.x<y.x; } }; struct edge {int to,next;}e[maxn<<1]; struct E {int u,v;}ee[maxn]; int dis[maxn],head[maxn],dfn[maxn],low[maxn],st[maxn],vis[maxn],pos[maxn],a[maxn],w[maxn],ll[maxn]; int n,m,top,sum,cnt,S,ind,p; void link(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; } void Tarjan(int x) { dfn[x]=low[x]=++ind; vis[x]=1; st[++top]=x; for (int i=head[x];i;i=e[i].next) { if (!vis[e[i].to]) { Tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); } else if (!pos[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); } if (dfn[x]==low[x]) { sum++; int j; do { j=st[top--]; pos[j]=sum;w[sum]+=a[j]; }while (st[top+1]!=x); } } void Dijkstra() { priority_queue<data> q; for (int i=1;i<=sum;i++) dis[i]=-inf; data y,x=(data){S,w[S]}; q.push(x);dis[S]=w[S]; while (q.size()) { x=q.top();q.pop(); if (vis[x.num]) continue; vis[x.num]=1; for (int i=head[x.num];i;i=e[i].next) if (dis[e[i].to]<dis[x.num]+w[e[i].to]) { dis[e[i].to]=y.x=dis[x.num]+w[e[i].to]; y.num=e[i].to; q.push(y); } } } void SPFA() { queue<int> q; for (int i=1;i<=sum;i++) dis[i]=-inf; q.push(S);dis[S]=w[S]; while (q.size()) { int x=q.front();q.pop(); vis[x]=0; for (int i=head[x];i;i=e[i].next) if (dis[e[i].to]<dis[x]+w[e[i].to]) { dis[e[i].to]=dis[x]+w[e[i].to]; if (!vis[e[i].to]) q.push(e[i].to); } } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d",&ee[i].u,&ee[i].v); link(ee[i].u,ee[i].v); } for (int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d%d",&S,&p); Tarjan(S);S=pos[S]; for (int x,i=1;i<=p;i++) { scanf("%d",&x); ll[pos[x]]=1; } for (int i=1;i<=n;i++) vis[i]=head[i]=0; for (int i=1;i<=m;i++) if (pos[ee[i].u]!=pos[ee[i].v]) link(pos[ee[i].u],pos[ee[i].v]); //Dijkstra(); 万万不可 SPFA(); int ans=0; for (int i=1;i<=sum;i++) if (ll[i]) ans=max(ans,dis[i]); printf("%d",ans); return 0; }
【bzoj1179】 Apio2009—Atm