完整版网站推广方案,网站建设苏州,网页制作的过程,入侵WordPress网站正题
评测记录#xff1a; https://www.luogu.org/recordnew/lists?uid52918pidP3387 大意
一个有向图。每个点有权值#xff0c;但每个值只能取一次#xff0c;每条边可以重复走#xff0c;求一条路径使值最大。 解题思路
用tarjan求出每一个强联通分量#xf…正题
评测记录 https://www.luogu.org/recordnew/lists?uid52918pidP3387 大意
一个有向图。每个点有权值但每个值只能取一次每条边可以重复走求一条路径使值最大。 解题思路
用tarjan求出每一个强联通分量然后将每个强联通分量缩成一个点这样这个图就变成了一个有向无环图然后就可以按广度优先遍历进行dp了。 代码
#includecstdio
#includestack
#includequeue
#includecstring
#define N 10000
#define M 100000
using namespace std;
stackint Stack;
queueint q;
struct line{int to,from,next;
}a[M];
int n,m,x,y,tot,in[N],ls[N],fl[N],cost[N],f[N],maxs,low[N],dfn[N],top,num,gt[N],an[N];
bool ins[N],v[N];
void addl(int x,int y,int tot)
{a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;
}
void tarjan(int x)
{ins[x]true;dfn[x]low[x]top;Stack.push(x);for (int ils[x];i;ia[i].next)if (!dfn[a[i].to]){tarjan(a[i].to);low[x]min(low[x],low[a[i].to]);}else if (ins[a[i].to])low[x]min(low[x],dfn[a[i].to]);if (low[x]dfn[x]){while (Stack.top()!x){int yStack.top();fl[y]x;an[x]cost[y];//计算强联通权值和Stack.pop();ins[y]0;}fl[x]x;an[x]cost[x];//计算强联通权值和ins[x]0;Stack.pop();}
}
void bfs()
{while (!q.empty()){int xq.front();q.pop();for (int ils[x];i;ia[i].next){int ya[i].to;f[y]max(f[y],f[x]an[y]);//dpmaxsmax(maxs,f[y]);//求最大值if (!v[y]){q.push(y);v[y]false;}}}
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i) scanf(%d,cost[i]);for (int i1;im;i){scanf(%d%d,x,y);addl(x,y,i);//加边}for (int i1;in;i)if (!dfn[i])tarjan(i);//求强联通memset(ls,0,sizeof(ls));//去除所有的边的连通保留值的for (int i1;im;i){xa[i].from;ya[i].to;if (fl[x]!fl[y])//不在强联通中{tot;addl(fl[x],fl[y],tot);//连边in[fl[y]];//统计入度}}for (int i1;in;i)if (fl[i]i!in[i])//加入队列{q.push(i);v[i]true;f[i]an[i];maxsmax(maxs,f[i]);}bfs();printf(%d,maxs);
}
