1.Sightseeing Trip
思路借鉴：传送门
代码参考于：传送门
设环的形式是：i<->k<->j , i<-->j （i,j,k不同） floyd是典型的插点算法，每次插入点k，为此，在点k被[插入前]可计算i-j-k这个环 即此时中间节点为：1~k-1，即我们已经算出了任意i<->j的最短道路，中间经过的节点可以为 (1,2,3,...,k-1) 我们只需枚举所有以k为环中最大节点的环即可。 pos[i][j]:i~j的最短路中经过的点是k(即由这个状态转移过来)，且这个k是此路径中编号最大的点(除i,j)//根据Floyd算法实质决定 这条道路存在以下两条性质 1.在i~j的最短道路中，一定没有环(显然) 2.设i,j之间的最短道路经过点k(不同于i,j)，则i~k , k~j之间必然没有交集 2证： 如果有交集,设交点为k'(k' < k,根据Floyd算法实质相关)，则存在道路： i<->k'<->j , 由于[i<->k'] < [i<->k] , [j->k'] < [j->k] 显然这条道路更小，和假设矛盾所以一定没有交集 对于pos[i][j]，如果pos[i][j] == 0 : 说明i~j的最短路没有经过其他节点 因此借用性质2来求解道路，注意书写顺序，确保最后输出顺序正确 每次把i <-> j 之间划分成 i<->k , k<->j
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=110,INF=0x3f3f3f3f; int n,m; int pos[N][N],d[N][N],g[N][N]; int path[N],cnt; int res=INF; void get_path(int i,int j)//获取i~j中由哪个点转移过来的，i~k,k~j这样子 { int k=pos[i][j]; if(!k) return;//假如没有 //这里遍历的顺序随意，因为有Special judge get_path(i,k); path[cnt++]=k; get_path(k,j); } void floyd() { for(int k=1;k<=n;k++)//dp思路, 假设k是环上的最大点, i ~ k ~ j(Floyd的思想) { for(int i=1;i<k;i++)// 至少包含三个点，i，j，k不重合 for(int j=i+1;j<k;j++) if((ll)d[i][j]+g[i][k]+g[k][j]<res) { res=d[i][j]+g[i][k]+g[k][j];//更新环的最小值 cnt=0; //把路径上的点存下来，这里随便顺序，因为有Special judge path[cnt++]=i; path[cnt++]=k; get_path(i,j); path[cnt++]=j; } for(int i=1;i<=n;i++)//正常的Floyd更新最短距离 for(int j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; pos[i][j]=k;//记录由那个点更新过来的 } } } int main() { memset(d,0x3f,sizeof d); scanf("%d%d",&n,&m); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); d[a][b]=d[b][a]=min(d[a][b],c); } memcpy(g,d,sizeof d); floyd();//跑一遍Floyd算法求路径最小环 if(res==INF) puts("No solution");//假如无环 else { for(int i=0;i<cnt;i++) printf("%d ",path[i]); puts(""); } return 0; }
2.拯救大兵瑞恩
题意就是从左上角到右下角的最短距离，但是跟走迷宫不太一样，他有门的限制，所以要先开门得拿到相应的钥匙才行，走一步的消耗是1点体力
我们可以采用状态分析的方式进行考虑，d[x,y,state]所有从起点走到（x,y）这个格子且拥有的钥匙的状态是state的所有路线的集合
但是由于这里可能会有环 没有拓扑序 实际不能用dp做 只能转换为最短路
把两种转移方式看成两种边
因为这里只有0和1的边所以可以用双端队列广搜来做，然后答案就是d[n,m,0~2^p-1]
然后我们可以用一维的坐标边数两维的位置
#include<bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; const int N=11,M=N*N,E=400,P=1<<10; int h[M],e[E],ne[E],w[E],idx;//w记录的是门需要的钥匙 int n,m,p,k; int g[N][N],key[M]; int dist[M][P]; bool st[M][P]; set<pii> edges;//用来记录出现过的边 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void built() { int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int u=0;u<4;u++)//枚举四个方向 { int x=i+dx[u],y=j+dy[u]; if(x<=0||x>n||y<=0||y>m) continue;//越界 int a=g[i][j],b=g[x][y]; if(edges.count({a,b})==0) add(a,b,0);//假如不是门或者墙，则说明不用钥匙也能过去，即0就是不需要钥匙 } } int bfs()//双端队列广搜 { memset(dist,0x3f,sizeof dist); dist[1][0]=0;//从起点走，钥匙的状态是0 deque<pii> q; q.push_back({1,0}); while(q.size()) { pii t=q.front(); q.pop_front(); if(st[t.x][t.y]) continue; st[t.x][t.y]=true; if(t.x==n*m) return dist[t.x][t.y];//假如走到了终点直接返回 if(key[t.x])//假如这个位置有钥匙 { int state=t.y|key[t.x];//把这个钥匙的状态加上 if(dist[t.x][state]>dist[t.x][t.y]) { dist[t.x][state]=dist[t.x][t.y];//更新最短距离 q.push_front({t.x,state});//因为边权是0，则加到队头中去 } } for(int i=h[t.x];~i;i=ne[i])//枚举领边 { int j=e[i]; if(w[i]&&!(t.y>>w[i]-1&1)) continue;//假如这个位置有钥匙但是开不了门 if(dist[j][t.y]>dist[t.x][t.y]+1)//更新最短距离 { dist[j][t.y]=dist[t.x][t.y]+1; q.push_back({j,t.y});//因为边权是1则加到队尾 } } } return -1;//反之无解 } int main() { scanf("%d%d%d%d",&n,&m,&p,&k); for(int i=1,t=1;i<=n;i++)//将二维坐标映射到一维的点中 for(int j=1;j<=m;j++) g[i][j]=t++; memset(h,-1,sizeof h); while(k--) { int x1,y1,x2,y2,c; scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c); int a=g[x1][y1],b=g[x2][y2]; edges.insert({a,b}),edges.insert({b,a});//标记这两条边有门或者墙 if(c) add(a,b,c),add(b,a,c);//加入是门，则这条边加上这个门需要的钥匙 } built();//建立其他点之间的边权 int s; scanf("%d",&s); while(s--)//读入钥匙 { int x,y,id; scanf("%d%d%d",&x,&y,&id); key[g[x][y]]|=1<<id-1;//将这个位置的钥匙的状态存下来 } printf("%d\n",bfs()); return 0; }
3.架设电话线
看看别人的题解：传送门
二分价格最贵的那根线的费用，然后进行判断是否满足所选出的边小于等于K
#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=4e3+10; int h[N],ne[M],e[M],w[M],idx; int n,p,k; bool st[N]; int dist[N]; deque<int> q; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool bfs(int mid) { //清空上一层状态 q.clear(); memset(st,0,sizeof st); memset(dist,0x3f,sizeof dist); q.push_back(1); dist[1]=0; while(q.size()) { int t=q.front(); q.pop_front(); if(st[t]) continue; st[t]=true; for(int i=h[t];~i;i=ne[i]) { int j=e[i],d=w[i]>mid;//d是判断这条边是否大于mid if(dist[j]>dist[t]+d)//假如可以更新最少的边 { dist[j]=dist[t]+d; if(d) q.push_back(j);//假如是0则假如队头 else q.push_front(j);//反之加到队尾 } } } return dist[n]<=k;//看看所需的边是否小于等于k条 } void solve() { memset(h,-1,sizeof h); cin>>n>>p>>k; int a,b,c; while(p--) { cin>>a>>b>>c; add(a,b,c),add(b,a,c); } int l=0,r=1000001; while(l<r)//二分费用 { int mid=l+r>>1; if(bfs(mid)) r=mid; else l=mid+1; } if(l==1000001) puts("-1"); else cout<<l<<endl; } int main() { int T=1; while(T--) solve(); return 0; }
4.农场派对
这题就是正向求一遍最短路和逆向求一遍最短路，然后更新每头牛的最大值
#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=2e5+10; int h1[N],ne1[M],e1[M],w1[M],idx1; int h2[N],ne2[M],e2[M],w2[M],idx2; int n,m,x; bool st[N]; int dist1[N],dist2[N]; int q[N]; void add1(int a,int b,int c) { e1[idx1]=b,w1[idx1]=c,ne1[idx1]=h1[a],h1[a]=idx1++; } void add2(int a,int b,int c) { e2[idx2]=b,w2[idx2]=c,ne2[idx2]=h2[a],h2[a]=idx2++; } void spfa(int h[],int e[],int w[],int ne[],int dist[],int type)//spfa求最短路 { memset(st,0,sizeof st); if(type==1) memset(dist,0x3f,sizeof dist1); else memset(dist,0x3f,sizeof dist2); int hh=0,tt=0; q[tt++]=x; dist[x]=0; while(hh!=tt) { int t=q[hh++]; st[t]=false; if(hh==N) hh=0; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q[tt++]=j; st[j]=true; if(tt==N) tt=0; } } } } } void solve() { memset(h1,-1,sizeof h1); memset(h2,-1,sizeof h2); cin>>n>>m>>x; int a,b,c; while(m--) { cin>>a>>b>>c; add1(a,b,c); add2(b,a,c); } spfa(h1,e1,w1,ne1,dist1,1);//正向求一遍最短路 spfa(h2,e2,w2,ne2,dist2,2);//逆向求一遍最短路 int res=0; for(int i=1;i<=n;i++) res=max(res,dist1[i]+dist2[i]);//求每头牛来回的最大值 cout<<res<<endl; } int main() { int T=1; while(T--) solve(); return 0; }
5.Roadblocks
这题求次短路，在求最短路的时候顺便更新最短路即可
1.假如最短路可以更新，则次短路等于最短路的值，最短路更新为最小的值
2.假如次短路可以更新， 并且最短路是小于更新的值的，则更新次短路的值
#include<bits/stdc++.h> using namespace std; const int N=5e3+10,M=2e5+10; int h[N],e[M],ne[M],w[M],idx; int d1[N],d2[N];//d1是最短路，d2是次短路 int n,m; typedef struct { int u,dist; }pii; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void bfs() { memset(d1,0x3f,sizeof d1); memset(d2,0x3f,sizeof d2); queue<pii> q; d1[1]=0; q.push({1,0}); while(q.size()) { pii t=q.front(); q.pop(); int u=t.u,dist=t.dist; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(d1[j]>dist+w[i])//假如可以更新最短路 { d2[j]=d1[j];//次短路等于最短路 d1[j]=dist+w[i];//最短路更新为最小值 q.push({j,d1[j]}); } else if(d1[j]<dist+w[i]&&d2[j]>dist+w[i])//假如可以更新次短路，并且最短路严格小于更新的值 { d2[j]=dist+w[i];//更新次短路 q.push({j,d2[j]}); } } } } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } bfs(); printf("%d\n",d2[n]);//输出次短 return 0; }
6.最短路计数
假如在更新最短路时，某个点j可以由某个点t更新过来，则j这个点的最短路个数cnt[j]=cnt[t]，假如最短路的长度相等，则直接cnt[j]+=cnt[t].
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=4e5+10,mod=100003; int h[N],e[M],ne[M],idx; int q[N]; int n,m; int dist[N],cnt[N]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void bfs() { memset(dist,0x3f,sizeof dist); dist[1]=0; int hh=0,tt=0; q[0]=1; cnt[1]=1;//起点到起点最短路是1条 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+1)//假如可以更新最短路 { dist[j]=dist[t]+1; cnt[j]=cnt[t];//则最短路数等于更新过来的那个数 q[++tt]=j; } else if(dist[j]==dist[t]+1) cnt[j]=(cnt[j]+cnt[t])%mod;//假如相等则加上 } } } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); int a,b; while(m--) { scanf("%d%d",&a,&b); add(a,b),add(b,a); } bfs();//用bfs求最短路 for(int i=1;i<=n;i++) printf("%d\n",cnt[i]%mod);//输出每个点的最短路数 return 0; }
7.新年好
先两两求一遍最短路，求一个地方到另一个地方的最短路，在枚举5个拜访的顺序
由于有5个亲戚，先预处理出来5个亲戚到其他所有点的最短距离待会可以直接用，则可以dfs的全排列方式来进行拜访顺序，在把经过的点加上相应的距离即可，最后更新一遍最小值
#include<bits/stdc++.h> using namespace std; const int N=5e4+10,M=2e5+10; int n,m; int h[N],e[M],w[M],ne[M],idx; bool st[N]; int ans=0x3f3f3f3f; int dist[10][N]; int q[N]; int id[10];//存每个亲戚所在的站点 void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void spfa(int u,int dist[])//spfa求最短路 { memset(st,0,sizeof st); int hh=0,tt=0; q[tt++]=u; dist[u]=0; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } } void dfs(int cnt,int u,int sum)//枚举到u这个点，cnt个数，最短花费为sum { if(sum>=ans) return;//加入大于最短了 if(cnt==6)//加入枚举完5个亲戚了 { ans=sum; return; } for(int i=2;i<=6;i++)//全排列枚举5个亲戚 if(!st[i]) { st[i]=true; dfs(cnt+1,i,sum+dist[u][id[i]]); st[i]=false; } } void solve() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); id[1]=1;//自己在1站点 for(int i=2;i<=6;i++) scanf("%d",&id[i]); memset(dist,0x3f,sizeof dist); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } for(int i=1;i<=6;i++) spfa(id[i],dist[i]);//求每个亲戚到其他点的最短距离 memset(st,0,sizeof st); dfs(1,1,0);//枚举搜索顺序，全排列 printf("%d\n",ans); } int main() { int T=1; while(T--) solve(); return 0; }
8.最优贸易
DP+spfa求最短路
dmin[i]表示1~i中的最小价值，dmax[i]表示i~n中的最大价值
则我们可以在前i个最小值入手，在后i个抛售，则获利为dmax[i]-dmin[i]，然后求一遍最大即可
这题因为存在环不可用dijkstra来做
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=1e6+10; int hs[N],ht[N],e[M],ne[M],w[N],idx; int dmax[N],dmin[N]; int n,m; int q[N]; bool st[N]; void add(int h[],int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void spfa(int h[],int type) { int hh=0,tt=1; if(type)//求最大值的情况 { memset(dmax,-0x3f,sizeof dmax); q[0]=n; dmin[n]=w[n]; } else//求最小值的情况 { memset(dmin,0x3f,sizeof dmin); q[0]=1; dmax[1]=w[1]; } while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(type&&dmax[j]<max(dmax[t],w[j])||!type&&dmin[j]>min(dmin[t],w[j]))//假如最大值或者最小值可以更新 { if(type) dmax[j]=max(dmax[t],w[j]);//假如最大值则更新最大值 else dmin[j]=min(dmin[t],w[j]);//反之更新最小值 if(!st[t]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } } int main() { memset(hs,-1,sizeof hs); memset(ht,-1,sizeof ht); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&w[i]); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); add(hs,a,b),add(ht,b,a);//建一条正向的供求1~i中的最小用，建一条反向的供n~i中的求最大用 if(c==2) add(hs,b,a),add(ht,a,b);//假如是双向边，则两个都建 } spfa(hs,0);//求1~i中的最小值 spfa(ht,1);//求n~i中的最大值 int res=0; for(int i=1;i<=n;i++) res=max(res,dmax[i]-dmin[i]);//求一遍最大值 printf("%d\n",res); return 0; }
9.汽车加油行驶问题
借鉴于：传送门
这题是假的网络流，虽然说费用流也不是不可以写。。。
设disx,y,kdisx,y,k表示到达位置在(x,y)(x,y)，剩余油量为kk这个状态的最小代价。可知这个东西可以用SPFASPFA转移。
所以转移即可。
注意：题目中说经过油库时若油箱不满是强制加油的。没判这个就要WA两个点（而且跑出来答案小了）
#include<bits/stdc++.h> using namespace std; const int N=110; int n,K,A,B,C; int mp[N][N]; int dist[N][N][11];//表示走到x,y这个点剩余步数是k的最小花费 bool st[N][N][11]; int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};//左上右下 typedef struct { int x,y,k; }pii; queue<pii> q; void spfa() { memset(dist,0x3f,sizeof dist); dist[1][1][K]=0,q.push({1,1,K});//把起点放进队列中 while(q.size()) { pii t=q.front(); q.pop(); int x=t.x,y=t.y,k=t.k; st[x][y][k]=false; if(mp[x][y]&&k<K)//假如是加油站而且油量不够满 { if(dist[x][y][K]>dist[x][y][k]+A)//假如可以加油 { dist[x][y][K]=dist[x][y][k]+A; if(!st[x][y][K]) q.push({x,y,K}),st[x][y][K]=true; } continue;//表示加油站强制加油，则后面就不用更新了 } else { if(dist[x][y][K]>dist[x][y][k]+A+C)//表示新设立一个加油站，并加油 { dist[x][y][K]=dist[x][y][k]+A+C; if(!st[x][y][K]) q.push({x,y,K}),st[x][y][K]=true; } } if(k)//假如有油，则可以更新四个方向的最小值 { for(int i=0;i<4;i++) { int tx=x+dx[i],ty=y+dy[i]; if(x<1||x>n||y<1||y>n) continue;//越界 if(i<=1&&dist[tx][ty][k-1]>dist[x][y][k]+B)//假如倒着走，则得加上费用B，而且能更新最小值 { dist[tx][ty][k-1]=dist[x][y][k]+B; if(!st[tx][ty][k-1]) q.push({tx,ty,k-1}),st[tx][ty][k-1]=true; } if(i>1&&dist[tx][ty][k-1]>dist[x][y][k])//正着走，不用加费用，而且能更新最小值 { dist[tx][ty][k-1]=dist[x][y][k]; if(!st[tx][ty][k-1]) q.push({tx,ty,k-1}),st[tx][ty][k-1]=true; } } } } } int main() { scanf("%d%d%d%d%d",&n,&K,&A,&B,&C); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]); spfa();//跑一遍spfa求最小花费 int ans=dist[n][n][0]; for(int i=1;i<=K;i++) ans=min(ans,dist[n][n][i]);//更新最后一个点剩余i步是最小花费 printf("%d\n",ans); return 0; }
10.道路和航线
#include<bits/stdc++.h> using namespace std; #define x first #define y second typedef pair<int,int> pii; const int N=25010,M=150010; int h[N],e[M],ne[M],w[M],idx; int n,m1,m2,s; int id[N],bcnt,din[N];//id是由点找连通块，bcnt是连通块的个数，din表示某个连通块的入度 int dist[N]; bool st[N]; vector<int> block[N];//存某个连通块中的点 queue<int> q; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int ver)//当前点为u，当前连通块是ver { block[ver].push_back(u);//放进连通块中 id[u]=ver;//标记这个点属于那个连通块 for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(!id[j]) dfs(j,ver);//假如没搜索过 } } void dijkstra(int ver) { priority_queue<pii,vector<pii>,greater<pii>> heap; for(int t:block[ver]) heap.push({dist[t],t});//把连通块中的所有点加入堆中 while(heap.size()) { pii t=heap.top(); heap.pop(); int u=t.y,d=t.x; if(st[u]) continue; st[u]=true; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(dist[j]>d+w[i]) { dist[j]=d+w[i]; if(id[j]==id[u]) heap.push({dist[j],j});//加入是同一个连通块则继续加入堆中更新 } if(id[j]!=id[u]&&--din[id[j]]==0) q.push(id[j]);//加入不是一个连通块并且入度减为0了，则把这个连通块加入队列中 } } } void topsort() { memset(dist,0x3f,sizeof dist); dist[s]=0; for(int i=1;i<=n;i++)//把所有入度为0的连通块加入队列中 if(!din[i]) q.push(i); while(q.size()) { int t=q.front(); q.pop(); dijkstra(t);//连通块内部跑一遍dijkstra } } int main() { memset(h,-1,sizeof h); scanf("%d%d%d%d",&n,&m1,&m2,&s); int a,b,c; while(m1--)//道路 { scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } for(int i=1;i<=n;i++)//获取连通块，即互相能到达的点为1个连通块 if(!id[i])//假如没有搜索过 dfs(i,++bcnt);//开辟新的连通块 while(m2--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); din[id[b]]++;//表示b这个连通块的入度++ } topsort();//跑一遍拓扑序 for(int i=1;i<=n;i++) if(dist[i]>=0x3f3f3f3f/2) puts("NO PATH");//假如数比较大，说明没有路径 else printf("%d\n",dist[i]); return 0; }
