[ARC089E] GraphXY 题解

题意：

给出一个 \(A \times B\) 的矩阵，其中第 \(i\) 行第 \(j\) 列元素为 \(d_{i,j}\)。试构造一个有向图，满足：

有向图点数 \(\leq 300\)；

图中没有自环和重边；

图中边有边权，边权为 \([0,100]\) 中的整数，或者是未知数 \(X\) 或 \(Y\)；

对于所有\(x \in [1,A] , y \in[1,B]\)，满足当未知数 \(X = x,\,Y = y\) 时，图中 \(S\) 到 \(T\) 的最短路为 \(d_{x,y}\)。

输入格式：

第一行两个正整数 \(A,B~(1 \leq A , B \leq 10)\)

接下来一个 \(A \times B\) 的矩阵描述 \(d\) 。保证对于 \(\forall i \in [1,A] , j \in [1,B] , d_{i,j} \in [1,100]\) 。

输出格式：

如果不存在满足条件的有向图，输出一行 Impossible。

否则第一行输出 Possible，第二行输出有向图的点数 \(n\) 和边数 \(m\)

接下来 \(m\) 行每行输出 \(u,v,x\) 描述一条从 \(u\) 到 \(v\) 边权为 \(x\) 的有向边

最后一行两个正整数 \(S,T\) 。

这道题的思维难度还是非常高的。

注意到任意路径的长度都形如 \(iX + jY + k\) ，并且当 \(i,j\) 固定时该路径是最短路当且仅当 \(k\) 取最小值。

设 \(f(i,j)\) 表示 \(S\) 到 \(T\) 的一条路径经过 \(i\) 条 \(X\) 边和 \(j\) 条 \(Y\) 边时，路径上其他边的长度和的最小值。

虽然转移方程不太好推，但是我们可以写出它和 \(d_{x,y}\) 的关系式 \[ d_{x,y} = \min_{i,j}\{ f(i,j) + i\cdot x + j \cdot y\} \] 得到 \[ f(i,j) + ix + jy \ge d_{x,y} \Longrightarrow f(i,j) \ge d_{x,y}-ix-iy \] 当 \(x,y\) 固定时对任意 \(i,j\) 成立（除了无解的情况）。

那么当 \(i,j\) 固定时对任意 \(x,y\) 同样成立，即 \[ f(i,j)= \max_{x,y}\{d_{x,y} - i\cdot x - j \cdot y\} \] 于是我们就推出 \(f(i,j)\) 的转移方程了。

那么怎么构造呢？我们可以弄两条长 \(100\) 的链，排成两行（显然更长的链不会产生贡献）

一条链边权全为 \(X\) ，另一条链边权全为 \(Y\) ，分别编号 \(2\) 到 \(101\) 、\(102\) 到 \(201\) ，令 \(S=1,\,T=202\) 。

然后将 \(X\) 链左起第 \(i+1\) 个和 \(Y\) 链右起第 \(j+1\) 个连边权 \(f(i,j)\) 的边。

最后把 \(S\) 连上节点 \(2\) ，\(T\) 连上节点 \(201\) ，\(S\) 和 \(T\) 连一条边权为 \(f(0,0)\) 的边，就搞定啦 qwq

时间复杂度 \(\mathcal{O}(n^6)\) ，\(n\) 是 \(A,B\) 的最大取值。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define N ((int)(333))
#define M 15

int f[N][N], d[M][M];
struct Edge { int u, v, w; } e[N * N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) cin >> d[i][j];
    rep(i, 0, 100) rep(j, 0, 100)
        rep(x, 1, n) rep(y, 1, m) { up(f[i][j], d[x][y] - i * x - j * y); }
    rep(x, 1, n) rep(y, 1, m) {
        int mn = INF;
        rep(i, 0, 100) rep(j, 0, 100) down(mn, f[i][j] + i * x + j * y);
        if(mn != d[x][y]) return cout << "Impossible\n", 0;
    }
    cout << "Possible" << '\n' << "202 10401" << '\n';
    rep(i, 1, 100) cout << i << ' ' << i + 1 << " X\n";
    rep(i, 102, 201) cout << i << ' ' << i + 1 << " Y\n";
    rep(i, 0, 100) rep(j, 0, 100)
        cout << i + 1 << ' ' << 202 - j << ' ' << f[i][j] << '\n';
    cout << "1 202" << '\n';
    return 0;
}