题解 P1073 【最优贸易】

· · 题解

注意到水晶球价格只有100种，可以忽略城市，只关注价格之间的关系

如果我们知道某一价格a（的城市i）有到达另一价格b（的城市j）的路径P，在不考虑P是否符合题意的情况下，存在买入价格为a的水晶球，卖出价格为b的水晶球的方案

若要让城市1到城市n有路径经过P，则要1可达i,j可达n，可用dfs在原图和反图上求出1可达的点和可达n的点

依据原图以价格为节点建立新图nG，因为只关心价格，1可达的城市无论是哪个，只要价格相同，便可视为同一种， 可达n的同理，也就是说，1可达（或可达n）的价格相同的城市认为是同一个点，它们所连的边也要合并。

如果1可达的价格为a的城市通往可达n价格为b的城市，那么在nG上对价格a向价格b连边

具体操作：例如有城市1可达价格为3的城市通往可达城市N价格为2的城市，那么在新图中节点3向节点100 + 2（100+表示可达城市n）连边，表示存在 城市1 -> 价格为2 -> 价格为3 -> 城市n 的路径。

在nG上跑floyd求传递闭包，求出每个价格可以到达哪些价格。枚举价格，求出答案

下面用画图软件画出的图来举个例子：

代码如下：

#include <cstdio>
#include <vector>

static const int maxn = 100005;

int get()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();

    int x = c - '0'; c = getchar();
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

int N, M;
int A[maxn];
int vis1[maxn], visN[maxn];
std::vector<int> G[maxn], uG[maxn];
int f[203][203];

void dfs(int k, int* vis, std::vector<int>* G)
{
    vis[k] = 1;
    for (int i = 0; i < (int)G[k].size(); i++)
        if (!vis[G[k][i]]) dfs(G[k][i], vis, G);
}

void floyd()
{
    for (int k = 1; k <= 200; k++)
        for (int i = 1; i <= 200; i++)
            for (int j = 1; j <= 200; j++)
                f[i][j] = (f[i][j] || (f[i][k] && f[k][j]));
}

int main()
{
    N = get(); M = get();
    for (int i = 1; i <= N; i++) A[i] = get();
    for (int i = 1; i <= M; i++)
    {
        int u, v, t; 
        u = get(); v = get(); t = get();
        if (t == 1) G[u].push_back(v);
        else        G[u].push_back(v), G[v].push_back(u);

        if (t == 1) uG[v].push_back(u);
        else        uG[u].push_back(v), uG[v].push_back(u);
    }
    dfs(1, vis1, G);
    dfs(N, visN,uG);

    for (int i = 1; i <= 200; i++) f[i][i] = 1;
    for (int i = 1; i <= N; i++) if (vis1[i])
        for (int j = 0; j < (int)G[i].size(); j++) if (visN[G[i][j]])
        {
            int u = A[i], v = A[G[i][j]] + 100;
            f[u][v] = 1;
        }

    floyd();
    int ans = 0;
    for (int i = 1; i <= 100; i++)
        for (int j = 101; j <= 200; j++)
            if (f[i][j]) ans = std::max(ans, j - i - 100);
    printf("%d\n", ans);
    return 0;
}