Atcoder Regular Contest 089E

题目链接：ARC089E - GraphXY
题意：给你一个未知的图，中间有一些边是定值，另一些边可能为X，也可能为Y，令(d_{x,y})为当所有的(X=x,Y=y)时，从S到T的最短路径长度。给你所有的(d_{x,y} (1 le x,y le 10))，请构造出这样的一个图，图中点数不得超过(300)，若无解，请输出"Impossible"（不含双引号），否则，请输出"Possible"（不含双引号），并在下一行输出节点个数与边数，接下来输出所有的边及边长（是一个常数或'X'或'Y'），最后输出S和T。
题解：令(f[i][j])表示从S到T的路径上有i个x和j个y时其余边的最小可能长度，若我们已知(f[i][j])，则可以推出(d[x][y]=min{f[i][j]+i*x+j*y})，那么对该式进行移项，得出(f[i][j]=max{d[x][y]-i*x-j*y})，但该(f[i][j])不一定符合条件，重新判断，若不符合则该情况一定无解，否则一定可以构造出一解。
考虑如何构造：连两条长度为100的链（显然，长度更长毫无意义），一条链所有边权为X，另一条链所有边权为Y，那么对于每一个(f[i][j])，可以在X链上的第(i)个节点和Y链上的倒数第(j)个节点间连一条长度为(f[i][j])的边。即可构造方案。
code:

#include <cstdio>
#include <cstring>
#define Maxn 300
#define Maxk 10
#define Inf 0x3f3f3f3f
int f[Maxn+5][Maxn+5];
int d[Maxk+5][Maxk+5];
//f[i][j]表示从S到T的路径上有i个x和j个y时其余边的最小可能长度 
//d[x][y]=min{f[i][j]+i*x+j*y}
//f[i][j]=max{d[x][y]-i*x-j*y}
int mx(int a,int b){
	return a>b?a:b;
}
int mn(int a,int b){
	return a<b?a:b;
}
struct Edge{
	int u,v,w;
}edge[Maxn*Maxn+5];
int n,m;
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]=mx(f[i][j],d[x][y]-i*x-j*y);
				}
			}
		}
	}
	int now;
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			now=Inf;
			for(int i=0;i<=100;i++){
				for(int j=0;j<=100;j++){
					now=mn(now,f[i][j]+i*x+j*y);
				}
			}
			if(now!=d[x][y]){
				puts("Impossible");
				return 0;
			}
		}
	}
	puts("Possible");
	puts("202 10401");
	for(int i=1;i<=100;i++){
		printf("%d %d X
",i,i+1);
	}
	for(int i=102;i<202;i++){
		printf("%d %d Y
",i,i+1);
	}
	for(int i=0;i<=100;i++){
		for(int j=0;j<=100;j++){
			printf("%d %d %d
",i+1,202-j,f[i][j]);
		}
	}
	puts("1 202");
	return 0;
}