引入
先介绍一下大家熟知的差分约束问题，通过建图将线性规划问题转化为图论问题。
给定多个形如\(a_i - a_j \geq c_{i , j}\)的不定式，找出一种可行解。
这种问题有一种很巧妙的构造方法，就是将这类问题抽象成一个图论问题来解决。
具体来说，就是将不等式移项，变为\(a_i \geq a_j + c_{i , j}\)，发现很像最短(长)路中的式子。
在所有边都松弛完成之后，最短路中每条边都满足\(dis_j \leq dis_i + w_{i , j}\)(不存在负环)，反之可以继续松弛。同理，在最长路中每条边都满足\(dis_j \leq dis_i + w_{i , j}\)(不存在正环)。
然后，我们发现这最短(长)路中的不等式的和原来的不等式很像，于是连接\(i\)与\(j\)之间边权为\(w_{i , j}\)的边，跑一遍最长路，就得到了原问题的一种可行解。
与差分约束类似，同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。
例题
[ABC077D] Small Multiple
我们可以先考虑如何求出一个数各数位之和。
先看个位，\(1\)的位和为\(1\)，\(2\)就在\(1\)的前提下\(+1\)，以此类推，就能求出个位位和。
再看其他位，无非就是\(n\)个\(10\)加上若干个\(1\)，而且只有\(1\)会对答案产生贡献。
所以我们一共存在两种状态，一种是\(+1\)，另外一种是\(\times 10\)，其中\(+1\)边权是\(1\)，\(\times 10\)边权是\(0\)。
但是这种方法还有一个问题，就是有可能会爆\(long\ long\)，但是我们考虑因为要求的是\(K\)的倍数的各数位之和，所以每次\(\times 10\)时\(/mod\ K\)就可以让余数不变，从而不影响结果。
然后，跑一遍\(SPFA\)或者\(Dijkstra\)或\(01Bfs\)就行了，答案就是\(dis_0\)。
参考代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std ;
namespace IO
{
namespace Read
{
#define isdigit(ch) (ch >= '0' && ch <= '9')
#define SIZE (1 << 16)
char buf[SIZE] , *_now = buf , *_end = buf ;
char getchar()
{
if(_now == _end)
{
_now = _end = buf ;
_end += fread(buf , 1 , SIZE , stdin) ;
if(_now == _end)
return EOF ;
}
return *(_now++) ;
}
template<typename T>
void read(T& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = (w << 1) + (w << 3) + (ch ^ 48) , ch = getchar() ;
w *= f ;
}
void read(char& c)
{
char tmp = getchar() ;
while(tmp == ' ' || tmp == '\n')
tmp = getchar() ;
c = tmp ;
}
#define sb(ch) (ch == ' ' || ch == '\n')
void read(char* s)
{
char ch = getchar() ;
while(sb(ch))
ch = getchar() ;
int len = 0 ;
while(!sb(ch))
s[len++] = ch , ch = getchar() ;
s[len] = '\0' ;
}
void read(string& s)
{
s.clear() ;
char ch = getchar() ;
while(sb(ch))
ch = getchar() ;
while(!sb(ch))
s.push_back(ch) , ch = getchar() ;
}
void read(double& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
void read(float& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
void read(long double& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
class qistream
{
public:
template<typename T>
qistream& operator>>(T& a)
{
read(a) ;
return *this ;
}
qistream& operator>>(char* s)
{
read(s) ;
return *this ;
}
} qcin ;
}
namespace Write
{
#define SIZE (1 << 16)
char buf[SIZE] , *p = buf ;
template<typename T>
struct pres
{
T num ;
int len ;
} ;
template<typename T>
pres<T> make_lf(T num , int len)
{
pres<T> ret ;
ret.num = num , ret.len = len ;
return ret ;
}
void flush()
{
fwrite(buf , 1 , p - buf , stdout) ;
p = buf ;
}
void putchar(char ch)
{
if(p == buf + SIZE)
flush() ;
*p = ch ;
++p ;
}
class Flush{public:~Flush(){flush() ;};}_;
template<typename T>
void write(T x)
{
char st[50] ;
int len = 0 ;
if(x < 0)
putchar('-') , x = -x ;
do
{
st[++len] = x % 10 + '0' ;
x /= 10 ;
} while(x) ;
while(len)
putchar(st[len--]) ;
}
void write(char c)
{
putchar(c) ;
}
void write(const char* s)
{
int siz = strlen(s) ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(char* s)
{
int siz = strlen(s) ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(string& s)
{
int siz = s.size() ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(double x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
long long sb = (long long)(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
long long ssb = (long long)(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
void write(float x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
int sb = int(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
int ssb = int(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
void write(long double x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
__int128 sb = __int128(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
__int128 ssb = __int128(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
class qostream
{
public:
template<typename T>
qostream& operator<<(T x)
{
write(x) ;
return *this ;
}
qostream& operator<<(const char* s)
{
write(s) ;
return *this ;
}
template<typename T>
qostream& operator<<(const pres<T> x)
{
write(x.num , x.len) ;
return *this ;
}
} qcout ;
}
using Read::qcin ;
using Write::qcout ;
using Write::make_lf ;
}
using namespace IO ;
int s = 0 ;
struct edg
{
int to , val ;
bool operator<(const edg& b) const
{
return val > b.val ;
}
} ;
edg make_edg(int to , int val)
{
edg ret ;
ret.to = to , ret.val = val ;
return ret ;
}
vector<edg> edge[100005] ;
int dis[100005] = {} ;
bool vis[100005] = {} ;
void dij(int sta)
{
memset(dis , 0x3f , sizeof dis) ;
dis[sta] = 1 ;
priority_queue<edg> Q ;
Q.push(make_edg(sta , 0)) ;
while(!Q.empty())
{
int t = Q.top().to ;
Q.pop() ;
if(vis[t])
continue ;
vis[t] = true ;
int siz = edge[t].size() ;
for(int i = 0 ; i < siz ; ++i)
{
int to = edge[t][i].to , val = edge[t][i].val ;
if(!vis[to] && dis[t] + val < dis[to])
dis[to] = dis[t] + val , Q.push(make_edg(to , dis[to])) ;
}
}
}
bool use[100005] = {} ;
void spfa(int sta)
{
memset(dis , 0x3f , sizeof dis) ;
dis[sta] = 1 ;
queue<int> Q ;
Q.push(sta) ;
while(!Q.empty())
{
int t = Q.front() ;
Q.pop() ;
use[t] = false ;
int siz = edge[t].size() ;
for(int i = 0 ; i < siz ; ++i)
{
int to = edge[t][i].to , val = edge[t][i].val ;
if(dis[t] + val < dis[to])
{
dis[to] = dis[t] + val ;
if(!use[to])
{
use[to] = true ;
Q.push(to) ;
}
}
}
}
}
int main()
{
qcin>>s ;
for(int i = 0 ; i < s ; ++i)
edge[i].push_back(make_edg((i + 1) % s , 1)) , edge[i].push_back(make_edg((i * 10) %s , 0)) ;
// dij(1) ;
// spfa(1) ;
qcout<<dis[0]<<'\n' ;
return 0 ;
}
P9140 [THUPC 2023 初赛] 背包
我们发现该题中的\(V\)很大但是\(v_i\)很小，而且是完全背包问题，所以考虑使用同余最短路。
-
首先考虑贪心，因为背包容量很大，所以其中占大部分的一定是性价比最高的物品，我们记该物品编号为\(k\)，其体积为\(v_k\)，价值为\(c_i\)。
-
我们考虑选一些总体积为\(v_k\)的物品一定不如选一个\(k\)物品，因为\(k\)的性价比最高，但是对于总体积不为\(v_k\)就不一定，最优解可能会比全部取\(k\)并空出剩下容量要优或劣（劣是因为本题要求总体积必须为\(V\)）。考虑求出要优或劣多少。
-
考虑\(DP\)，设\(V\)为体积，\(C\)为价值，\(dp_i\)为\(i\equiv (V \mod v_k)\)下最大的$C - \lfloor \frac{V}{v_i} \rfloor \times c_k \(，也就是最优解比全部取\)k\(优或劣多少。可以证明\)V\(不会大于实际询问的\)V$
(但是我懒)。转移方程式即为：
\[dp_i = \max_{1 \leq j \leq n}(dp_j + c_j - \lfloor \frac{i + v_j}{v_k} \rfloor \times c_k) \] -
然后，我们发现：这个\(DP\)转移是有后效性的，因此无法直接转移，需要建图跑最长路。
-
查询结果就是\(\frac{V}{v_k} \times c_k + dp_{V \ mod \ v_k}\)。
我看题解都是转圈写的，但是我不会，所以只能跑\(SPFA\)。
参考代码：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std ;
namespace IO
{
namespace Read
{
#define isdigit(ch) (ch >= '0' && ch <= '9')
#define SIZE (1 << 16)
char buf[SIZE] , *_now = buf , *_end = buf ;
char getchar()
{
if(_now == _end)
{
_now = _end = buf ;
_end += fread(buf , 1 , SIZE , stdin) ;
if(_now == _end)
return EOF ;
}
return *(_now++) ;
}
template<typename T>
void read(T& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = (w << 1) + (w << 3) + (ch ^ 48) , ch = getchar() ;
w *= f ;
}
void read(char& c)
{
char tmp = getchar() ;
while(tmp == ' ' || tmp == '\n')
tmp = getchar() ;
c = tmp ;
}
#define sb(ch) (ch == ' ' || ch == '\n')
void read(char* s)
{
char ch = getchar() ;
while(sb(ch))
ch = getchar() ;
int len = 0 ;
while(!sb(ch))
s[len++] = ch , ch = getchar() ;
s[len] = '\0' ;
}
void read(string& s)
{
s.clear() ;
char ch = getchar() ;
while(sb(ch))
ch = getchar() ;
while(!sb(ch))
s.push_back(ch) , ch = getchar() ;
}
void read(double& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
void read(float& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
void read(long double& w)
{
w = 0 ;
short f = 1 ;
char ch = getchar() ;
while(!isdigit(ch))
{
if(ch == '-')
f = -1 ;
ch = getchar() ;
}
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() ;
if(ch == '.')
{
ch = getchar() ;
int len = 0 ;
while(isdigit(ch))
w = w * 10 + (ch ^ 48) , ch = getchar() , ++len ;
while(len)
w /= 10 , --len ;
}
w *= f ;
}
class qistream
{
public:
template<typename T>
qistream& operator>>(T& a)
{
read(a) ;
return *this ;
}
qistream& operator>>(char* s)
{
read(s) ;
return *this ;
}
} qcin ;
}
namespace Write
{
#define SIZE (1 << 16)
char buf[SIZE] , *p = buf ;
template<typename T>
struct pres
{
T num ;
int len ;
} ;
template<typename T>
pres<T> make_lf(T num , int len)
{
pres<T> ret ;
ret.num = num , ret.len = len ;
return ret ;
}
void flush()
{
fwrite(buf , 1 , p - buf , stdout) ;
p = buf ;
}
void putchar(char ch)
{
if(p == buf + SIZE)
flush() ;
*p = ch ;
++p ;
}
class Flush{public:~Flush(){flush() ;};}_;
template<typename T>
void write(T x)
{
char st[50] ;
int len = 0 ;
if(x < 0)
putchar('-') , x = -x ;
do
{
st[++len] = x % 10 + '0' ;
x /= 10 ;
} while(x) ;
while(len)
putchar(st[len--]) ;
}
void write(char c)
{
putchar(c) ;
}
void write(const char* s)
{
int siz = strlen(s) ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(char* s)
{
int siz = strlen(s) ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(string& s)
{
int siz = s.size() ;
for(int i = 0 ; i < siz ; ++i)
putchar(s[i]) ;
}
void write(double x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
long long sb = (long long)(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
long long ssb = (long long)(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
void write(float x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
int sb = int(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
int ssb = int(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
void write(long double x , int len = 6)
{
if(x < 0)
write('-') , x = -x ;
__int128 sb = __int128(x) ;
x -= sb ;
int spar = 0 ;
for(int i = 0 ; i <= len ; ++i)
{
x *= 10 ;
if(int(x) == 0)
++spar ;
}
__int128 ssb = __int128(x) ;
if(ssb % 10 >= 5)
ssb += 10 ;
ssb /= 10 ;
write(sb) , write('.') ;
for(int i = 1 ; i <= spar ; ++i)
write('0') ;
write(ssb) ;
}
class qostream
{
public:
template<typename T>
qostream& operator<<(T x)
{
write(x) ;
return *this ;
}
qostream& operator<<(const char* s)
{
write(s) ;
return *this ;
}
template<typename T>
qostream& operator<<(const pres<T> x)
{
write(x.num , x.len) ;
return *this ;
}
} qcout ;
}
using Read::qcin ;
using Write::qcout ;
using Write::make_lf ;
}
using namespace IO ;
#define int long long
struct edg
{
int to , val ;
} ;
edg make_edg(int to , int val)
{
edg ret ;
ret.to = to , ret.val = val ;
return ret ;
}
vector<edg> edge[100005] ;
int n = 0 , T = 0 ;
int w[55] = {} , v[55] = {} ;
int m = 1000000 , t = 0 ;
bool use[100005] = {} ;
int dis[100005] = {} ;
void spfa(int sta)
{
for(int i = 0 ; i <= m ; ++i)
dis[i] = -1e18 ;
dis[sta] = 0 ;
queue<int> Q ;
Q.push(sta) ;
while(!Q.empty())
{
int now = Q.front() ;
Q.pop() ;
use[now] = false ;
int siz = edge[now].size() ;
for(int i = 0 ; i < siz ; ++i)
{
int to = edge[now][i].to , val = edge[now][i].val ;
if(dis[now] + val > dis[to])
{
dis[to] = dis[now] + val ;
if(!use[to])
{
use[to] = true ;
Q.push(to) ;
}
}
}
}
}
signed main()
{
qcin>>n>>T ;
for(int i = 1 ; i <= n ; ++i)
{
qcin>>w[i]>>v[i] ;
if(v[i] * m > t * w[i])
m = w[i] , t = v[i] ;
}
for(int i = 0 ; i <= m ; ++i)
for(int j = 1 ; j <= n ; ++j)
edge[i].push_back(make_edg((i + w[j]) % m , v[j] - (i + w[j]) / m * t)) ;
spfa(0) ;
while(T--)
{
int V = 0 ;
qcin>>V ;
if(dis[V % m] <= -1e17)
qcout<<"-1\n" ;
else
qcout<<dis[V % m] + V / m * t<<'\n' ;
}
return 0 ;
}