zcmimi's blog
avatar
zc
2020-04-24 22:28:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i(x);i<=y;++i)
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
#define Fl(i,x) for(int i(Head[x]),to;to=e[i].to,i;i=e[i].nxt)
void cmin(int &x,int y){if(x>y)x=y;}
void cmax(int &x,int y){if(x<y)x=y;}
const int N=80011;
int n,m,cnt,ans,head[N],Head[N],bl[N],c[N],f[N];
struct edge{
    int x,to,nxt,w;
    double k;
}e[200011];
void add(int x,int y,int w,double k){
    e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;e[cnt].w=w,e[cnt].k=k;e[cnt].x=x;
}
void addd(int x,int y,int w){
    e[++cnt].to=y;e[cnt].nxt=Head[x];Head[x]=cnt;e[cnt].w=w;
}
int dfn[N],low[N],sz,q[N*2],tp,id=1;
bool v[N];
void tarjan(int x){
    dfn[x]=low[x]=++sz;
    v[x]=1;q[++tp]=x;
    fl(i,x)
    if(!dfn[to])tarjan(to),cmin(low[x],low[to]);
    else if(v[to])cmin(low[x],dfn[to]);
    if(low[x]==dfn[x]){
        ++id;
        while(int k=q[tp--]){
            bl[k]=id,v[k]=0;
            if(k==x){++id;break;}
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int x,y,w,h=0,t=1;double k;
    fur(i,1,m)scanf("%d%d%d%lf",&x,&y,&w,&k),add(x,y,w,k);
    fur(i,1,n)if(!dfn[i])tarjan(i);
    cnt=0;
    fur(i,1,m){
        x=bl[e[i].x],y=bl[e[i].to];
        if(x==y){
            w=e[i].w;
            while(w){
                c[x]+=w;
                w=int(w*e[i].k);
            }
        }
        else addd(x,y,e[i].w);
    }
    scanf("%d",&x);q[0]=x=bl[x];
    f[x]=c[x];
    while(h<t){
        v[x=q[h++]]=0;
        Fl(i,x)if(f[x]+e[i].w+c[to]>f[to]){
            f[to]=f[x]+e[i].w+c[to];
            if(!v[to])q[t++]=to,v[to]=1;
        }
    }
    fur(i,1,id)cmax(ans,f[i]);
    printf("%d\n",ans);
}
LG 2656 采蘑菇
comment评论
Search
search