首页 > 代码库 > BZOJ2750: [HAOI2012]Road
BZOJ2750: [HAOI2012]Road
2750: [HAOI2012]Road
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 261 Solved: 113
[Submit][Status]
Description
C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。
Input
第一行包含两个正整数n、m
接下来m行每行包含三个正整数u、v、w，表示有一条从u到v长度为w的道路
Output
输出应有m行，第i行包含一个数，代表经过第i条道路的最短路的数目对1000000007取模后的结果
Sample Input
4 4
1 2 5
2 3 5
3 4 5
1 4 8
1 2 5
2 3 5
3 4 5
1 4 8
Sample Output
2
3
2
1
3
2
1
HINT
数据规模
30%的数据满足：n≤15、m≤30
60%的数据满足：n≤300、m≤1000
100%的数据满足：n≤1500、m≤5000、w≤10000
Source
题解：
60分是社交网络。。。居然还有升级版。。。考场上果断写60分暴力。。
yy了一两天结果发现题看错了。。。
以为是经过某个点的最短路的数目，果断写了topsort+dfs。。。简直不能再sb。。。
贴上我的sb代码
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 500+100 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct edge{int go,next,w;}e[2*maxm],e2[2*maxm]; 61 62 ll n,m,k,s,t,tot,q[maxn],d[maxn],head[maxn],head2[maxn],f[maxn],g[maxn],ans[maxn],inp[maxn]; 63 bool v[maxn]; 64 inline void insert(int x,int y,int z) 65 { 66 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z; 67 } 68 inline void insert2(int x,int y) 69 { 70 e2[++tot].go=y;e2[tot].next=head2[x];head2[x]=tot; 71 } 72 inline void add(ll &x,ll &y) 73 { 74 x+=y; 75 if(x>=mod)x%=mod; 76 } 77 void dfs(int x) 78 { 79 g[x]=f[x]; 80 for(int i=head2[x];i;i=e2[i].next){dfs(e2[i].go);add(g[x],g[e2[i].go]);}; 81 } 82 83 void work(int s) 84 85 { 86 87 for(int i=1;i<=n;++i) d[i]=inf; 88 89 memset(v,0,sizeof(v)); 90 91 int l=0,r=1,x,y;q[1]=s;d[s]=0; 92 93 while(l!=r) 94 95 { 96 97 x=q[++l];if(l==maxn)l=0;v[x]=0; 98 99 for(int i=head[x];i;i=e[i].next)100 101 if(d[x]+e[i].w<d[y=e[i].go])102 103 {104 105 d[y]=d[x]+e[i].w;106 107 if(!v[y]){v[y]=1;q[++r]=y;if(r==maxn)r=0;}108 109 }110 111 }112 memset(head2,0,sizeof(head2));tot=0;113 memset(inp,0,sizeof(inp));114 memset(f,0,sizeof(f));115 memset(g,0,sizeof(g));116 for1(x,n)117 for(int i=head[x],y;i;i=e[i].next)118 if(d[x]+e[i].w==d[y=e[i].go])insert2(x,y),inp[y]++;119 l=0;q[r=1]=s;f[s]=1;120 while(l<r)121 {122 int x=q[++l];123 for(int i=head2[x],y;i;i=e2[i].next)124 {125 inp[y=e2[i].go]--;126 add(f[y],f[x]);127 if(!inp[y])q[++r]=y;128 }129 }130 dfs(s);131 for1(i,n)add(ans[i],g[i]);ans[s]--;132 for1(i,n)cout<<i<<‘ ‘<<g[i]<<‘ ‘<<f[i]<<endl;133 cout<<"TTTTTTTTTTT"<<endl;134 }135 136 int main()137 138 {139 140 freopen("input.txt","r",stdin);141 142 freopen("output.txt","w",stdout);143 144 n=read();m=read();int x,y,z;145 for1(i,m)x=read(),y=read(),z=read(),insert(x,y,z);146 for1(i,n)work(i);147 for1(i,n)printf("%lld\n",ans[i]);148 149 return 0;150 151 }
纠正题意之后突然发现不会做了 QAQ。。。
膜拜了lyd的代码才知道，居然这么神。。。
dijkstra算法可以在算出最短路的同时将点的源点的距离排序，然后按照这个
从前往后枚举在最短路上的边可以得到源点到每个点的最短路的数目，记为a[i] （也就是我的topsort）
从后往前枚举在最短路上的边可以得到经过每个点有多少条最短路，记为b[i] （也就是我的dfs，我好像写错了23333）
然后对于每条边就是 +=a[e[i].from]*b[e[i].go]
图论题的技巧还有很多，我还太年轻23333
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 20000 26 27 #define maxm 50000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 struct edge{int go,next,w;}e[2*maxm],e2[2*maxm]; 61 62 ll n,m,k,s,t,tot,q[maxn],d[maxn],head[maxn],a[maxn],b[maxn],c[maxn],ans[maxn]; 63 bool v[maxn]; 64 inline void insert(int x,int y,int z) 65 { 66 e[++tot].go=y;e[tot].next=head[x];head[x]=tot;e[tot].w=z; 67 } 68 inline void add(ll &x,ll y) 69 { 70 x+=y; 71 if(x>=mod)x%=mod; 72 } 73 74 void dijkstra(int s) 75 76 { 77 78 priority_queue<pa,vector<pa>,greater<pa> >q; 79 80 for(int i=1;i<=n;i++)d[i]=inf; 81 82 memset(v,0,sizeof(v)); 83 84 d[s]=0;q.push(make_pair(0,s)); 85 int t=0; 86 87 while(!q.empty()) 88 89 { 90 91 int x=q.top().second;q.pop(); 92 93 if(v[x])continue;v[x]=1;c[++t]=x; 94 95 for(int i=head[x],y;i;i=e[i].next) 96 97 if(d[x]+e[i].w<d[y=e[i].go]) 98 99 {100 101 d[y]=d[x]+e[i].w;102 103 q.push(make_pair(d[y],y));104 105 }106 107 108 109 }110 memset(a,0,sizeof(a));a[s]=1;111 memset(b,0,sizeof(b));112 for1(i,t)b[c[i]]=1;113 for1(i,t)114 for(int j=head[c[i]],y;j;j=e[j].next)115 if(d[c[i]]+e[j].w==d[y=e[j].go])add(a[y],a[c[i]]);116 for3(i,t,1)117 for(int j=head[c[i]],y;j;j=e[j].next)118 if(d[c[i]]+e[j].w==d[y=e[j].go])add(b[c[i]],b[y]); 119 for1(i,n)120 for(int j=head[i],y;j;j=e[j].next)121 if(d[i]+e[j].w==d[y=e[j].go])add(ans[j],a[i]*b[y]); 122 }123 124 int main()125 126 {127 128 freopen("roadsw.in","r",stdin);129 130 freopen("roadsw.out","w",stdout);131 132 n=read();m=read();int x,y,z;133 for1(i,m)x=read(),y=read(),z=read(),insert(x,y,z);134 for1(i,n)dijkstra(i);135 for1(i,m)printf("%lld\n",ans[i]);136 137 return 0;138 139 }
BZOJ2750: [HAOI2012]Road
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。