虽然刷的大部分都是水题，但也是花费时间了的。所以还是总结一下吧。
3239：最短路
求\(1\)到\(n\)的最短路。
思路：直接单源最短路模板。
点击查看代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,s;
vector< pair<int,int> > g[100005];
long long dis[100005];
bool vis[100005];
priority_queue<pair<long long,int> ,vector<pair<long long,int> >,greater< pair<long long,int> > > q;
void dij(){
for(int i=1;i<=n;i++){
dis[i]=0x7fffffff;
}
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()){
int u=q.top().second;
long long w=q.top().first;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i].second;
int ww=g[u][i].first;
if(vis[v]) continue;
if(w+ww<dis[v]){
dis[v]=w+ww;
q.push(make_pair(dis[v],v));
}
}
}
}
int main(){
n=read(),m=read(),s=1;
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
g[u].push_back(make_pair(w,v));
}
dij();
cout<<dis[n];
return 0;
}
3240: 小P的Civilization
给定一棵树，操作：路径节点权值加1，求路径上节点权值的最大值。
思路：差分，倍增求路径上节点权值的最大值。一些细节需要注意。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,q,f[500005][20],t,d[500005],dp[500005],maxx[500005][20];
vector<int> g[500005];
void dfs(int x,int fa){
d[x]=d[fa]+1;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
f[v][0]=x;
for(int j=1;j<=t;j++) f[v][j]=f[f[v][j-1]][j-1];
dfs(v,x);
}
}
int lca(int u,int v){
if(d[u]<d[v]) swap(u,v);
for(int i=t;i>=0;i--){
if(d[f[u][i]]>=d[v]) u=f[u][i];
}
if(u==v) return u;
for(int i=t;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];
}
void dfs1(int x,int fa){
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
dfs1(v,x);
dp[x]+=dp[v];
}
}
void dfs2(int x,int fa){
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
maxx[v][0]=dp[x];
for(int j=1;j<=t;j++) maxx[v][j]=max(maxx[v][j-1],maxx[f[v][j-1]][j-1]);
dfs2(v,x);
}
}
int ask_maxx(int u,int v){
if(d[u]<d[v]) swap(u,v);
int ans=max(dp[u],dp[v]);
for(int i=t;i>=0;i--){
if(d[f[u][i]]>=d[v]){
ans=max(maxx[u][i],ans);
u=f[u][i];
}
}
if(u==v) return ans;
for(int i=t;i>=0;i--){
if(f[u][i]!=f[v][i]){
ans=max(ans,max(maxx[u][i],maxx[v][i]));
u=f[u][i],v=f[v][i];
}
}
ans=max(ans,maxx[u][0]);
return ans;
}
int main(){
n=read(),m=read(),q=read();
t=log(n)/log(2)+1;
for(int i=2;i<=n;i++){
int u=read();
g[u].push_back(i);
g[i].push_back(u);
}
dfs(1,0);
for(int i=1;i<=m;i++){
int u=read(),v=read();
int lac=lca(u,v);
dp[u]+=1,dp[v]+=1,dp[lac]-=1,dp[f[lac][0]]-=1;
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=q;i++){
int u=read(),v=read();
cout<<ask_maxx(u,v)<<"\n";
}
return 0;
}
3242: 聚会
给定一棵树，多次查找距离三个点总距离最短的节点，并输出总距离。
思路：两两求LCA，会出现重复的LCA，取不重复的那个LCA，即为目标节点。
点击查看代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,f[500005][20],d[500005],t;
vector<int> g[500005];
queue<int> q;
void bfs(){
q.push(1);
d[1]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(d[v]) continue;
d[v]=d[u]+1;
f[v][0]=u;
for(int j=1;j<=t;j++) f[v][j]=f[f[v][j-1]][j-1];
q.push(v);
}
}
}
int lca(int u,int v){
if(d[u]<d[v]) swap(u,v);
for(int i=t;i>=0;i--){
if(d[f[u][i]]>=d[v]) u=f[u][i];
}
if(u==v) return u;
for(int i=t;i>=0;i--){
if(f[u][i]!=f[v][i]){
u=f[u][i];
v=f[v][i];
}
}
return f[u][0];
}
int main(){
n=read(),m=read();
t=log(n)/log(2)+1;
for(int i=1;i<n;i++){
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
bfs();
for(int i=1;i<=m;i++){
int u=read(),v=read(),k=read();
int root1=lca(u,v);
int root2=lca(v,k);
int root3=lca(u,k);
int p;
if(root1==root2) p=root3;
if(root1==root3) p=root2;
if(root2==root3) p=root1;
int ans=d[u]+d[v]+d[k]-d[root1]-d[root2]-d[root3];
printf("%d %d\n",p,ans);
}
return 0;
}
3243: 邮递员送信
求1到其他所有节点并返回1号的总距离。
思路：正向，反向跑最短路即可。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m;
int dis[1005];
bool inq[1005];
long long ans;
vector<pair<int,int> > g[1005],g1[1005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void dij(){
memset(inq,0,sizeof(inq));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()){
int u=q.top().second;
int w=q.top().first;
q.pop();
inq[1]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i].second;
int w=g[u][i].first;
if(inq[v]) continue;
if(dis[v]>w+dis[u]){
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
}
void dij1(){
memset(inq,0,sizeof(inq));
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty()){
int u=q.top().second;
int w=q.top().first;
q.pop();
inq[u]=1;
for(int i=0;i<g1[u].size();i++){
int v=g1[u][i].second;
int w=g1[u][i].first;
if(inq[v]) continue;
if(dis[v]>w+dis[u]){
dis[v]=dis[u]+w;
q.push(make_pair(dis[v],v));
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
g[u].push_back(make_pair(w,v));
g1[v].push_back(make_pair(w,u));
}
dij();
for(int i=2;i<=n;i++) ans+=dis[i];
dij1();
for(int i=2;i<=n;i++) ans+=dis[i];
cout<<ans;
return 0;
}
3244: 奶牛野餐
给一图，有向边，有若干标记点，求所有标记点都可以到达的节点的个数。
思路：依次从标记点出发，将能走到的节点的到达次数+1，最后扫描，到达次数=标记点的数量的即目标点，统计答案。
点击查看代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int k,n,m,c[105],s[1005],ans;
vector<int> g[1005];
bool vis[1005],mark[1005];
void bfs(int x){
queue<int> q;
q.push(x);
vis[x]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(mark[v]) s[v]++;
if(!vis[v]){
vis[v]=1;
s[v]++;
q.push(v);
}
}
}
}
int main(){
k=read(),n=read(),m=read();
for(int i=1;i<=k;i++) c[i]=read(),s[c[i]]++;
for(int i=1;i<=m;i++){
int u=read(),v=read();
g[u].push_back(v);
}
for(int i=1;i<=k;i++){
memset(vis,0,sizeof(vis));
bfs(c[i]);
}
for(int i=1;i<=n;i++){
if(s[i]==k) ans++;
}
cout<<ans;
return 0;
}
3245: 最近公共祖先
LCA模板。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,s,t,f[500005][20],d[500005];
vector<int> g[500005];
void dfs(int x,int fa){
d[x]=d[fa]+1;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(v==fa) continue;
f[v][0]=x;
for(int j=1;j<=t;j++) f[v][j]=f[f[v][j-1]][j-1];
dfs(v,x);
}
}
int lca(int u,int v){
if(d[u]<d[v]) swap(u,v);
for(int j=t;j>=0;j--){
if(d[f[u][j]]>=d[v]) u=f[u][j];
}
if(u==v) return u;
for(int j=t;j>=0;j--){
if(f[u][j]!=f[v][j]){
u=f[u][j];
v=f[v][j];
}
}
return f[u][0];
}
int main(){
n=read(),m=read();
t=log(n)/log(2)+1;
for(int i=1;i<n;i++){
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=m;i++){
int u=read(),v=read();
cout<<lca(u,v)<<"\n";
}
return 0;
}
3246: 最小生成树
最小生成树模板。
点击查看代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,tot,f[200005];
long long ans;
struct edge{
int u;
int v;
int w;
}e[500005];
bool cmp(edge a,edge b){
return a.w<b.w;
}
int get(int x){
if(f[x]==x) return x;
return f[x]=get(f[x]);
}
void kru(){
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(get(u)==get(v)) continue;
f[get(u)]=get(v);
tot++;
ans+=w;
if(tot==n-1) break;
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
e[i].u=read();
e[i].v=read();
e[i].w=read();
}
kru();
cout<<ans;
return 0;
}
3247: 奶牛比赛
给定若干节点的关系，求能确定排名的奶牛的个数。
思路：一个点的排名可以确定，当且仅当它的上面节点数+它的下面节点数==n-1。建正反图对每个点依次统计。
点击查看代码
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
inline int read(){
int w=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
w=w*10+ch-'0';
ch=getchar();
}
return w*f;
}
int n,m,ans,sum_win,sum_lose;
bool vis[105];
vector<int> g[105],g1[105];
void dfs_win(int x){
vis[x]=1;
sum_win++;
for(int i=0;i<g1[x].size();i++){
int v=g1[x][i];
if(vis[v]) continue;
dfs_win(v);
}
}
void dfs_lose(int x){
vis[x]=1;
sum_lose++;
for(int i=0;i<g[x].size();i++){
int v=g[x][i];
if(vis[v]) continue;
dfs_lose(v);
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();
g[u].push_back(v);
g1[v].push_back(u);
}
for(int i=1;i<=n;i++){
sum_win=0,sum_lose=0;
memset(vis,0,sizeof(vis));
dfs_win(i);
memset(vis,0,sizeof(vis));
dfs_lose(i);
if(sum_win+sum_lose==n+1) ans++;
}
cout<<ans;
return 0;
}
3248: 灌水
有\(n\)块牧草，可以在当地花费\(wi\)挖一口井，也可一花费一定的钱连向有井的牧草。求使每块牧草都浇上水的最小代价。
思路：建立一个超级大井，将在当地挖井当作连向超级大井。然后最小生成树模板。