AT3877-[ARC089C]GraphXY【構造】

正題

題目連結: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\leq A,B\leq 10\)

解題思路

設\(f_{i,j}\)表示經過\(i\)條\(X\)邊\(j\)條\(Y\)邊時的最小權值，那麼有

\[d_{X,Y}=min\{f_{i,j}+i\times X+j\times Y\}

\]

其中對于\(f\)的限制有

\[d_{X,Y}\leq min\{f_{i,j}+i\times X+j\times Y\}

由于為了盡量滿足條件，是以\(f\)越小越好那麼

\[f_{i,j}=max\{d_{X,Y}-i\times X-j\times Y\}

然後判一下是否合法就好了。

之後顯然\(i,j\)不需要超過\(100\)，是以我們可以構造兩條長度為\(100\)的\(X/Y\)鍊然後互相連邊就好了。

時間複雜度：\(O(100^2AB)\)

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