AT3877-[ARC089C]GraphXY【构造】 正题
题目链接:https://www.luogu.com.cn/problem/AT3877
题目大意
给出一个大小为(A imes B)的矩阵(d)
要求构造一个点数不超过(300)的有向图满足
- 图中没有重边和自环
- 图中的边权为([0,100])的整数或者未知数(X/Y)
- 对于所有(Xin[1,A],Yin[1,B])都有(d_{X,Y})为最短路径长度。
(1leq A,Bleq 10)
解题思路
设(f_{i,j})表示经过(i)条(X)边(j)条(Y)边时的最小权值，那么有
[d_{X,Y}=min{f_{i,j}+i imes X+j imes Y}
]
其中对于(f)的限制有
[d_{X,Y}leq min{f_{i,j}+i imes X+j imes Y}
]
由于为了尽量满足条件，所以(f)越小越好那么
[f_{i,j}=max{d_{X,Y}-i imes X-j imes 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
");
printf("249 1 0
");
printf("102 250 0
");
for(int i=1;i<=100;i++)printf("%d %d X
",i,i+1);
for(int i=1;i<=100;i++)printf("%d %d Y
",i+1+101,i+101);
for(int i=0;i<=100;i++)
for(int j=0;j<=100;j++)
printf("%d %d %d
",i+1,j+101+1,f[i][j]);
printf("%d %d
",249,250);
return 0;
}