//主要是根据各种网上资料做笔记
Floyd
\(f[i][j]\)：从\(i\)号顶点到\(j\)号顶点只经过前\(k\)号点的最短路程
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
f[i][j] = min(f[i][j],f[i][k]+f[k][j]);\(k\)是阶段 所以必须位于最外层 而\(i和j\)为附加状态
应用
给一个正权无向图，找一个最小权值和的环
这一定是一个简单环 考虑环上编号最大的结点\(u\)
f[u-1][x][y]和\((u,x), (u,y)\)共同构成了环。在 Floyd 的过程中枚举\(u\)，计算这个和的最小值即可
有向图的最小环问题 可枚举起点\(s=1\sim n\) 执行对优化的\(Dijsktra\)求解单源最短路径\(s\)一定为第一个被从堆中取出节点 扫描\(s\)所有出边 扩展、更新完成后 令\(d[s]=+\infty\) 然后继续求解 当s第二次被从堆中取出时 \(d[s]\)就是经过点\(s\)的最小环长度
POJ1734 sightseeing trip
找最小环 并输出一个最小环方案
#include<bits/stdc++.h>
using namespace std;
const int N=100+10,M=1e5+50,inf=0x3f3f3f3f;
int n,m,mp[N][N],dis[N][N],pos[N][N];
vector<int>path;
void get_path(int x,int y){
if(!pos[x][y]) return;
get_path(x,pos[x][y]);
path.push_back(pos[x][y]);
get_path(pos[x][y],y);
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
int ans=inf;
memset(mp,inf,sizeof(mp));
for(int i=1;i<=n;++i) mp[i][i]=0;
for(int i=1,x,y,w;i<=m;++i)
scanf("%d%d%d",&x,&y,&w),mp[x][y]=mp[y][x]=w;
memcpy(dis,mp,sizeof(mp));
for(int k=1;k<=n;++k){
for(int i=1;i<k;++i)
for(int j=i+1;j<k;++j)
if((long long)dis[i][j]+mp[i][k]+mp[k][j]<ans){
ans=dis[i][j]+mp[i][k]+mp[k][j];
path.clear(),path.push_back(i);
get_path(i,j);path.push_back(j),path.push_back(k);
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j],pos[i][j]=k;
}
if(ans==inf) return puts("No solution."),0;
for(int i=0;i<path.size();++i) printf("%d ",path[i]);
return 0;
}传递闭包
已知一个有向图中任意两点之间是否有连边，要求判断任意两点是否连通
按照 Floyd 的过程，逐个加入点判断一下。
只是此时的边的边权变为 \(1/0\)，而取 \(min\)变成了与运算。
再进一步用 bitset 优化，复杂度可以到 \(O\left(\dfrac{n^3}w\right)\)
for (k=1;k<=n;k++)
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
f[i][j]|=f[i][k]&f[k][j]; // std::bitset<SIZE> f[SIZE];
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (f[i][k]) f[i] = f[i] & f[k];POJ1094 sorting it all out
给定 n 个变量，m 个不等式。
不等式之间具有传递性，即若 A>B 且 B>C ，则 A>C。
判断这 m 个不等式是否有矛盾。
若存在矛盾，则求出 t 的最小值，满足仅用前 t 个不等式就能确定不等式之间存在矛盾。
若无矛盾，则判断这 m 个不等式是否能确定每一对变量之间的关系。
若能，则求出 t 的最小值，满足仅用前 t 个不等式就能确定每一对变量之间的大小关系。
==不得不说 lyd劳斯的代码真的很好 精简高效
\(mp[i][j]\)表示\(i<j\)
#include<bits/stdc++.h>
using namespace std;
const int N=100+10,M=1e5+50,inf=0x3f3f3f3f;
int n,m,x,y,mp[N][N],ok1,ok2;
char opt[10];
int main(){
freopen("in.txt","r",stdin);
//freopen("and.out","w",stdout);
while(~scanf("%d%d",&n,&m)&&(n+m)){
ok1=ok2=0;
memset(mp,0,sizeof(mp));
int i;
for(i=1;i<=n;++i) mp[i][i]=1;
for(i=1;i<=m;++i){
scanf("%s",opt),ok2=0;
x=opt[0]-'A'+1,y=opt[2]-'A'+1,mp[x][y]=1;
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
mp[j][k]|=mp[j][x]&mp[y][k];
for(int j=1;j<n;++j)
for(int k=j+1;k<=n;++k)
if(mp[j][k]&mp[k][j]){
printf("Inconsistency found after %d relations.\n",i);
j=n,ok1=1;break;
}
else if(!(mp[j][k]|mp[k][j])) ok2=1;
if(ok1) break;
if(!ok2){
printf("Sorted sequence determined after %d relations: ",i);
int a[N];
memset(a,0,sizeof(a)) ;
for(int j=1;j<=n;++j)
for(int k=j+1;k<=n;++k)
if(mp[j][k]) ++a[k];else ++a[j];
for(int j=0;j<n;++j)
for(int k=1;k<=n;++k)
if(a[k]==j) {putchar(k+'A'-1);break;}
puts(".");break;
}
}
if(i>m) puts("Sorted sequence cannot be determined.");
for(++i;i<=m;++i) scanf("%s",opt);
}
return 0;
}- else
POJ2613 cow relays
给定一张由T条边构成的无向图，点的编号为1~1000之间的整数。
求从起点S到终点E恰好经过N条边（可以重复经过）的最短路。
矩阵乘法和floyd的组合！
#include<bits/stdc++.h>
using namespace std;
const int N=200+10,M=1e6+10,inf=0x3f3f3f3f;
int n,m,s,t,vc[M];
struct mar{
int a[N][N];
mar operator *(mar &X){
mar c;
memset(c.a,inf,sizeof(c.a));
for(int i=1;i<=vc[0];++i)
for(int j=1;j<=vc[0];++j)
for(int k=1;k<=vc[0];++k)
c.a[i][j]=min(c.a[i][j],a[i][k]+X.a[k][j]);
return c;
}
}ans,mp;
void qpow(mar a,int b){
ans=a,--b;
while(b){
if(b&1) ans=ans*a;
a=a*a,b>>=1;
}
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d%d%d",&n,&m,&s,&t);
memset(mp.a,inf,sizeof(mp.a));
for(int i=1,x,y,w;i<=m;++i){
scanf("%d%d%d",&w,&x,&y);
x=(!vc[x]?(vc[x]=++vc[0]):vc[x]),
y=(!vc[y]?(vc[y]=++vc[0]):vc[y]);
mp.a[x][y]=mp.a[y][x]=min(w,mp.a[x][y]);
}
//for(int i=1;i<=vc[0];++i) mp.a[i][i]=0;
qpow(mp,n);
printf("%d",ans.a[vc[s]][vc[t]]);
return 0;
}
SCOI2008 天平
用floyd跑差分约束==
因为砝码大小只有1、2、3 所以未知时最大差值为2 最小差值为-2
由\(A+B>C+D\)可以转为\(A-C>D-B\) 然后就挨个判断就好了
注意判断等于时的条件
#include<bits/stdc++.h>
using namespace std;
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
const int N=50+10,M=1e6+10,inf=0x3f3f3f3f;
int n,A,B,c1,c2,c3,mx[N][N],mn[N][N];
char opt[N];
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&A,&B);
for(int i=1;i<=n;++i){
scanf("%s",opt+1);mx[i][i]=mn[i][i]=0;
for(int j=1;j<=n;++j)
if(j!=i){
if(opt[j]=='-') mn[i][j]=-2,mx[i][j]=-1;
else if(opt[j]=='+') mn[i][j]=1,mx[i][j]=2;
else if(opt[j]=='=') mx[i][j]=mn[i][j]=0;
else mn[i][j]=-2,mx[i][j]=2;
}
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
mn[i][j]=Max(mn[i][j],mn[i][k]+mn[k][j]),
mx[i][j]=Min(mx[i][j],mx[i][k]+mx[k][j]);
for(int i=1;i<=n;++i)
if(i!=A&&i!=B)
for(int j=i+1;j<=n;++j)
if(j!=A&&j!=B){
if(mn[A][i]>mx[j][B]||mn[B][i]>mx[j][A]) ++c1;
if(mn[i][A]>mx[B][j]||mn[i][B]>mx[A][j]) ++c3;
if(mn[A][i]==mx[A][i]&&mn[j][B]==mx[j][B]&&mn[A][i]==mn[j][B])++c2;
else if(mn[B][i]==mx[B][i]&&mn[j][A]==mx[j][A]&&mn[B][i]==mn[j][A])++c2;
}
printf("%d %d %d",c1,c2,c3);
return 0;
}