H - transaction transaction transaction

https://vjudge.net/contest/184514#problem/H

题意：

一个商人为了赚钱，在城市之间倒卖商品。有n个城市，每个城市之间有且只有一条无向边连通。给出n个城市的货物的价格，比如A城市是a元，B城市是b元，那么在A买在B卖，赚的钱就是b - a，反之就是 a - b。商人走每条路也需要一定的花费。现在他需要选择某两个城市进行货物的倒卖，问他能获得的最大利润是多少。

思路：

建图的方式非常妙。我们把从A到B的边的权值定义为b - a - v(v为边的权值)，从B到A的边的权值定义为a - b - v。依据这个从A到B再到C，就是b - a - v1 加上 c - b - v2，加起来就是c - a - v1 - v2，这样我们就可表示从任意城市到任意城市的距离了。

现在我们要求的就是任意两个城市之间的最大距离。树上最长路并不擅长，所以考虑用最短路求法进行求解。加一个超级源点和超级汇点，跑一遍最短路，就可以了，但是我们求的是最长路。。所以把边取反求最短路就ok了，开始用dijstra跑崩了，忘记了dij不能处理有负权边的图，所以跑了一遍spfa就过了。

这题的主要收获是建图，关键是抵消中间城市对结果的影响。

代码：

 #include <stdio.h>

 #include <string.h>

 #include <vector>

 #include <queue>

 using namespace std;

 const int inf = 0x3f3f3f3f;

 struct edge

 {

     int from,to;

     int cost;

 };

 vector<edge> edges;

 vector<int> v[];

 int nodev[];

 int dis[];

 bool vis[];

 void adde(int from,int to,int cost)

 {

     edge tmp;

     tmp.from = from;

     tmp.to = to;

     tmp.cost = -cost;

     edges.push_back(tmp);

     int sz = edges.size();

     v[from].push_back(sz-);

 }

 void init(int n)

 {

     for (int i = ;i <= n;i++) v[i].clear();

     edges.clear();

 }

 void spfa(void)

 {

     memset(vis,,sizeof(vis));

     memset(dis,inf,sizeof(dis));

     queue<int> q;

     q.push();

     dis[] = ;

     vis[] = ;

     while (!q.empty())

     {

         int u = q.front();

         q.pop();

         vis[u] = ;

         for (int i = ;i < v[u].size();i++)

         {

             int id = v[u][i];

             int to = edges[id].to;

             if (dis[to] > dis[u] + edges[id].cost)

             {

                 dis[to] = dis[u] + edges[id].cost;

                 if (!vis[to])

                 {

                     q.push(to);

                     vis[to] = ;

                 }

             }

         }

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while (t--)

     {

         int n;

         scanf("%d",&n);

         init(n+);

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

         {

             scanf("%d",&nodev[i]);

         }

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

         {

             int x,y,z;

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

             adde(x,y,nodev[y] - nodev[x] - z);

             adde(y,x,nodev[x] - nodev[y] - z);

         }

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

         {

             adde(,i,);

             adde(i,n+,);

         }

         spfa();

         printf("%d\n",-dis[n+]);

         //for (int i = 0;i <= n + 1;i++) printf("%d\n",dis[i]);

     }

     return ;

 }

巴特西

H - transaction transaction transaction

最新文章

热门文章