Any questions?
Reply Back New Topic
View Topic

最优贸易【题解】


本题应该不止一种方法

(因为我自己就想到了俩)

方法一:重新建图+最长路

对于每座城市来说,有三种状态:

 1.啥也没做呢
 2.买了,但没卖
 3.已卖

因为需要已买一个球且仍未卖出时,才能卖出,所以上述三个状态有先后顺序。

由此,把每座城市分裂成三个点,分别代表上述三种状态。对于原图中有向边,重新建边为

1.,代表经过X城市时没球,也不买球,并到了Y城市。

2.,同理。

3.,同理。

4.,代表在X城市购入了球。

5.,代表在X城市卖出了球。

然后因为要求最大收益,所以SPFA跑一遍最长路即可。

代码:

//Copyright@3_soon,From Hangzhou No.2 High School Baimahu
//Problem:
//Result:

#include<bits/stdc++.h>
using namespace std;
#define re register
#define LL long long
#define DB double
#define il inline
#define For(x,a,b) for(re int x=a;x<=b;x++)
#define For2(x,a,b) for(re int x=a;x>=b;x--)
#define LFor(x,a,b) for(re LL x=a;x<=b;x++)
#define LFor2(x,a,b) for(re LL x=a;x>=b;x--)
#define Abs(x) ((x>0)? x:-x)
#define INF (2000000000)
int gi()
{
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
LL gl()
{
    LL res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
    if(ch=='-') fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
int n,m;
int head[300005],tot;
struct pp{int to,nxt,cap;}e[5000005];
int dis[300005],c[300005];
void addedge(int x,int y,int z){e[++tot]=(pp){y,head[x],z};head[x]=tot;}
queue<int>q;
bool vis[300005];
void spfa(int S)
{
    For(i,1,3*n+1) dis[i]=-INF;
    memset(vis,0,sizeof(vis));
    dis[S]=0;
    q.push(S);
    vis[S]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=0;
        for(int i=head[x];i!=-1;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dis[y]<dis[x]+e[i].cap)
            {
                dis[y]=dis[x]+e[i].cap;
                if(vis[y]==0)
                {
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
}
int p[100005];
void add(int x,int y)
{
    addedge(x,y,0);addedge(n+x,n+y,0);addedge(2*n+x,2*n+y,0);
    addedge(x,n+x,-p[x]);addedge(n+x,2*n+x,p[x]);
}

int main()
{
    memset(head,-1,sizeof(head));
    tot=0;
    re int x,y,z;
    n=gi(),m=gi();
    For(i,1,n) p[i]=gi();
    For(i,1,m)
    {
        x=gi(),y=gi(),z=gi();
        if(z==1) add(x,y);
        else{add(x,y);add(y,x); }
    }
    addedge(n,n*3+1,0);addedge(n*3,n*3+1,0);
    spfa(1);
    printf("%d\n",dis[n*3+1]);
    return 0;
}

方法二:Tarjan缩点+拓扑排序

缩点后,对每个连通分量记录他的最小值和最大值。此时就只剩个DAG了,再跑遍拓扑排序,边做边更新答案即可。