前言
赛时得分情况：
| A | B | C | D | E | F | G | H | I | \(\texttt{Total}\) | \(\texttt{Rank}\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(100\) | \(100\) | \(10\) | \(58\) | \(54\) | \(100\) | \(300\) | \(100\) | \(0\) | \(822\) | \(2\) |
考试总结完善情况：
| A | B | C | D | E | F | G | H | I | \(\texttt{All}\) |
|---|---|---|---|---|---|---|---|---|---|
| √ | √ |
A. P1993 小 K 的农场
题面
给出 \(n\) 个变量 \(A_1,A_2,\cdots,A_n\)。有 \(m\) 个约束条件，约束条件分三种：
1 x y c：\(A_x-A_y\geq c\)。
2 x y c：\(A_x-A_y\leq c\)。
3 x y：\(A_x=A_y\)。
你需要输出是否存在满足条件的自然数解。如果存在输出 \(\texttt{Yes}\) 否则输出 \(\texttt{No}\)。
\(1 \leq n,m,c \leq 5 \times 10^3\)
题解
差分约束模板题。
对于第一种，\(A_x-A_y\geq c\) 可以变形成 \(A_y-A_x\leq -c\)。连边 \((x,y,-c)\)。
对于第二种，连边 \((y,x,c)\)。
对于第三种，可以看成 \(A_x-A_y\leq0\) 且 \(A_y-A_x\leq0\)，连边 \((x,y,0)\) 和 \((y,x,0)\)。
最后建立超级源点 \(O\)，对于所有变量 \(i\) 连边 \((O,i,0)\)。跑 SPFA 判负环，如果有负环就无解，否则有解。
时间复杂度 \(O(nm)\)。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5;
int n,m;
struct edge{
int nxt,to,w;
} g[N<<1];
int head[N],ec;
void add(int u,int v,int w){
g[++ec].nxt=head[u];
g[ec].to=v;
g[ec].w=w;
head[u]=ec;
}
int vis[N],dis[N],cq[N];
bool spfa(int s){
queue<int> q;
q.push(s);
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
cq[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(dis[u]+g[i].w<dis[v]){
dis[v]=dis[u]+g[i].w;
if(!vis[v]){
vis[v]=1;
cq[v]++;
if(cq[v]>=(n+1)) return false;
q.push(v);
}
}
}
}
return true;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int op,a,b,c;
cin>>op>>a>>b;
if(op==1){
cin>>c;
add(a,b,-c);
}
else if(op==2){
cin>>c;
add(b,a,c);
}
else{
add(a,b,0);
add(b,a,0);
}
}
for(int i=1;i<=n;i++){
add(0,i,0);
}
cout<<(spfa(0)?"Yes":"No");
return 0;
}
B. P2294 [HNOI2005]狡猾的商人
题面
有 \(n\) 个变量 \(A_1,A_2,\cdots,A_n\) 和 \(m\) 个约束条件，每个约束条件形如 \(\{s,t,v\}\)，意思是 \(\sum_{i=s}^{t}=v\)。求是否存在自然数解。
\(w\) 组数据。
\(1 \leq w \lt 100,1 \leq n \lt 100,\leq m \lt 1000\)
题解
令 \(b\) 为 \(a\) 的前缀和，则对于约束 \(\{s,t,v\}\)，可以看成 \(b_t-b_{s-1}=v\)，可以化成 \(b_t-b_{s-1}\leq v,b_{s-1}-b_t\leq (-v)\) 差分约束，连边 \((s-1,t,v),(t,s-1,-v)\)，最后跑 SPFA 判负环即可。
时间复杂度 \(O(wnm)\)。
代码
#include <bits/stdc++.h>
#define CL(x) memset(x,0,sizeof(x))
using namespace std;
const int N = 1e5;
int n,m;
struct edge{
int nxt,to,w;
} g[N<<1];
int head[N],ec;
void add(int u,int v,int w){
g[++ec].nxt=head[u];
g[ec].to=v;
g[ec].w=w;
head[u]=ec;
}
int vis[N],dis[N],cq[N];
bool spfa(int s){
queue<int> q;
q.push(s);
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
cq[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(dis[u]+g[i].w<dis[v]){
dis[v]=dis[u]+g[i].w;
if(!vis[v]){
vis[v]=1;
cq[v]++;
if(cq[v]>=(n+1)) return false;
q.push(v);
}
}
}
}
return true;
}
signed main(){
int t;cin>>t;
while(t--){
cin>>n>>m;
CL(g);CL(head);ec=0;CL(vis);CL(cq);CL(dis);
while(m--){
int u,v,w;
cin>>u>>v>>w;
add(u-1,v,-w);
add(v,u-1,w);
}
for(int i=1;i<=n;i++){
add((n+1),i,0);
}
if(!spfa(n+1)) cout<<"false";
else cout<<"true";
cout<<'\n';
}
return 0;
}
C. P7624 [AHOI2021初中组] 地铁
题面
题解
代码
D. P6378 [PA2010] Riddle
题面
题解
代码
E. P3513 [POI2011] KON-Conspiracy
题面
题解
代码
F. P5905 【模板】Johnson 全源最短路
题面
给出一个 \(n\) 个点 \(m\) 条边的有向图，令 \(d(i,j)\) 为 \(i\to j\) 的最短路径边权和。对于每一个 \(i(1 \leq i \leq n)\)，输出 \(\sum_{j=1}^{n}{j\cdot d(i,j)}\)。
\(1 \leq n \leq 3\times10^3,1 \leq m \leq 6\times10^3\)
题解
模板题，不讲。
时间复杂度 \(O(nm+nm\log m)\)。
