关于 最短路条数 和 边不可重复最短路条数问题 /hdu3599（边不可重复最短路）
2024-08-28 19:18:35
原先一直在做一道省赛题，由于题意错误理解成球最短路条数，误打误撞敲了最短路条数，又发现hdu3599（多校）求边不可重复最短路条数。下面说说俩种问题解法：
最短路条数：
求一个图一共一几条最短路径，思路：先从终点跑一边最短路，记录终点到到所有点最短距离（d【i】），然后从起点出发，dfs 按d[i]走（必是最短路径），一句话：我到终点的最短路条数=我的所有孩子到终点的最短路条数之和，这样只需一遍即可。这不知道是不是叫记忆化搜索？
边不可重复最短路径条数：（最短路+建新图之最大流）
hdu3599题意：求1-->n最短路条数，所有路径边不可重复。思路：边不可重复？？！！转为流量的为1 的话，求最大流啊（以后切记该方法，不可重复问题转最大流）！于是：先跑一遍最短路（随便从起点还是终点）,然后按老图中是最短路的边就在新图添加一条边，权为1，这样的话，从起点到终点跑最大流即为答案。
附代码：问题一：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n;
int e[100000][3];int head[2000];
int nume=0;
int d[2000];
const int inf =0x3f3f3f3f;
int vis[2000];
int inq[2000];
void adde(int a,int b,int w)
{
e[nume][0]=b;e[nume][1]=head[a];head[a]=nume;
e[nume++][2]=w;
e[nume][0]=a;e[nume][1]=head[b];head[b]=nume;
e[nume++][2]=w;
}
void spfa() //一遍求出终点到所有点的最短路长度d[i]。
{
queue<int>q;
int start;
start=n;
inq[start]=1;
q.push(start);
d[start]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
inq[cur]=0;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(d[cur]+e[i][2]<d[v])
{
d[v]=d[cur]+e[i][2];
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
return ;
}
long long counted[2000]; //点i到终点有几条最短路
int nowd[2000]; //从原点出发当前所走的长度
long long dfs(int cur) //记忆化收索？ 访问所有点一遍求出最短路条数，
{
if(cur==n)
return 1;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(nowd[cur]+e[i][2]+d[v]!=d[1]) //走这一步必需是最短的
continue;
if(!vis[v]) //没有走过
{
nowd[v]=nowd[cur]+e[i][2];
vis[v]=1;
counted[cur]+=dfs(v); //我所有孩子（是最短路径中）到目标的最短路之和为我到目标最短路
}
else
{
counted[cur]+=counted[v]; //该孩子最短路条数已经算出
}
}
return counted[cur];
}
int main()
{
int ta;
cin>>ta;
while(ta--)
{
scanf("%d",&n);
int aa,bb,cc;
for(int i=0;i<=n;i++)
{
head[i]=-1;
nowd[i]=d[i]=inf;
inq[i]=counted[i]=vis[i]=0;
}
nume=0;
while(~scanf("%d%d%d",&aa,&bb,&cc)&&(aa||bb||cc))
adde(aa,bb,cc);
spfa();
counted[n]=1;
nowd[1]=0;
vis[1]=1;
cout<<dfs(1)<<endl;
}
return 0;
}
问题2：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int n;
int e[2260000][3];int head[1510];
int nume=0;
int d[1510];
const int inf =0x3f3f3f3f;
int inq[1510];
void adde(int a,int b,int w) //原图
{
e[nume][0]=b;e[nume][1]=head[a];head[a]=nume;
e[nume++][2]=w;
e[nume][0]=a;e[nume][1]=head[b];head[b]=nume;
e[nume++][2]=w;
}
int ee[2260000][3];int head2[1510]; //新图
void adde2(int a,int b)
{
ee[nume][0]=b;ee[nume][1]=head2[a];head2[a]=nume;
ee[nume++][2]=1;
ee[nume][0]=a;ee[nume][1]=head2[b];head2[b]=nume;
ee[nume++][2]=0;
}
void spfa() //求出终点到所有点的最短路长度d[i]。
{
queue<int>q;
int start;
start=n;
inq[start]=1;
q.push(start);
d[start]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
inq[cur]=0;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(d[cur]+e[i][2]<d[v])
{
d[v]=d[cur]+e[i][2];
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
return ;
}
int vis[1510];int lev[1510];
int nowd[1510]; //从原点出发当前所走的长度
void dfs_getg(int cur) // 遍历一次老图获得新图
{
vis[cur]=1; //注意这里要标记访问，否则新图有重边！开始因为这个WA了好几遍!
if(cur==n)
return ;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(nowd[cur]+e[i][2]+d[v]!=d[1]) //走这一步必需是最短的
continue;
else //没有走过
{
nowd[v]=nowd[cur]+e[i][2];
adde2(cur,v);
if(!vis[v]) //这里在添加边之后方可进入，
dfs_getg(v);
}
}
return ;
} bool bfs() //dinic不解释
{
for(int i=0;i<=n;i++)
vis[i]=lev[i]=0;
queue<int>q;
q.push(1);
vis[1]=1;
while(!q.empty())
{
int cur=q.front();
q.pop();
for(int i=head2[cur];i!=-1;i=ee[i][1])
{
int v=ee[i][0];
if(!vis[v]&&ee[i][2]>0)
{
lev[v]=lev[cur]+1;
if(v==n) return 1;
vis[v]=1;
q.push(v);
}
}
}
return vis[n];
}
int dfs(int u,int minf)
{
if(u==n||minf==0)return minf;
int sumf=0,f;
for(int i=head2[u];i!=-1&&minf;i=ee[i][1])
{
int v=ee[i][0];
if(ee[i][2]>0&&lev[v]==lev[u]+1)
{
f=dfs(v,ee[i][2]<minf?ee[i][2]:minf);
ee[i][2]-=f;ee[i^1][2]+=f;
minf-=f;sumf+=f;
}
}
return sumf;
}
int dinic()
{
int sum=0;
while(bfs())
sum+=dfs(1,inf);
return sum;
}
int main()
{
int ta;
cin>>ta;
while(ta--)
{
scanf("%d",&n);
int aa,bb,cc;
for(int i=0;i<=n;i++)
{
head[i]=-1;
nowd[i]=d[i]=inf;
inq[i]=vis[i]=0;
}
nume=0;
while(~scanf("%d%d%d",&aa,&bb,&cc)&&(aa||bb||cc))
adde(aa,bb,cc);
if(n==1){cout<<0<<endl; continue;} // 1个点的时候要特判！！
spfa();
nume=0;
for(int i=0;i<=n;i++)
head2[i]=-1;
nowd[1]=0;
dfs_getg(1);
cout<<dinic()<<endl;
}
return 0;
}
附几组数据：
5
1 2 1
2 3 1
3 5 1
1 3 2
1 4 2
3 4 2
0 0 0
4
1 0 2
2 0 2
1 3 1
2 3 3
2 4 1
1 2 4
0 0 0
6
1 2 1
3 2 1
3 4 1
1 3 2
4 2 2
4 5 1
5 6 1
4 6 2
0 0 0
1
0 0 0
最新文章
- Angular2 NgModule
- NHibernate系列文章二十七：NHibernate Mapping之Fluent Mapping基础（附程序下载）
- wxPython安装错误问题：No module named wx
- 使用Unity制作游戏关卡的教程（三）
- epoll 回显服务器源码
- HAPROXY 配置项/配置实例
- [Redux] Generating Containers with connect() from React Redux (VisibleTodoList)
- 自定义上传按钮 <input type="file" name = "file"/> (将file隐藏在button下)
- 【gcd+数学证明】【HDU1722】 CAKE
- react视频入门
- Java的static和final关键字的用法
- gittalk报错Error
- Divide Candies CodeForces - 1056B （数学）
- 使用jQuery插件时避免重复引入jquery.js文件
- php生成毫秒时间戳的例子
- （转）Spring boot（一）：入门篇
- thread join和detach的区别
- netty ------------ 如果selector检测到一个channel可以读了
- Unity Shader 获取模型空间坐标
- zabbix 2.0 安装