如何在局域网内做网站,薛城做网站,郑州世界工厂网,lamp wordpress 一键problem
luogu-P3344
solution
这个题面#xff0c;这个数据范围#xff0c;完完全全就是网络流宗教。。然而我发现建不出来。
很多一眼网络流最后却不是网络流而往往是 dpdpdp 的题目都有一个特性#xff1a;一个点可以流出多条流量#xff0c;流入流量却只能为 111。…problem
luogu-P3344
solution
这个题面这个数据范围完完全全就是网络流宗教。。然而我发现建不出来。
很多一眼网络流最后却不是网络流而往往是 dpdpdp 的题目都有一个特性一个点可以流出多条流量流入流量却只能为 111。
我曾尝试过对点加两条边一条流量为 111 带花费另一条流量无穷不带花费然后强制先流特殊边这就必须要用费用流来做到。
但题目所求往往相反也就是我强制先流要用负花费求出的是最大费用而题目却要最小费用。 首先我们把所有不能被任何一个网络架点覆盖的景点删去就解决了第一小问。
问题转化成了将所有点全覆盖的最小花费。
此题需要寻找一个结论景点按 xxx 排序后每个网络架点覆盖的点一定是景点的一段连续区间。 由 所有网络架的圆心都在矩形外 以及 所有网络架的半径均相同 这两个性质确保该结论的正确性。
注意这个结论是 所有圆心均在矩形上方 / 所有圆心均在矩形下方 分类后才成立。
于是我们就设 f(i,j,k):f(i,j,k):f(i,j,k): 考虑前 iii 个景点最后一次使用圆心在矩阵上方的网络架为 jjj最后一次使用圆心在矩阵下方的网络架为 kkk。
iii 景点能被圆心在矩阵上方的第 jjj 个网络架覆盖则再枚举一下矩阵上方的网络架上一次用的是哪个
f(i,j,k)min{f(i−1,o,k)}c(j)f(i,j,k)\min\{f(i-1,o,k)\}c(j)f(i,j,k)min{f(i−1,o,k)}c(j)。
圆心在矩阵下方的转移同理。
时间复杂度就是非常朴素的 O(n4)O(n^4)O(n4)。
注意我们的 fff 状态设计不再是常见到使用前 j/kj/kj/k 个圆心在矩阵上 / 下方的网络架而是直接最近一次使用的编号。
所以实际上这个网络架的使用编号是反复变化跳跃的。
看似并不是一个圆会覆盖一段连续点的方案。
但实际上这些不合法的方案一定不会成为最优解因为多次计算了网络架点的搭建花费。
而一个圆覆盖一段连续点的最优方案也统计进了所以最后答案是不会受到影响的。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define maxn 105
int n, m, R, cnt, cntd, cntu;
int f[maxn][maxn][maxn];
struct NB { int x, y; }s[maxn], g[maxn];
struct DK { int x, y, c; }p[maxn], d[maxn], u[maxn];bool check( DK o, NB w ) { return (o.x - w.x) * (o.x - w.x) (o.y - w.y) * (o.y - w.y) R * R;
}signed main() {scanf( %lld %lld %lld, n, m, R );for( int i 1;i n;i ) scanf( %lld %lld, s[i].x, s[i].y );for( int i 1;i m;i ) scanf( %lld %lld %lld, p[i].x, p[i].y, p[i].c );for( int i 1;i n;i ) {for( int j 1;j m;j )if( check( p[j], s[i] ) ) {g[ cnt] s[i];break;}}sort( g 1, g cnt 1, []( NB a, NB b ) { return a.x b.x; } );for( int i 1;i m;i )if( p[i].y 0 ) d[ cntd] p[i];else u[ cntu] p[i];memset( f, 0x3f, sizeof( f ) );f[0][0][0] 0;for( int i 1;i cnt;i )for( int j 0;j cntu;j )for( int k 0;k cntd;k ) {if( j and check( u[j], g[i] ) ) {f[i][j][k] f[i - 1][j][k];for( int o 0;o cntu;o )f[i][j][k] min( f[i][j][k], f[i - 1][o][k] u[j].c );}if( k and check( d[k], g[i] ) ) {f[i][j][k] f[i - 1][j][k];for( int o 0;o cntd;o )f[i][j][k] min( f[i][j][k], f[i - 1][j][o] d[k].c );}}int ans 1e18;for( int i 0;i cntu;i )for( int j 0;j cntd;j )ans min( ans, f[cnt][i][j] );printf( %lld\n%lld\n, cnt, ans );return 0;
}
