POJ 1860&&3259&&1062&&2253&&1125&&2240

  六道烦人的最短路(然而都是水题)

  我也不准备翻译题目了(笑)

  一些是最短路的变形(比如最长路,最短路中的最长边,判环),还有一些就是裸题了。

  1860:找环,只需要把SPFA的松弛条件改一下即可,这里打的是BFS的。如果一个点入队次数大于n次,那么一定有环存在。

  CODE

#include<cstdio>
#include<cstring>
using namespace std;
typedef double DB;
const int N=;
struct data
{
int to,next;
DB r,c;
}e[N*];
int head[N],q[N*N*],t[N],n,m,s,i,x,y,k=;
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,-,sizeof(head));
memset(e,-,sizeof(e));
scanf("%d%d%d%lf",&n,&m,&s,&v);
for (i=;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=,T=;
dis[s]=v; q[]=s; vis[s]=t[s]=;
while (H<T)
{
int now=q[++H];
vis[now]=;
if (t[now]>n) { puts("YES"); return ; }
for (i=head[now];i!=-;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]=;
t[e[i].to]++;
}
}
}
puts("NO");
return ;
}

  3259:几乎相同的SPFA判负环,这里写了DFS(判环比BFS的快)

  CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
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=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',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]=;
if (flag) return;
for (int i=head[now];i!=-;i=e[i].next)
if (dis[e[i].to]>dis[now]+e[i].v)
{
if (vis[e[i].to]) { flag=; return; }
dis[e[i].to]=dis[now]+e[i].v;
SPFA(e[i].to);
}
vis[now]=;
}
int main()
{
read(t);
while (t--)
{
memset(e,-,sizeof(e));
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
read(n); read(m); read(w);
k=flag=;
for (i=;i<=m;++i)
{
read(x); read(y); read(z);
add(x,y,z); add(y,x,z);
}
for (i=;i<=w;++i)
{
read(x); read(y); read(z);
add(x,y,-z);
}
for (i=;i<=n;++i)
{
if (flag) break;
memset(dis,,sizeof(dis));
SPFA(i);
}
if (flag) puts("YES"); else puts("NO");
}
return ;
}

  1062:枚举+SPFA,感觉SPFA写起来比DJ舒服,DJ还要开个堆。

  对于等级的限制我们只需要枚举等级的左右端点即可。

  CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int N=;
struct data
{
int to,next,v;
}e[N*N];
int head[N],dis[N],vis[N],lev[N],v[N],q[N*],t,n,c,k,i,j,num,p,l,r,ans=1e9;
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',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,,sizeof(dis));
dis[s]=; vis[s]=; q[]=s;
int H=,T=,res=1e9;
while (H<T)
{
int now=q[++H];
vis[now]=;
for (int i=head[now];i!=-;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]=;
}
}
for (int i=;i<=n;++i)
res=min(res,dis[i]+v[i]);
return res;
}
int main()
{
memset(e,-,sizeof(e));
memset(head,-,sizeof(head));
read(t); read(n);
for (i=;i<=n;++i)
{
read(v[i]); read(lev[i]); read(c);
for (j=;j<=c;++j)
{
read(num); read(p);
add(i,num,p);
}
}
for (i=;i<=t+;++i)
{
l=lev[]+i--t; r=lev[]+i-;
ans=min(ans,SPFA());
}
printf("%d",ans);
return ;
}

  2253:求最短路中的最长边—>写DJ,改松弛条件—>炸了,改写最小生成树(Kruskal)找最短边

  其实图论题重在建模!

  CODE

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef double DB;
const int N=,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=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',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=;
for (i=;i<=n;++i)
read(x[i]),read(y[i]),father[i]=i;
for (i=;i<n;++i)
for (j=i+;j<=n;++j)
add(i,j,calc(i,j)),add(j,i,calc(i,j));
sort(e+,e+k+,comp);
for (i=;i<=k;++i)
{
int fx=getfather(e[i].x),fy=getfather(e[i].y);
if (getfather()==getfather()) break;
if (fx!=fy)
{
father[fx]=fy;
ans=e[i].s;
}
}
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++c,ans);
}
}

  1125:最短路模板题,不过要枚举起点再跑SPFA(话说这是Floyd能解决的事,但我发现我好像不会Floyd了)

  CODE

#include<cstdio>
#include<cstring>
using namespace std;
const int N=,INF=1e9;
struct data
{
int to,next,v;
}e[N*N];
int dis[N],head[N],q[N*N*],n,i,j,m,k,x,y,ans,num;
bool vis[N];
inline void read(int &x)
{
x=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',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=;
memset(e,-,sizeof(e));
memset(head,-,sizeof(head));
for (i=;i<=n;++i)
{
read(m);
for (j=;j<=m;++j)
{
read(x); read(y);
add(i,x,y);
}
}
for (i=;i<=n;++i)
{
for (j=;j<=n;++j)
dis[j]=INF;
memset(vis,,sizeof(vis));
dis[i]=; vis[i]=; q[]=i;
int H=,T=;
while (H<T)
{
int now=q[++H];
vis[now]=;
for (j=head[now];j!=-;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]=;
}
}
}
int res=;
for (j=;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\n",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=;
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=; char ch=getchar();
while (ch<''||ch>'') ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',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]=;
for (int i=head[now];i!=-;i=e[i].next)
if (dis[e[i].to]<dis[now]*e[i].v)
{
if (vis[e[i].to]) { flag=; return; }
dis[e[i].to]=dis[now]*e[i].v;
SPFA(e[i].to);
}
vis[now]=;
}
int main()
{
for (;;)
{
read(n);
if (!n) break;
memset(e,-,sizeof(e));
memset(head,-,sizeof(head));
k=flag=;
for (i=;i<=n;++i)
{
cin>>s1;
hash[s1]=i;
}
read(m);
for (i=;i<=m;++i)
{
cin>>s1; scanf("%lf",&v); cin>>s2;
add(hash[s1],hash[s2],v);
}
for (i=;i<=n;++i)
{
if (flag) break;
memset(dis,,sizeof(dis));
memset(vis,,sizeof(vis));
dis[i]=;
SPFA(i);
}
if (flag) printf("Case %d: Yes\n",++t); else printf("Case %d: No\n",++t);
}
return ;
}

  准备结束图论专题!

上一篇:WEBapi在IIS发布注意事项-发布错误


下一篇:004-Shell 基本运算符、算术运算符、关系运算符、布尔运算符、辑运算符、字符串运算符、文件测试运算符