test20230111考试总结 -2023寒图论专题
前言
赛时得分情况:
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)\)。
代码
G. P8207 [THUPC2022 初赛] 最小公倍树
题面
题解
代码
H. P6192 【模板】最小斯坦纳树
题面
题解
代码
I. P4294 [WC2008]游览计划
题面
题解
代码
最新文章
- geotrellis使用(二十)geotrellis1.0版本新功能及变化介绍
- Ansible 学习笔记
- 为linux普通用户添加超级用户权限sudo
- js数组的操作
- (视频) 基于HTML5的服务器远程访问工具
- MD5 (摘要加密)
- 小试牛刀C#作为脚本语言执行解密
- iOS 关于多线程的一些知识点(不断更新)
- java.net.BindException: Address already in use: JVM_Bind
- IOS 区分缓存 内存 物理存储 逻辑存储
- 常用数据字典---bai
- edittext实现粘贴表情
- TMOUT
- BZOJ 2510: 弱题( 矩阵快速幂 )
- 关于JavaScript的模块化
- CSS清除浮动的几种方式
- echarts中视觉映射器(visualMap)与时间轴(timeline)混用的实现方法
- 转 -Filebeat + Redis 管理 LOG日志实践
- PostgreSQL 与 PostGIS
- SEED-DVS6467_SDK的交叉编译环境搭建问题