題解 AT3877 【[ARC089C] GraphXY】
在【有趣的思維題】里看到了這道題。
題意：
給出一個\(A\times B\)的矩陣，其中第i行第j列元素為\(d_{i,j}\)，試構造一個有向圖，滿足：
-
有向圖點數\(\le 300\)
-
沒有重邊和自環
-
圖中邊有邊權，邊權\(\in [0,100]\)且是正整數。或者是未知數X或者Y
-
對於所有\(x \in [1,A] \ y\in[1,B]\)，滿足未知數\(X=x,Y=y\)時，圖中s到t的最短路為\(d_{x,y}\)
看清楚題目了，睜大眼睛。s和t是自己選定的，x和y是在區間內變化的，再讀一遍題意。
分析：
當 \(s\) 與 \(t\) 之間的路徑上有 \(i\) 個\(x\) ，\(j\) 個 \(y\) ，設 \(f_{i,j}\) 表示此時路徑上其餘邊的最小可能長度。
\(d_{x,y}\ge ix+jy+f_{i,j}\) 。
有：\(d_{x,y}=\min \{ix+jy+f_{i,j}\}\)
\(d_{x,y}-ix-jy \le f_{i,j}\)
\(f_{i,j}=\max \{d_{x,y}-ix-jy\}\)
嘗試構造一種情況，
連兩條長度為 \(100\) ，有 \(101\) 個點的鏈，一條鏈所有邊權為 \(X\) ，另一條鏈所有邊權為 \(Y\)
設 \(s=1，t=202\)
\(X\) 鏈的第 \(i\) 個節點和 \(Y\) 鏈的倒數第 \(j\) 個節點間連一條邊權 \(f_{i,j}\) 的邊。
如果 \(d_{x,y} \neq \min \{ix+jy+f_{i,j}\}\) 則是無解情況。
否則輸出答案。
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f,N=310;
int n,m,f[N][N],d[N][N];
int bmin(int a,int b){ return (a<b)?a:b;}
int bmax(int a,int b){ return (a<b)?b:a;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
scanf("%d",&d[i][j]);
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
for(int x=1;x<=n;x++) for(int y=1;y<=m;y++)
f[i][j]=bmax(f[i][j],d[x][y]-i*x-j*y);
for(int x=1;x<=n;x++) for(int y=1;y<=m;y++){
int mn=inf;
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
mn=bmin(mn,f[i][j]+i*x+j*y);
if(mn!=d[x][y]){ puts("Impossible"); return 0; }
}
puts("Possible"); printf("202 10401\n");
for(int i=1;i<=100;i++) printf("%d %d X\n",i,i+1);
for(int i=102;i<202;i++) printf("%d %d Y\n",i,i+1);
for(int i=0;i<=100;i++) for(int j=0;j<=100;j++)
printf("%d %d %d\n",i+1,202-j,f[i][j]);
puts("1 202");
return 0;
}
