Solution -「多校联训」数学考试
2024-10-19 00:08:53
\(\mathcal{Description}\)
Link.
给定 \(n\) 个函数，第 \(i\) 个有 \(f_i(x)=a_ix^3+b_ix^2+cx_i+d~(x\in[l_i,r_i]\cap\mathbb Z)\)，还有 \(m\) 条形如 \(x_u\le x_v+d\) 的限制，请最大化 \(\sum_{i=1}^nf_i(x_i)\) 或声明无解。
\(n,|l_i|,|r_i|\le 100\)。
\(\mathcal{Solution}\)
很久没遇到了，压根儿没往网络流方面想 qwq。
对于每个 \(f_i\)，拉一条代表 \(f_i(l_i..r_i)\) 的链，边权就是某个 \(f\) 的值的相反数；限制条件方便转化为最小割，之后直接跑最小割即可。
\(\mathcal O(\operatorname{Dinic}(\sum(r-l),m\sum(r-l)))\)。
\(\mathcal{Code}\)
/*~Rainybunny~*/
#include <queue>
#include <cstdio>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
#define int long long
inline int imin( const int a, const int b ) { return a < b ? a : b; }
const int MAXN = 100, IINF = 1ll << 50, BASE = 7e6;
int n, m, lid[MAXN + 5];
struct Function {
int a, b, c, d, l, r;
inline void read() {
scanf( "%lld %lld %lld %lld %lld %lld" , &a, &b, &c, &d, &l, &r );
}
inline int operator () ( const int x ) const {
return d + x * ( c + x * ( b + x * a ) );
}
} fc[MAXN + 5];
struct FlowGraph {
static const int MAXND = 2e4 + 10, MAXEG = 2e5;
int ecnt, bound, S, T, head[MAXND];
struct Edge { int to, flw, nxt; } graph[MAXEG * 2];
int ds[MAXND], curh[MAXND];
FlowGraph(): ecnt( 1 ) {}
inline void clear() {
ecnt = 1;
rep ( i, 0, bound ) head[i] = 0;
}
inline void operator () ( const int s, const int t, const int f ) {
graph[++ecnt] = { t, f, head[s] }, head[s] = ecnt;
graph[++ecnt] = { s, 0, head[t] }, head[t] = ecnt;
}
inline bool bfs() {
static std::queue<int> que;
rep ( i, 0, bound ) ds[i] = IINF;
que.push( S ), ds[S] = 0;
while ( !que.empty() ) {
int u = que.front(); que.pop();
for ( int i = head[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw && ds[u] + 1 < ds[v = graph[i].to] ) {
ds[v] = ds[u] + 1, que.push( v );
}
}
}
return ds[T] != IINF;
}
inline int dfs( const int u, int iflw ) {
if ( u == T ) return iflw;
int oflw = 0;
for ( int& i = curh[u], v; i; i = graph[i].nxt ) {
if ( graph[i].flw && ds[u] + 1 == ds[v = graph[i].to] ) {
int tmp = dfs( v, imin( iflw - oflw, graph[i].flw ) );
oflw += tmp, graph[i].flw -= tmp, graph[i ^ 1].flw += tmp;
if ( iflw == oflw ) break;
}
}
if ( !oflw ) ds[u] = IINF;
return oflw;
}
inline int calc( const int s, const int t ) {
int ret = 0; S = s, T = t;
while ( bfs() ) {
rep ( i, 0, bound ) curh[i] = head[i];
ret += dfs( S, IINF );
}
return ret;
}
} G;
signed main() {
freopen( "sleep.in", "r", stdin );
freopen( "sleep.out", "w", stdout );
int Q; scanf( "%lld", &Q );
while ( Q-- ) {
scanf( "%lld %lld", &n, &m ), G.clear();
int S = 0, T = 1, node = 1;
rep ( i, 1, n ) {
fc[i].read();
G( S, lid[i] = ++node, IINF );
rep ( j, fc[i].l, fc[i].r ) {
G( node, node + 1, BASE - fc[i]( j ) ), ++node;
}
G( node, T, IINF );
}
rep ( i, 1, m ) {
int u, v, d; scanf( "%lld %lld %lld", &u, &v, &d );
rep ( x, fc[u].l, fc[u].r ) {
if ( fc[v].l <= x - d && x - d <= fc[v].r ) {
G( lid[u] + x - fc[u].l, lid[v] + x - d - fc[v].l, IINF );
} else if ( x - d > fc[v].r ) {
G( lid[u] + x - fc[u].l, T, IINF );
}
}
}
G.bound = node;
int ans = -G.calc( S, T );
if ( ans <= -IINF ) puts( "mei ji ge" );
else printf( "%lld\n", ans + n * BASE );
}
return 0;
}
最新文章
- MST 001
- webpack构建与loaders
- HDOJ-1002
- github上有android开源项目
- 在web.config里使用configSource分隔各类配置
- 二分+最短路 uvalive 3270 Simplified GSM Network(推荐)
- 使用NPOI操作Excel
- 关于js封装框架类库之DOM操作模块（一）
- oracle求时间差的常用函数
- iostat磁盘IO命令详解
- HDFS对象存储--Ozone架构设计
- luogu2402 奶牛隐藏
- sql server中如何修改视图中的数据？
- Linux上配置http上网代理
- Benchmarking Zeebe: An Intro to How Zeebe Scales Horizontally and How We Measure It
- RabbitMQ :VHost,Exchanges, Queues,Bindings and Channels
- Android 进程回收
- 第二阶段Sprint冲刺会议5
- django 建立一个简单的应用
- RN47 中通过 JS 调用 Native 方法