1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<queue> 6 using namespace std; 7 const int N = 5005; 8 const int INF = 1e9+7; 9 inline int read() { 10 int x = 0; char ch = getchar(); 11 while(ch<'0' || ch>'9') ch = getchar(); 12 while(ch>='0' && ch<='9') x = x*10+ch-'0', ch = getchar(); 13 return x; 14 } 15 16 int n; 17 struct node{ 18 int y, z, nxt; 19 }e[N << 1]; 20 int h[N], tot=0; 21 inline void ad(int x, int y, int z){ 22 ++tot; 23 e[tot].y = y; e[tot].z = z; e[tot].nxt = h[x]; h[x] = tot; 24 } 25 26 int Dl,Dr; 27 int dis[N], vis[N]; 28 queue<int> q; 29 inline void bfs(int now) { 30 memset(vis,0,sizeof(vis)); 31 dis[now] = 0; 32 q.push(now); vis[now] = 1; 33 while(!q.empty()) { 34 int x = q.front(); q.pop(); 35 for(int i = h[x]; i; i = e[i].nxt){ 36 int y = e[i].y; if(vis[y])continue; 37 dis[y] = dis[x] + e[i].z; 38 vis[y] = 1; q.push(y); 39 } 40 } 41 } 42 inline void Get_d() { 43 bfs(1); 44 Dl=Dr=0; 45 for(int i=1; i<=n; ++i) if(dis[i] >= dis[Dl])Dl=i; 46 bfs(Dl); 47 for(int i=1; i<=n; ++i) if(dis[i] >= dis[Dr])Dr=i; 48 } 49 50 struct D_edge{ 51 int o,len; 52 }sew[N]; 53 int t_sew=0; 54 inline bool dfs(int st, int ed, int f) { 55 if(st == ed) { 56 ++t_sew; sew[t_sew].o=st; return true; 57 } 58 for(int i=h[st]; i; i=e[i].nxt) { 59 int y = e[i].y; if(y == f)continue; 60 if(dfs(y,ed,st)) { 61 ++t_sew; 62 sew[t_sew].o=st; sew[t_sew].len=e[i].z; 63 return true; 64 } 65 } 66 return false; 67 } 68 69 inline int son_d(int o) { 70 q.push(o); vis[o]=1; 71 int mx=0; 72 while(!q.empty()) { 73 int x=q.front(); q.pop(); 74 mx = max(mx, dis[x]); 75 for(int i=h[x]; i; i=e[i].nxt) { 76 int y = e[i].y; 77 if(!vis[y]) { 78 vis[y]=1; q.push(y); 79 dis[y] = dis[x]+e[i].z; 80 } 81 } 82 } 83 return mx; 84 } 85 86 struct son_tree{ 87 int d,r; 88 }str[N],sdr[N]; 89 90 inline void draw(){ 91 memset(dis,0,sizeof(dis)); 92 memset(vis,0,sizeof(vis)); 93 for(int i=1; i <= t_sew; ++i) vis[sew[i].o]=1; 94 } 95 96 int main() { 97 n=read(); 98 for(int i=1; i<n; ++i) { 99 int x,y,z; 100 x=read(); y=read(); z=read(); 101 ad(x,y,z); ad(y,x,z); 102 } 103 Get_d(); 104 dfs(Dl,Dr,Dl); 105 draw(); 106 int mid=1; 107 for(int i=2; i<=t_sew; ++i) { 108 int o = sew[i].o; 109 dis[o] = dis[ sew[i-1].o ]+sew[i].len; 110 int Di = son_d(o); 111 if(Di <= str[ sew[i-1].o ].d) { 112 str[o]=str[ sew[i-1].o ]; 113 } else { 114 int pos0 = sew[mid].o, pos1 = sew[mid+1].o; 115 while(mid<i && max( Di-dis[pos0], dis[pos0] ) > max( Di-dis[pos1], dis[pos1] )){ 116 ++mid; 117 pos0 = pos1; 118 pos1 = sew[mid+1].o; 119 } 120 str[o].r = max(dis[sew[mid].o],Di-dis[sew[mid].o]); 121 str[o].d = Di; 122 } 123 } 124 draw(); 125 mid = t_sew; 126 for(int i=t_sew-1; i>=1; --i) { 127 int o=sew[i].o; 128 dis[o] = dis[ sew[i+1].o ] + sew[i+1].len; 129 int Di = son_d(o); 130 if(Di <= sdr[ sew[i+1].o ].d) { 131 sdr[ sew[i].o ] = sdr[ sew[i+1].o ]; 132 } else { 133 int pos0 = sew[mid].o, pos1 = sew[mid-1].o; 134 while(mid>i && max( Di-dis[pos0], dis[pos0] ) > max( Di-dis[pos1], dis[pos1] )) { 135 --mid; 136 pos0 = pos1; 137 pos1 = sew[mid-1].o; 138 } 139 sdr[o].d = Di; 140 sdr[o].r = max( dis[ sew[mid].o ], Di-dis[ sew[mid].o ] ); 141 } 142 } 143 int minn=INF; 144 for(int i=1; i<=t_sew; ++i) { 145 int t_d=str[ sew[i].o ].r + sdr[ sew[i+1].o ].r + sew[i+1].len; 146 minn=min(minn, max( t_d, max(str[sew[i].o].d, sdr[sew[i+1].o].d) )); 147 } 148 printf("%d",minn); 149 } 150
运输计划
tywz day3 排队
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<queue> #include<algorithm> #define int long long using namespace std; int read(){ int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar(); return x*f; } const int N=125; const int mod=1e9+7; int n,a,b,c,d,e,mx; int f[N][2],g[N][2]; int s[N],tot=0; struct matrix{ int m[N][N]; }x; matrix mul(matrix A,matrix B){ matrix C; for(int i=1;i<=mx*4;++i) for(int j=1;j<=mx*4;++j){ C.m[i][j]=0; for(int k=1;k<=mx*4;++k) C.m[i][j]+=A.m[i][k]*B.m[k][j]; } return C; } matrix qpow(matrix A,int y){ matrix res; memset(res.m,0,sizeof(res.m)); for(int i=1;i<=120;++i){ res.m[i][i]=1; } for(;y;){ if(y&1)res=mul(res,A); A=mul(A,A);y>>=1; } return res; } signed main(){ n=read();a=read();b=read();c=read();d=read();e=read(); mx=max(a,max(b,c));f[0][1]=d;f[0][0]=e;g[0][0]=1,g[0][1]=1; for(int i=1;i<=mx;++i){ if(i>=a) f[i][1]+=f[i-a][1]+d*g[i-a][1],g[i][1]+=g[i-a][1]; f[i][0]%=mod;f[i][1]%=mod;g[i][0]%=mod;g[i][1]%=mod; if(i>=b)f[i][0]+=f[i-b][1]+e*g[i-b][1],g[i][0]+=g[i-b][1], f[i][1]+=f[i-b][0]+d*g[i-b][0],g[i][1]+=g[i-b][0]; f[i][0]%=mod;f[i][1]%=mod;g[i][0]%=mod;g[i][1]%=mod; if(i>=c)f[i][0]+=f[i-c][0]+e*g[i-c][0],g[i][0]+=g[i-c][0]; f[i][0]%=mod;f[i][1]%=mod;g[i][0]%=mod;g[i][1]%=mod; s[++tot]=f[i][0];s[++tot]=g[i][0];s[++tot]=f[i][1];s[++tot]=g[i][1]; } if(n<=mx){ printf("%lld",(f[n][0]+f[n][1])%mod); return 0; } memset(x.m,0,sizeof(x.m)); for(int i=1;i<=(mx-1)*4;++i){ x.m[i][i+4]=1; } x.m[(mx-1)*4+1][(mx-b)*4+3]=1;x.m[(mx-1)*4+1][(mx-b)*4+4]=e; x.m[(mx-1)*4+1][(mx-c)*4+1]=1;x.m[(mx-1)*4+1][(mx-c)*4+2]=e; x.m[(mx-1)*4+2][(mx-b)*4+4]=1;x.m[(mx-1)*4+2][(mx-c)*4+2]=1; x.m[(mx-1)*4+3][(mx-a)*4+3]=1;x.m[(mx-1)*4+3][(mx-a)*4+4]=d; x.m[(mx-1)*4+3][(mx-b)*4+1]=1;x.m[(mx-1)*4+3][(mx-b)*4+2]=d; x.m[(mx-1)*4+4][(mx-a)*4+4]=1;x.m[(mx-1)*4+4][(mx-b)*4+2]=1; matrix p=qpow(x,n-mx); int ans=0; for(int i=1;i<=mx*4;++i){ if(i%2==0)continue; ans+=s[i]*p.m[(mx-1)*4+1][i];ans%=mod; ans+=s[i]*p.m[(mx-1)*4+3][i];ans%=mod; } cout<<ans; }