hdu 5385 The path

http://acm.hdu.edu.cn/showproblem.php?pid=5385

 

题意：

给定一张n个点m条有向边的图，构造每条边的边权（边权为正整数），令d(x)表示1到x的最短路，使得存在点i(1<=i<=n)满足d(1)<d(2)<…<d(i)>d(i+1)>…>d(n)。

 

从两边向中间构造。

开始L=1，R=n

从L开始bfs，顺次构造L，L+1，L+2……

构造不动了再从R开始bfs，顺次构造R，R-1，R-2……

然后在从L开始……

直到L>=R

第j个bfs到的点，就令它的dis[i]=j

边u-->v的边权即为 dis[v]-dis[u] 的绝对值

 

 

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;#define N 100001int n,m;struct node {int u,v; }e[N];int front[N],nxt[N],to[N],tot;bool vis[N]; int dis[N];int L,R; int id;void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } }void add(int u,int v) {to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; }void bfs(int &s,int k) {while(s>0 && s<=n){if(!vis[s]) return;if(dis[s]!=-1) return;dis[s]=id++;for(int i=front[s];i;i=nxt[i]) vis[to[i]]=true;s+=k;} }int main() {int T,x;read(T);while(T--){tot=0;memset(front,0,sizeof(front));read(n); read(m);for(int i=1;i<=m;++i){read(e[i].u);read(e[i].v);add(e[i].u,e[i].v);}memset(vis,false,sizeof(vis));memset(dis,-1,sizeof(dis));vis[1]=true;L=1; R=n;id=0;while(L<R){bfs(L,1);bfs(R,-1);}for(int i=1;i<=m;++i) {x=abs(dis[e[i].u]-dis[e[i].v]);if(!x) x=n;printf("%d\n",x);}} }

 

 

转载于:https://www.cnblogs.com/TheRoadToTheGold/p/8443161.html

总结

以上是生活随笔为你收集整理的hdu 5385 The path的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。