首页 > 代码库 > 【POJ3272】Cow Traffic 拓扑DP
【POJ3272】Cow Traffic 拓扑DP
题意:给一个有向图,边严格由编号小的点到编号大的点,现在计数所有的极大路径,求每条边遍历次数的最大值。
题解:正着扫一遍,倒着扫一遍,dp值相乘。
#include <cstdio> #include <cstring> #include <algorithm> #define N 5050 #define M 50500 using namespace std; struct KSD { int v,next; long long cnt; }e[M],E[M]; int head[N],HEAD[N],cnt; int n,m; void add(int u,int v) { ++cnt; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; E[cnt].v=u; E[cnt].next=HEAD[v]; HEAD[v]=cnt; } long long f[N],g[N]; int id[N],od[N]; int main() { // freopen("test.in","r",stdin); int i,j; int a,b,v; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); add(a,b); id[b]++; od[a]++; } for(i=1;i<=n;i++) { if(!id[i])f[i]=1; if(!od[i])g[i]=1; } for(i=1;i<=n;i++) { for(j=head[i];j;j=e[j].next) { v=e[j].v; f[v]+=f[i]; e[j].cnt+=f[i]; } } for(j=n;j;j--) { for(i=HEAD[j];i;i=E[i].next) { v=E[i].v; g[v]+=g[j]; E[i].cnt+=g[j]; } } long long ans=0; for(i=1;i<=m;i++)ans=max(ans,e[i].cnt*E[i].cnt); printf("%lld\n",ans); return 0; }
【POJ3272】Cow Traffic 拓扑DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。