怎么样搭建qq号网站,用python做的大型网站,建立网站的市场价格,汽车创意logo设计题意#xff1a;一张有向图#xff0c;每条边上都有wi个蘑菇#xff0c;第i次经过这条边能够采到w-(i-1)*i/2个蘑菇#xff0c;直到它为0。问最多能在这张图上采多少个蘑菇。 分析#xff1a;在一个强连通分量内#xff0c;边可以无限次地走直到该连通块内蘑菇被采完为止…题意一张有向图每条边上都有wi个蘑菇第i次经过这条边能够采到w-(i-1)*i/2个蘑菇直到它为0。问最多能在这张图上采多少个蘑菇。 分析在一个强连通分量内边可以无限次地走直到该连通块内蘑菇被采完为止因此每个强连通分量内的结果是确定的。 设一条边权值为w最大走过次数为t解一元二次方程得 t (int)(1sqrt(18w))则该边对所在连通块的贡献为w*t - (t-1)*t*(t1)/6。 而不在任何一个强连通分量内的边最多只能走一次。所以在缩点后的DAG上进行dp即可。 #includebits/stdc.h
using namespace std;
typedef long long LL;
const int maxn 1e65;
struct Edge{int v,next;LL val;
}edges[maxn],E[maxn];
int head[maxn],tot,H[maxn],tt;
stackint S;
int pre[maxn],low[maxn],sccno[maxn],dfn,scc_cnt;
LL W[maxn];
LL dp[maxn];
void init()
{tot dfn scc_cnttt0;memset(H,-1,sizeof(H));memset(W,0,sizeof(W));memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));memset(sccno,0,sizeof(sccno));memset(head,-1,sizeof(head));
}void AddEdge(int u,int v,LL val) {edges[tot] (Edge){v,head[u],val};head[u] tot;
}void Tarjan(int u)
{int v;pre[u]low[u]dfn;S.push(u);for(int ihead[u];~i;iedges[i].next){v edges[i].v;if(!pre[v]){Tarjan(v);low[u]min(low[u],low[v]);}else if(!sccno[v]){low[u]min(low[u],pre[v]);}}if(pre[u]low[u]){int x;scc_cnt;for(;;){x S.top();S.pop();sccno[x]scc_cnt;if(xu)break;}}
}void nAddEdge(int u,int v,LL w)
{E[tt] (Edge){v,H[u],w};H[u] tt;
}LL dfs(int u)
{if(dp[u]) return dp[u];for(int iH[u];~i;iE[i].next){int v E[i].v;dp[u] max(dp[u],dfs(v)E[i].val);}dp[u]W[u];return dp[u];
}int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt,r,stdin);freopen(out.txt,w,stdout);#endifint N,M; while(scanf(%d%d,N,M)2){init();int st,u,v; LL w;while(M--){scanf(%d%d%lld,u,v,w);AddEdge(u,v,w);}scanf(%d,st);for(int i1;iN;i){if(!pre[i]){Tarjan(i);}}for(int u 1;uN;u){for(int i head[u];~i;i edges[i].next){v edges[i].v;LL w edges[i].val;if(sccno[u]!sccno[v]){nAddEdge(sccno[u],sccno[v],w);}else{int t (int)(1sqrt(18*w))/2;W[sccno[u]] (LL)t*w - (LL)(t-1)*t*(t1)/6;}}}for(int i1;iscc_cnt;i){if(!dp[i]){dfs(i);}}printf(%lld\n,dp[sccno[st]]);}return 0;
} 转载于:https://www.cnblogs.com/xiuwenli/p/9494938.html
