admin 管理员组

文章数量: 1086019

路径和（cdq分治）

题目描述
对于一张有向图，定义d(u,v,w)为从u号点出发，不经过v号点，最终到达w号点的最短路径长度。如果不存在这样的路径，d(u,v,w)的值为−1。
你也可以认为d(u,v,w)是删去v点和其相关的边后，图中u到w的最短路。
现在给定这张有向图每两个点之间的有向边的长度（如果不存在连边则为−1），对于所有满足1≤x,y,z≤n,x≠y,y≠z的有序数对(x,y,z)，求它们d(x,y,z)的和。
你可以借助样例一解释来理解上面这句话的意思。
输入
第一行输入一个正整数n，表示该地区的点数。

接下来输入n行，每行输入n个整数。第i行第j个数Gi,j表示从i号点到j号的有向路径长度。如果这个数为−1，则表示不存在从i号点出发到j号点的路径。

输出
输出一个整数表示答案。

样例输入
3
0 1 -1
100 0 2
-1 -1 0

样例输出
100

提示

思路
每次分治假设(l,r)的区间为被删去的边，利用cdq分治递推即可得解

代码实现

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=305;
const int M=1e5+5;
const int INF=0x3f3f3f3f;
const ll LINF=5e18;
const ull sed=31;
const ll mod=19260817;
const double eps=1e-5;
const double PI=acos(-1.0);
typedef pair<int,int>P;
typedef pair<double,double>Pd;template<class T>void read(T &x)
{x=0;int f=0;char ch=getchar();while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;return;
}template <typename T> inline void write(T x) 
{if(x<0) putchar('-'), x = -x;if(x >= 10) write(x/10);putchar(x%10+'0');
}int n,mp[N][N];ll cal(int l,int r)
{ll ret=0;if(l==r){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=l && j!=l && i!=j){if(mp[i][j]>=INF) ret-=1;else ret+=mp[i][j];}}}return ret;}int tmp[N][N];int mid=(l+r)>>1;memcpy(tmp,mp,sizeof(mp));for(int k=mid+1;k<=r;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);ret+=cal(l,mid);memcpy(mp,tmp,sizeof(mp));for(int k=l;k<=mid;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);ret+=cal(mid+1,r);memcpy(mp,tmp,sizeof(mp));return ret;
}int main()
{//freopen("a.txt","r",stdin);read(n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){read(mp[i][j]);if(mp[i][j]==-1) mp[i][j]=INF;}}printf("%lld\n",cal(1,n));return 0;
}

本文标签： 路径和（cdq分治）

版权声明：本文标题：路径和（cdq分治） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686560541a10391.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。