$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n$ 个点 $m$ 条边的有向图。
点的编号 $1 \\sim n$。
图中可能包含重边和自环。
现在,我们要从点 $A$ 前往点 $B$,请你同时规划出尽可能多的最短路线,要求任意两条路线均不含公共边。
输出可以同时规划出的最短路线的最大数量。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行包含三个整数 $a,b,c$,表示存在一条从 $a$ 到 $b$ 的边,长度为 $c$。
最后一行包含两个整数 $A$ 和 $B$,表示起始点和目标点。
输出格式
每行输出一个答案,一个整数表示可以同时规划出的最短路线的最大数量。
数据范围
$1 \\le T \\le 65$,
$2 \\le n \\le 1000$,
$0 \\le m \\le 10^5$,
$1 \\le a,b \\le n$,
$1 \\le c \\le 1000$,
$1 \\le A,B \\le n$,
$A \\neq B$。
输入样例:
3
7 8
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
5 7 1
6 7 1
1 7
6 7
1 2 1
2 3 1
1 3 3
3 4 1
3 5 1
4 6 1
5 6 1
1 6
2 2
1 2 1
1 2 2
1 2
输出样例:
2
1
1
思路
- 先用
dijkstra算法
求出最短路径,并且筛掉那些不在最短路径上的边
;- 构建
网络流图
:对于在最短路径上的边$u\rightarrow v$,在网络流图中构建一条边 $u\rightarrow v$,且边权为$1$,表明这条边只能被走一次(同时需建立其反向边,其边权为0,方便Dinic算法
执行);- 以起点为
源点
,以终为汇点
,求出最大流
,即为答案。
代码
// Problem: 规划最短路
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4267/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-06 20:38:37
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 1010
#define MAXM 200010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int start_,end_;
int t,n,m;
int head[2][MAXN],ed[2][MAXM],nex[2][MAXM],val[2][MAXM],idx[2];
void add(int a,int b,int c,int op)
{
ed[op][idx[op]]=b;
val[op][idx[op]]=c;
nex[op][idx[op]]=head[op][a];
head[op][a]=idx[op]++;
}
struct node{
int a;
int b;
int c;
}s[MAXM];
int dist[MAXN],vis[MAXN];
void dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
dist[start]=0;
q.push(make_pair(0,start));
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[0][temp_pos];i!=-1;i=nex[0][i])
{
int j=ed[0][i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[0][i])
{
dist[j]=temp_dis+val[0][i];
q.push(make_pair(dist[j],j));
}
}
}
}
int level[MAXN],now[MAXN];
int bfs()
{
memset(level,-1,sizeof(level));
level[start_]=1;
memcpy(now,head[1],sizeof(head[1]));//当前弧优化初始化
queue<int> q;
q.push(start_);
while(q.size()>0)
{
int temp=q.front();
q.pop();
if(temp==end_)
return 1;
for(int i=head[1][temp];i!=-1;i=nex[1][i])
{
int j=ed[1][i];
ll vol=val[1][i];
if(vol>0&&level[j]==-1)
{
level[j]=level[temp]+1;
q.push(j);
}
}
}
return -1;
}
int dfs(int p,int flow)
{
if(p==end_)
return flow;
int temp=flow;//剩余的流量
for(int i=now[p];i!=-1&&temp>0;i=nex[1][i])
{
now[p]=i;//当前弧优化,更新当前弧
int j=ed[1][i];
int vol=val[1][i];
if(vol>0&&level[j]==level[p]+1)//往层数高的方向走
{
int c=dfs(j,min(vol,temp));//尽可能多的传递流量
temp-=c;//剩余流量减少
val[1][i]-=c;//更新空闲容量
val[1][i^1]+=c;//建立反向边,并合并权值
}
}
return flow-temp;//返回变化的流量
}
int Dinic()
{
int res=0;
while(bfs()!=-1)
res+=dfs(start_,inf);
return res;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> n >> m;
memset(head,-1,sizeof(head));
idx[0]=idx[1]=0;
for(int i=1;i<=m;i++)
{
cin >> s[i].a >> s[i].b >> s[i].c;
add(s[i].a,s[i].b,s[i].c,0);
}
cin >> start_ >> end_;
dijkstra(start_);
for(int i=1;i<=m;i++)
if(dist[s[i].b]==dist[s[i].a]+s[i].c)
{
add(s[i].a,s[i].b,1,1);//建立以a->b的权值为1的图
add(s[i].b,s[i].a,0,1);//建立反边
}
int res=Dinic();
cout << res << endl;
}
return 0;
}