正题

题目链接:https://www.luogu.com.cn/problem/AT3877

---

题目大意

给出一个大小为$A\times B$的矩阵$d$
要求构造一个点数不超过$300$的有向图满足

• 图中没有重边和自环
• 图中的边权为$[0,100]$的整数或者未知数$X/Y$
• 对于所有$X\in [1,A],Y\in [1,B]$都有$d_{X,Y}$为最短路径长度。

$1\le A,B\le 10$

---

解题思路

设$f_{i,j}$表示经过$i$条$X$边$j$条$Y$边时的最小权值，那么有
dX,Y=min{fi,j+i×X+j×Y}d_{X,Y}=min\{f_{i,j}+i\times X+j\times Y\}dX,Y​=min{fi,j​+i×X+j×Y}
其中对于$f$的限制有
dX,Y≤min{fi,j+i×X+j×Y}d_{X,Y}\leq min\{f_{i,j}+i\times X+j\times Y\}dX,Y​≤min{fi,j​+i×X+j×Y}
由于为了尽量满足条件，所以$f$越小越好那么
fi,j=max{dX,Y−i×X−j×Y}f_{i,j}=max\{d_{X,Y}-i\times X-j\times Y\}fi,j​=max{dX,Y​−i×X−j×Y}
然后判一下是否合法就好了。

之后显然$i,j$不需要超过$100$，所以我们可以构造两条长度为$100$的$X/Y$链然后相互连边就好了。

时间复杂度：$O(100^{2}AB)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int A,B,d[N][N],f[N][N];
int main()
{scanf("%d%d",&A,&B);for(int i=1;i<=A;i++)for(int j=1;j<=B;j++)scanf("%d",&d[i][j]);for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)for(int p=1;p<=A;p++)for(int q=1;q<=B;q++)f[i][j]=max(f[i][j],d[p][q]-p*i-q*j);for(int p=1;p<=A;p++)for(int q=1;q<=B;q++){int ans=1e9;for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)ans=min(ans,f[i][j]+p*i+q*j);if(ans!=d[p][q])return puts("Impossible")&0;}puts("Possible");printf("250 10403\n");printf("249 1 0\n");printf("102 250 0\n");for(int i=1;i<=100;i++)printf("%d %d X\n",i,i+1);for(int i=1;i<=100;i++)printf("%d %d Y\n",i+1+101,i+101);for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)printf("%d %d %d\n",i+1,j+101+1,f[i][j]);printf("%d %d\n",249,250);return 0;
}