Loading...

洛谷P1073 最优贸易

check评论:0 条 remove_red_eye浏览量:364 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-10-09

qwq,一道还行的图论

我用的是分层图的方法

因为只能买一次,并且买了为了不亏一定要卖,我们将图分为三层,同层的边权为$0$,第一层到第二层边权为负,代表买入,第二层到第三层为正,代表卖出,我们再设置一个超级汇点,将第一层和第三层的终点连入,最后跑$spfa$最长路就可以了qwq

#include <bits/stdc++.h>
using namespace std;
int head[300010],dis[300010],vis[300010],a[100010];
int n,m,cnt;
struct edge
{
    int next,to,dis;
}e[3000010];
void add(int u,int v,int dis)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].dis=dis;
    head[u]=cnt;
}
int t;
void spfa()
{
    fill(dis+1,dis+(n<<1)+n+1,-0x3f3f3f3f);
    queue<int> q;
    q.push(1);
    vis[1]=1;
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]<dis[u]+e[i].dis)
            {
                dis[v]=dis[u]+e[i].dis;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    t=n+(n<<1)+1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,opt;
        scanf("%d%d%d",&x,&y,&opt);
        if(opt==1)
        {
            add(x,y,0);
            add(x,y+n,-a[x]);
            add(x+n,y+n,0);
            add(x+n,y+(n<<1),a[x]);
            add(x+(n<<1),y+(n<<1),0);
        }
        else
        {
            add(x,y,0);
            add(x,y+n,-a[x]);
            add(x+n,y+(n<<1),a[x]);
            add(y,x,0);
            add(y,x+n,-a[y]);
            add(y+n,x+(n<<1),a[y]);
            add(x+n,y+n,0);
            add(y+n,x+n,0);
            add(y+(n<<1),x+(n<<1),0);
            add(x+(n<<1),y+(n<<1),0);
        }
    }
    add(n,t,0);
    add(n+(n<<1),t,0);
    spfa();
    cout<<(max(0,dis[t]));
}

chevron_left POJ 1741 Tree

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名