小型网站开发时间周期,wordpress建网站详细教程,做网站推广的 什么是开户,东莞厚街网站建设正题
题目链接:https://www.luogu.com.cn/problem/AT3877 题目大意
给出一个大小为ABA\times BAB的矩阵ddd 要求构造一个点数不超过300300300的有向图满足
图中没有重边和自环图中的边权为[0,100][0,100][0,100]的整数或者未知数X/YX/YX/Y对于所有X∈[1,A],Y∈[1,B]X\in[1,A…正题
题目链接:https://www.luogu.com.cn/problem/AT3877 题目大意
给出一个大小为A×BA\times BA×B的矩阵ddd 要求构造一个点数不超过300300300的有向图满足
图中没有重边和自环图中的边权为[0,100][0,100][0,100]的整数或者未知数X/YX/YX/Y对于所有X∈[1,A],Y∈[1,B]X\in[1,A],Y\in[1,B]X∈[1,A],Y∈[1,B]都有dX,Yd_{X,Y}dX,Y为最短路径长度。
1≤A,B≤101\leq A,B\leq 101≤A,B≤10 解题思路
设fi,jf_{i,j}fi,j表示经过iii条XXX边jjj条YYY边时的最小权值那么有 dX,Ymin{fi,ji×Xj×Y}d_{X,Y}min\{f_{i,j}i\times Xj\times Y\}dX,Ymin{fi,ji×Xj×Y} 其中对于fff的限制有 dX,Y≤min{fi,ji×Xj×Y}d_{X,Y}\leq min\{f_{i,j}i\times Xj\times Y\}dX,Y≤min{fi,ji×Xj×Y} 由于为了尽量满足条件所以fff越小越好那么 fi,jmax{dX,Y−i×X−j×Y}f_{i,j}max\{d_{X,Y}-i\times X-j\times Y\}fi,jmax{dX,Y−i×X−j×Y} 然后判一下是否合法就好了。
之后显然i,ji,ji,j不需要超过100100100所以我们可以构造两条长度为100100100的X/YX/YX/Y链然后相互连边就好了。
时间复杂度O(1002AB)O(100^2AB)O(1002AB) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N110;
int A,B,d[N][N],f[N][N];
int main()
{scanf(%d%d,A,B);for(int i1;iA;i)for(int j1;jB;j)scanf(%d,d[i][j]);for(int i0;i100;i)for(int j0;j100;j)for(int p1;pA;p)for(int q1;qB;q)f[i][j]max(f[i][j],d[p][q]-p*i-q*j);for(int p1;pA;p)for(int q1;qB;q){int ans1e9;for(int i0;i100;i)for(int j0;j100;j)ansmin(ans,f[i][j]p*iq*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 i1;i100;i)printf(%d %d X\n,i,i1);for(int i1;i100;i)printf(%d %d Y\n,i1101,i101);for(int i0;i100;i)for(int j0;j100;j)printf(%d %d %d\n,i1,j1011,f[i][j]);printf(%d %d\n,249,250);return 0;
}
