六道烦人的最短路(然而都是水题)
我也不准备翻译题目了(笑)
一些是最短路的变形(比如最长路,最短路中的最长边,判环),还有一些就是裸题了。
1860:找环,只需要把SPFA的松弛条件改一下即可,这里打的是BFS的。如果一个点入队次数大于n次,那么一定有环存在。
CODE
#include<cstdio> #include<cstring> using namespace std; typedef double DB; const int N=105; struct data { int to,next; DB r,c; }e[N*2]; int head[N],q[N*N*10],t[N],n,m,s,i,x,y,k=0; DB dis[N],v,r,c; bool vis[N]; inline void add(int x,int y,DB r,DB c) { e[++k].to=y; e[k].r=r; e[k].c=c; e[k].next=head[x]; head[x]=k; } int main() { memset(head,-1,sizeof(head)); memset(e,-1,sizeof(e)); scanf("%d%d%d%lf",&n,&m,&s,&v); for (i=1;i<=m;++i) { scanf("%d%d%lf%lf",&x,&y,&c,&r); add(x,y,r,c); scanf("%lf%lf",&c,&r); add(y,x,r,c); } int H=0,T=1; dis[s]=v; q[1]=s; vis[s]=t[s]=1; while (H<T) { int now=q[++H]; vis[now]=0; if (t[now]>n) { puts("YES"); return 0; } for (i=head[now];i!=-1;i=e[i].next) if (dis[e[i].to]<(dis[now]-e[i].r)*e[i].c) { dis[e[i].to]=(dis[now]-e[i].r)*e[i].c; if (!vis[e[i].to]) { q[++T]=e[i].to; vis[e[i].to]=1; t[e[i].to]++; } } } puts("NO"); return 0; }
3259:几乎相同的SPFA判负环,这里写了DFS(判环比BFS的快)
CODE
#include<cstdio> #include<cstring> using namespace std; const int N=10005; struct data { int to,next,v; }e[N]; int t,n,m,w,i,x,y,z,k,dis[N],vis[N],head[N]; bool flag; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void add(int x,int y,int z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } inline void SPFA(int now) { vis[now]=1; if (flag) return; for (int i=head[now];i!=-1;i=e[i].next) if (dis[e[i].to]>dis[now]+e[i].v) { if (vis[e[i].to]) { flag=1; return; } dis[e[i].to]=dis[now]+e[i].v; SPFA(e[i].to); } vis[now]=0; } int main() { read(t); while (t--) { memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); read(n); read(m); read(w); k=flag=0; for (i=1;i<=m;++i) { read(x); read(y); read(z); add(x,y,z); add(y,x,z); } for (i=1;i<=w;++i) { read(x); read(y); read(z); add(x,y,-z); } for (i=1;i<=n;++i) { if (flag) break; memset(dis,0,sizeof(dis)); SPFA(i); } if (flag) puts("YES"); else puts("NO"); } return 0; }
1062:枚举+SPFA,感觉SPFA写起来比DJ舒服,DJ还要开个堆。
对于等级的限制我们只需要枚举等级的左右端点即可。
CODE
#include<cstdio> #include<cstring> using namespace std; const int N=105; struct data { int to,next,v; }e[N*N]; int head[N],dis[N],vis[N],lev[N],v[N],q[N*10],t,n,c,k,i,j,num,p,l,r,ans=1e9; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void add(int x,int y,int z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } inline int min(int a,int b) { return a<b?a:b; } inline int SPFA(int s) { memset(dis,63,sizeof(dis)); dis[s]=0; vis[s]=1; q[1]=s; int H=0,T=1,res=1e9; while (H<T) { int now=q[++H]; vis[now]=0; for (int i=head[now];i!=-1;i=e[i].next) if (lev[e[i].to]>=l&&lev[e[i].to]<=r) if (dis[e[i].to]>dis[now]+e[i].v) { dis[e[i].to]=dis[now]+e[i].v; if (!vis[e[i].to]) q[++T]=e[i].to,vis[e[i].to]=1; } } for (int i=1;i<=n;++i) res=min(res,dis[i]+v[i]); return res; } int main() { memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); read(t); read(n); for (i=1;i<=n;++i) { read(v[i]); read(lev[i]); read(c); for (j=1;j<=c;++j) { read(num); read(p); add(i,num,p); } } for (i=1;i<=t+1;++i) { l=lev[1]+i-1-t; r=lev[1]+i-1; ans=min(ans,SPFA(1)); } printf("%d",ans); return 0; }
2253:求最短路中的最长边—>写DJ,改松弛条件—>炸了,改写最小生成树(Kruskal)找最短边
其实图论题重在建模!
CODE
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef double DB; const int N=205,INF=1e9; struct data { int x,y; DB s; }e[N*N]; int father[N],x[N],y[N],c,n,i,j,k; DB ans; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline DB calc(int a,int b) { return sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(double)(y[a]-y[b])*(y[a]-y[b])); } inline void add(int x,int y,DB z) { e[++k].x=x; e[k].y=y; e[k].s=z; } inline int comp(data a,data b) { return a.s<b.s; } inline int getfather(int k) { return father[k]==k?k:father[k]=getfather(father[k]); } int main() { for (;;) { read(n); if (!n) break; k=ans=0; for (i=1;i<=n;++i) read(x[i]),read(y[i]),father[i]=i; for (i=1;i<n;++i) for (j=i+1;j<=n;++j) add(i,j,calc(i,j)),add(j,i,calc(i,j)); sort(e+1,e+k+1,comp); for (i=1;i<=k;++i) { int fx=getfather(e[i].x),fy=getfather(e[i].y); if (getfather(1)==getfather(2)) break; if (fx!=fy) { father[fx]=fy; ans=e[i].s; } } printf("Scenario #%d Frog Distance = %.3lf ",++c,ans); } }
1125:最短路模板题,不过要枚举起点再跑SPFA(话说这是Floyd能解决的事,但我发现我好像不会Floyd了)
CODE
#include<cstdio> #include<cstring> using namespace std; const int N=105,INF=1e9; struct data { int to,next,v; }e[N*N]; int dis[N],head[N],q[N*N*10],n,i,j,m,k,x,y,ans,num; bool vis[N]; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void add(int x,int y,int z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } int main() { for (;;) { read(n); if (!n) break; ans=INF; num=k=0; memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); for (i=1;i<=n;++i) { read(m); for (j=1;j<=m;++j) { read(x); read(y); add(i,x,y); } } for (i=1;i<=n;++i) { for (j=1;j<=n;++j) dis[j]=INF; memset(vis,0,sizeof(vis)); dis[i]=0; vis[i]=1; q[1]=i; int H=0,T=1; while (H<T) { int now=q[++H]; vis[now]=0; for (j=head[now];j!=-1;j=e[j].next) { if (dis[e[j].to]>dis[now]+e[j].v) { dis[e[j].to]=dis[now]+e[j].v; if (!vis[e[j].to]) q[++T]=e[j].to,vis[e[j].to]=1; } } } int res=0; for (j=1;j<=n;++j) if (dis[j]>res) res=dis[j]; if (res<ans) ans=res,num=i; } if (ans==INF) puts("disjoint"); else printf("%d %d ",num,ans); } }
2240:同样的货币兑换,也是找环的过程。这里对于字符串懒得写hash了,直接开了map
CODE
#include<cstdio> #include<map> #include<string> #include<cstring> #include<iostream> using namespace std; typedef double DB; const int N=35; map <string,int> hash; struct data { int to,next; DB v; }e[N*N]; string s1,s2; DB dis[N],v; int head[N],n,i,k,m,t; bool vis[N],flag; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void add(int x,int y,DB z) { e[++k].to=y; e[k].v=z; e[k].next=head[x]; head[x]=k; } inline void SPFA(int now) { if (flag) return; vis[now]=1; for (int i=head[now];i!=-1;i=e[i].next) if (dis[e[i].to]<dis[now]*e[i].v) { if (vis[e[i].to]) { flag=1; return; } dis[e[i].to]=dis[now]*e[i].v; SPFA(e[i].to); } vis[now]=0; } int main() { for (;;) { read(n); if (!n) break; memset(e,-1,sizeof(e)); memset(head,-1,sizeof(head)); k=flag=0; for (i=1;i<=n;++i) { cin>>s1; hash[s1]=i; } read(m); for (i=1;i<=m;++i) { cin>>s1; scanf("%lf",&v); cin>>s2; add(hash[s1],hash[s2],v); } for (i=1;i<=n;++i) { if (flag) break; memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[i]=1; SPFA(i); } if (flag) printf("Case %d: Yes ",++t); else printf("Case %d: No ",++t); } return 0; }
准备结束图论专题!