闲来无事写点图

本文主要是介绍闲来无事写点图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01电路维修

https://www.acwing.com/problem/content/177/

题意

每次移动一个木棍，让其转方向，问最少转动几次能从左上角到右下角。

解析 (巧妙建立01权图+最短路问题）

难点在于建图，长和宽分别是$r,c$那么总共的点就有$(r+1)\times (c+1)$个顶点，每个顶点都需要建4条边，如果为“/”，那么说明右上角和左下角的代价为0，同理左上角和右下角的代价为1。因此这张图就建成了只有0 和 1 的有向图，只需要求解最短路即可。

• 迪杰斯特拉解法

#include<bits/stdc++.h>
using namespace std;
const int N=505*505;
const int inf=0x3f3f3f3f;
int h[N],e[4*N],ne[4*N],idx,w[4*N],dis[N];
int r,c;
int v[N];
void add(int a,int b,int c){e[++idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx;
}
struct node{int idx,dis;bool operator < (const node b)const{return dis>b.dis;}
};
int dj(){memset(dis,0x3f,sizeof dis);memset(v,0,sizeof v);priority_queue<node,vector<node>>q;dis[1]=0;q.push({1,0});while(!q.empty()){auto t=q.top();q.pop();if(v[t.idx])continue;v[t.idx]=1;for(int i=h[t.idx];i;i=ne[i]){int j=e[i];if(!v[j] && dis[j]>t.dis+w[i]){dis[j]=t.dis+w[i];q.push({j,dis[j]});}}}int end=(r+1)*(c+1);if(dis[end]>inf/2)return -1;else return dis[end];
}
void solve(){memset(h,0,sizeof h),idx=0;cin>>r>>c;for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){char x;cin>>x;int p1,p2,p3,p4;//左上右上左下右下p1=(c+1)*(i-1)+j,p2=(c+1)*(i-1)+j+1,p3=(c+1)*i+j,p4=(c+1)*i+j+1;int le=1;if(x=='/')le=0;add(p1,p4,!le),add(p4,p1,!le);add(p2,p3,le),add(p3,p2,le);}}int res=dj();if(res==-1){cout<<"NO SOLUTION"<<endl;}else{cout<<res<<endl;}
}
int main(){int t;cin>>t;while(t--){solve();}}

• 双端队列求解01图

int dj(){memset(v,0,sizeof v);int end=(r+1)*(c+1);//双端队列求解;deque<node>q;q.push_back({1,0});while(!q.empty()){node t=q.front();q.pop_front();v[t.id]=1;//出来的时候才能标记  因为怕权重1的标记了丢后面 0的反而访问不了if(t.id==end)return t.dis;for(int i=h[t.id];i;i=ne[i]){int j=e[i];if(!v[j]){if(w[i]==1){q.push_back({j,t.dis+1});}else{q.push_front({j,t.dis});}}}}return -1;
}

02 通信线路

1~n之间的某条路径，可以选择k条路径免费升级，剩下的路径只需要花费最贵的一条路径的价钱就能全部升级。
求最少需要多少钱能升级一条从1~n的路径。

https://www.acwing.com/problem/content/342/

解析（二分+最短路

发现答案具有单调性，如果花m元，那么大于m的路线都需要使用免费升级的机会，如果花的钱越多，需要使用免费升级的机会就越少。因此我们可以二分答案，对于每次check，如果路径费用大于mid，代表需要花费1（升级一次），小于mid就不需要花钱。最后看到终点需要升级几次才能到，且要保证花的钱最少，即最短路。

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int N=20005;
int h[N],e[N],w[N],ne[N],idx;
int dis[N];
int v[N];
struct node{int id,dis;bool operator < (const node b )const{return dis>b.dis;}
};
void add(int a,int b,int c){e[++idx]=b,ne[idx]=h[a],h[a]=idx,w[idx]=c;
}
//检测是否存在一条能到达终点 且超过mid的边的个数<=k
bool check(int mid){priority_queue<node,vector<node>>q;memset(v,0,sizeof v);memset(dis,0x3f,sizeof dis);dis[1]=0;q.push({1,0});while(!q.empty()){auto t=q.top();q.pop();if(v[t.id])continue;v[t.id]=1;for(int i=h[t.id];i;i=ne[i]){int j=e[i];int le=w[i]>mid;if(!v[j] && dis[j]>t.dis+le){dis[j]=t.dis+le;q.push({j,dis[j]});}}}if(dis[n]<=k)return true;return false;
}
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}int l=0,r=1e6;while(l<r){int mid=l+r>>1;if(check(mid)){r=mid;}else{l=mid+1;}}if(check(l)){printf("%d",l);}else{printf("-1");}
}

03 最优贸易

找到一条从1到n的路径，在这条路径上，在一个点购买商品，随后在后面一个点卖出，赚取之间的差价费用，贸易只能进行一次，问最多能收益多少。

解析 （SPFA+巧妙反向建图

用spfa可以维护从A出发到B点路径上的最小值，所以考虑方向建图，从起点出发维护路径最小值，从终点出发维护路径最大值，这样对于每个点，我们只需要res=max(res,mx[i]-mi[i])即可，反
图保证了这个点能到达终点。

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1e6+5;;
int h[N],rh[N],e[2*N],ne[2*N],idx;
int v[N];
int mi[N],mx[N];
int st[N];
//min[i]代表从家里出发到i这个位置的所有路径中的所有点的最小值 min[i]=inf 代表这个点无法从起点到达
//max[i]代表从这里到目标点这个位置中所有点的最大值。max[i]=0 代表这个点无法到终点
void add(int *h,int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
void getMx(){//从n出发 遍历反图queue<int>q;q.push(n);mx[n]=v[n];while(!q.empty()){int t=q.front();q.pop();st[t]=0;for(int i=rh[t];i;i=ne[i]){int j=e[i];if(mx[j]<max(v[j],mx[t])){mx[j]=max(v[j],mx[t]);if(!st[j]){q.push(j);st[j]=1;                    }}}}
}
void getMi(){//从1出发 遍历图memset(mi,0x3f,sizeof mi);queue<int>q;q.push(1);mi[1]=v[1];while(!q.empty()){int t=q.front();q.pop();st[t]=0;for(int i=h[t];i;i=ne[i]){int j=e[i];if(mi[j]>min(v[j],mi[t])){mi[j]=min(v[j],mi[t]);if(!st[j]){q.push(j);st[j]=1;}}}}    
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&v[i]);}for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(h,a,b);add(rh,b,a);if(c==2){add(h,b,a);add(rh,a,b);}}getMx();getMi();int res=0;for(int i=1;i<=n;i++){res=max(res,mx[i]-mi[i]);}cout<<res;return 0;
}

04 道路与航线

从起点n出发，有r条无向正权边，p条无向可能为负权边，求解从起点出发到各点的最短路

解析一（SPFA+SLF优化

由于有负权边，不能直接用dj，所以我们考虑用spfa，本题的数据专门卡了spfa，所以要用SLF优化，即用双端队列替代原本队列，当更新后的点x,dis[x]<dis[q.front()] 的时候，放到队头，反之放到队尾。这样做的好处是，优先利用负权边，可以更优先的得到结果

#include<bits/stdc++.h>
using namespace std;
const int N=25005,M=3*50005;
const int inf=0x3f3f3f3f;
int t,r,p,s;
int h[N], e[M], w[M], ne[M], idx;
int dis[N];
bool st[N];
void add(int a,int b,int c){e[++idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx;
}void spfa(){deque<int>q;memset(dis,0x3f,sizeof dis);q.push_back(s);dis[s]=0;while(!q.empty()){int t=q.front();q.pop_front();st[t]=0;for(int i=h[t];i;i=ne[i]){int j=e[i];if(dis[j]>dis[t]+w[i]){dis[j]=dis[t]+w[i];if(!st[j]){if(!q.empty() && dis[j]<dis[q.front()]){q.push_front(j);}else{q.push_back(j);}st[j]=1;}}}}
}
int main(){scanf("%d%d%d%d",&t,&r,&p,&s);for(int i=1;i<=r;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}for(int i=1;i<=p;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);        }spfa();for(int i=1;i<=t;i++){if(dis[i]>inf/2){printf("NO PATH\n");}else{printf("%d\n",dis[i]);}}
}

解析二 划分连通块拓扑序内部连通迪杰斯特拉求内部最短路

1. 首先我们不能直接用迪杰斯特拉
2. 我们发现对于刚开始的无向边，我们能划分处好几个连通块。
3. 后面添加的负权边后生成的图，保证了无环，因此负权边只会出现在两个连通块之间。
4. 我们可以对连通块拓扑排序，处理入度为0的连通块，对于每个连通块进行内部的迪杰斯特拉求解最短路。
5. 对于内部迪杰斯特拉，如果我们更新了一条从连通块A到连通块B的边，我们就减少相应的入度。
6. 当我们对某个连通块用迪杰斯特拉时，由于入度为0，所以一定保证没有外部的负权边影响，因此满足贪心的性质。
7. 从整体来看，拓扑排序保证了无后向性，使得每个连通块在内部求解时，不会被负边影响。

#include<bits/stdc++.h>
using namespace std;
const int N=25005,M=50005*3;
const int inf=0x3f3f3f3f;
int h[N],e[M],ne[M],idx,w[M];
int c[N];//c[i]代表所属的连通块;
int d[N];//入度;
int dis[N];
int t,r,p,s;
int bid=0;//连通块数目;
int st[N];
queue<int>bq;//存储连通块的;
vector<int>block[N];//第i个;void add(int a,int b,int c){e[++idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx;
}
void dfs(int x){c[x]=bid;block[bid].push_back(x);for(int i=h[x];i;i=ne[i]){int j=e[i];if(!c[j]){dfs(j);}}
}
//对每个连通快进行拓扑排序;
struct node{int nid,dis;bool operator < (node b)const{return dis>b.dis;}
};
void dj(int id){priority_queue<node,vector<node>>priorityQueue;for(auto f:block[id]){priorityQueue.push({f,dis[f]});}
//    cout<<"end"<<endl;while(!priorityQueue.empty()){node t=priorityQueue.top();priorityQueue.pop();if(st[t.nid])continue;st[t.nid]=1;for(int i=h[t.nid];i;i=ne[i]){int j=e[i];if(dis[j]>dis[t.nid]+w[i]){dis[j]=dis[t.nid]+w[i];if(c[j]==id){//目前只更新bid为id的连通块;priorityQueue.push({j,dis[j]});}}if(c[j]!=id){if(--d[c[j]]==0)bq.push(c[j]);}}}
}
//为了保证无后向性;
void topSort(){//初始化;memset(dis,0x3f,sizeof dis);dis[s]=0;//入度为0的连通块入队;for(int i=1;i<=bid;i++){if(!d[i]){bq.push(i);}}while(!bq.empty()){int t=bq.front();bq.pop();dj(t);}
}
int main(){scanf("%d%d%d%d",&t,&r,&p,&s);for(int i=1;i<=r;i++){int u,v,wg;scanf("%d%d%d",&u,&v,&wg);add(u,v,wg);add(v,u,wg);}for(int i=1;i<=t;i++){if(!c[i]){bid++;dfs(i);}}//读入负权图 维护每个连通分量的;for(int i=1;i<=p;i++) {int u, v, wg;scanf("%d%d%d", &u, &v, &wg);add(u, v, wg);d[c[v]]++;}topSort();for(int i=1;i<=t;i++){if(dis[i]>inf/2)printf("NO PATH\n");else printf("%d\n",dis[i]);}
}

方法二在特殊数据下快了6倍左右。
总结一下：比赛的时候先用SLF优化，如果发现tle了，用方法二重写一遍。

这篇关于闲来无事写点图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---