Sgu - SpaceQ's Blog
Sgu 134
非常经典一题,我竟然交了那么十几次。。。TnT。。。
注意这么几个问题:
1、千万不要只连单向边否则遇上这种例子就跪了。。。
3
1 2
3 2
2、poj3107 sgu149 ural1056 poj3099 noi03逃学的孩子。。。1=6。。。
3、至于算法:ans[x]=max(x->son->size,n- x->size)
画个图就可以意会了 :)
4、从poj上搬运几组小数据
8 1 2 1 3 1 4 1 5 5 6 6 7 7 8 ans: 4 2 1 5
=====。。。。。==========。。。。。=====
10 1 2 1 3 1 4 1 5 5 6 6 7 7 8 5 9 4 10 ans: 5 2 1 5
=====。。。。。==========。。。。。=====
11 1 2 1 3 2 4 2 5 4 8 5 9 3 6 3 7 10 1 11 2 ans: 5 1 2
Sgu 103
最短路。。。就是在SPFA是要现算两点之间在这一时刻的dist(包括等的时间)。主要就是这个东东。。。其他就没什么了
写的时候差点要跪。。。但是竟然一次AC了~非常高兴。
听说Sgu不存代码,于是写日志吧。。
#include<cstdio> #include<cstring> #include<vector> #include<queue> #define rep(i,n) for(int i=0;i<(n);i++) #define maxn 307 #define pb push_back using namespace std; const int inf=~0u>>2; struct edge { int to,c; }; vector<edge>G[maxn]; void add(int from,int to,int c) { G[from].pb((edge){to,c}); G[to].pb((edge){from,c}); } int d[maxn],v[maxn],pre[maxn],s,t,r[maxn],T[maxn][2]; char C[maxn][3]; queue<int>Q; int Dist(int x,int i,int t) { int y=G[x][i].to; bool f1=C[x][0]=='B'?0:1,f2=C[y][0]=='B'?0:1; int r1=r[x],r2=r[y]; int t1=t%(T[x][0]+T[x][1]),t2=t%(T[y][0]+T[y][1]); if(r1>=t1)r1-=t1; else { r1+=T[x][f1^=1]; if(r1>=t1)r1-=t1; else { r1+=T[x][f1^=1]; r1-=t1; } } if(r2>=t2)r2-=t2; else { r2+=T[y][f2^=1]; if(r2>=t2)r2-=t2; else { r2+=T[y][f2^=1]; r2-=t2; } } if(r1==0)r1+=T[x][f1^=1]; if(r2==0)r2+=T[y][f2^=1]; if(f1==f2)return G[x][i].c; int c=3,tt=0; while(c--) { int mi=min(r1,r2); tt+=mi; r1-=mi;r2-=mi; if(r1==0)r1+=T[x][f1^=1]; if(r2==0)r2+=T[y][f2^=1]; if(f1==f2)return G[x][i].c+tt; } return inf; } void spfa() { memset(d,127,sizeof(d)); memset(v,0,sizeof(v)); Q.push(s); v[s]=true; d[s]=0; while(Q.size()) { int x=Q.front();Q.pop(); v[x]=false; rep(i,G[x].size()) { edge&e=G[x][i]; int dist=Dist(x,i,d[x]); if(dist==inf)continue; if(d[e.to]>d[x]+dist) { d[e.to]=d[x]+dist; pre[e.to]=x; if(!v[e.to]) { v[e.to]=true; Q.push(e.to); } } } } } vector<int>ans; int main() { //freopen("103.in","r",stdin); int n,m,a,b,c; scanf("%d%d",&s,&t); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s%d%d%d",&C[i],&r[i],&T[i][0],&T[i][1]); while(m--) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } spfa(); if(d[t]>=inf){printf("0\n");return 0;} //for(int i=1;i<n;i++)printf("%d ",d[i]); printf("%d\n",d[t]); int u=t; while(u!=s) { ans.pb(u); u=pre[u]; } ans.pb(s); for(int i=ans.size()-1;i>0;i--)printf("%d ",ans[i]); printf("%d\n",ans[0]); return 0; }