[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;
}