Luogu P1073 最优贸易【最短路/建反图】 By cellur925

这么经典的题目，还是看了lyd的题解....唉难过。

一句话题意：在一张点有全都的图上找一条从1到n的路径，存在两个点p,q(p<q),使val[q]-val[p]最大。

给出的图是既有双向又有单向的混合图，考虑像普通的方法一样建图。除此之外，再在一个新邻接表中建原图的反图（边方向相反）。

为什么要这样做？

考虑分别自起点到终点和自终点到起点遍历，计算出f[]和d[]，其中f[i]表示从1到i的路径中经过的最小的点权，d[i]表示从n到i的路径中经过的最大点权。（想一想，为什么？）

于是我们就可以枚举断点X,使d[x]-f[x]最大。保证了1能走到n，即路径的连贯（联通）性。

code

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #define maxn 100090

 #define maxm 500090 

 using namespace std;

 int n,m,totp,totn,ans;

 int headp[maxn],headn[maxn],val[maxn],f[maxn],d[maxn],vis[maxn];

 struct node{

     int to,next;

 };

 node edge_posi[maxm*],edge_nega[maxm*];

 void add_posi(int x,int y)

 {

     edge_posi[++totp].to=y;

     edge_posi[totp].next=headp[x];

     headp[x]=totp;

 }

 void add_nega(int x,int y)

 {

     edge_nega[++totn].to=y;

     edge_nega[totn].next=headn[x];

     headn[x]=totn;

 }

 void spfa_posi()

 {

     queue<int>q;

     memset(d,0x3f,sizeof(d));

     q.push();d[]=val[];vis[]=;

     while(!q.empty())

     {

         int x=q.front();

         q.pop();vis[x]=;

         for(int i=headp[x];i;i=edge_posi[i].next)

         {

             int y=edge_posi[i].to;

             if(min(d[x],val[y])<d[y])

             {

                 d[y]=min(d[x],val[y]);

                 if(!vis[y]) q.push(y),vis[y]=;

             }

         }

     }

 }

 void spfa_nega()

 {

     queue<int>q;

     memset(vis,,sizeof(vis));

     memset(f,,sizeof(f));

     q.push(n);d[n]=val[n];vis[n]=;

     while(!q.empty())

     {

         int x=q.front();

         q.pop();vis[x]=;

         for(int i=headn[x];i;i=edge_nega[i].next)

         {

             int y=edge_nega[i].to;

             if(max(f[x],val[y])>f[y])

             {

                 f[y]=max(f[x],val[y]);

                 if(!vis[y]) q.push(y),vis[y]=;

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d",&val[i]);

     for(int i=;i<=m;i++)

     {

         int x=,y=,opt=;

         scanf("%d%d%d",&x,&y,&opt);

         if(opt==)

         {

             add_posi(x,y);

             add_nega(y,x);

         }

         else if(opt==)

         {

             add_posi(x,y);add_posi(y,x);

             add_nega(y,x);add_nega(x,y);

         }

     }

     spfa_posi();

     spfa_nega();

     for(int i=;i<=n;i++)

         ans=max(ans,f[i]-d[i]);

     printf("%d",ans);

     return ;

 }

建反图的思想妙啊！

巴特西

Luogu P1073 最优贸易【最短路/建反图】 By cellur925

最新文章

热门文章