题解 P2648 【赚钱】

2018-09-20 15:31:50


题目描述--->p2648 赚钱

分析就不讲了 qwq

之前 Created_equal1 大佬orz已经讲过了,只是来放一下加了超级源的代码

需要注意的一点

与暴力的不同的是, $dis[s]=0$

(即超级源处无城市,我们不能打工赚钱

ps: $dis[i]$ 的定义是到达i能赚的钱.

因此我们的 $ans$ 要取 $max$

$24ms$

-----------------代码------------------

#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 666
using namespace std;
IL void in(int &x)
{
    int f=1;x=0;char s=getchar();
    while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
    while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int head[N],tot,s,dis[N],cnt[N];
bool vis[N];
int n,m,f,D,ans;
struct cod{int u,v,w;}edge[N];
IL void add(int x,int y,int z)
{
    edge[++tot].u=head[x];
    edge[tot].v=y;
    edge[tot].w=z;
    head[x]=tot;
}
IL bool spfa(int s)
{
    vis[s]=true;dis[s]=0;cnt[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=false;
        if(cnt[u]>n+1)return true;
        for(RI i=head[u];i;i=edge[i].u)
        {
            if(dis[edge[i].v]<dis[u]-edge[i].w+D)
            {
                dis[edge[i].v]=dis[u]-edge[i].w+D;
                if(cnt[edge[i].v]>n+1)return true;
                if(!vis[edge[i].v])
                {
                    vis[edge[i].v]=true;
                    cnt[edge[i].v]++;
                    q.push(edge[i].v);
                }
            }
        }
    }
    for(RI i=1;i<=n;i++)
        ans=max(ans,dis[i]);
    return false;
}
int main()
{
    in(D),in(m),in(n),in(f);s=n+1;
    for(RI i=1,a,b;i<=m;i++)
    {
        in(a),in(b);
        add(a,b,0);
    }
    for(RI i=1,a,b,c;i<=f;i++)
    {
        in(a),in(b),in(c);
        add(a,b,c);
    }
    for(RI i=1;i<=n;i++)add(s,i,0),dis[i]=-2147483647;
    if(spfa(s)) puts("orz");
    else printf("%d",ans);
}