@TOC
声明：
本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+《挑战程序设计竞赛》的学习笔记，主要是因为我三本都买了按照《算法竞赛进阶指南》的目录顺序学习，包含书中的少部分重要知识点、例题解题报告及我个人的学习心得和对该算法的补充拓展，仅用于学习交流和复习，无任何商业用途。博客中部分内容来源于书本和网络（我尽量减少书中引用），由我个人整理总结（习题和代码可全都是我自己敲哒）部分内容由我个人编写而成，如果想要有更好的学习体验或者希望学习到更全面的知识，请于京东搜索购买正版图书：《算法竞赛进阶指南》——作者李煜东，强烈安利，好书不火系列，谢谢配合。
下方链接为学习笔记目录链接（中转站）
对于一张无向图，我们可以把无向边看作两条方向相反的有向边，所以对于图我们都将其作为有向图来看待。
一般用邻接表来存储图，空间复杂度为。
int nex[N],ver[N],head[N],edge[N],tot;
void add(int u,int v,int val){
ver[++tot] = v;
egde[tot] = val;
nex[tot] = head[u];
head[u] = tot;
}
for(int i= head[u];i;i = nex[i]){
int v = ver[i],val = edge[i];
} 单源最短路径
一、Dijkstra算法
经典的最短路算法，基于贪心思想的，适用于非负权值图的经过优先队列或者线段树优化后的的优秀算法。
Dijkstra可以使用优先队列或者set或者线段树优化，据说set优化的比优先队列常数小，更优。
解释一下松弛操作。
对于一个点的最短路可能被多次更新，那么肯定是只有最后一次是最优的，前面几次次优的更新的点还是会进入到优先队列中，但是这些点就没有使用的必要了，所以如果当前的点的最短路d，，不等于当前最优解，那么就直接跳过这个点即可。
1.常用的优先队列优化
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"# "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647000;
const ll N=500007;
struct Edge
{
ll v,w,next;//v:目的地,w:距离,next:下一个节点
}G[N];
ll head[N],cnt,n,m,s;
ll dis[N];//存距离
inline void addedge(ll u,ll v,ll w)//链式前向星存图
{
cnt++;
G[cnt].w=w;
G[cnt].v=v;
G[cnt].next=head[u];
head[u]=cnt;
}
struct node
{
ll d,u;//d是距离u是起点
bool operator<(const node& t)const//重载运算符
{
return d>t.d;
}
};
inline void Dijkstra()
{
for(register int i=1;i<=n;++i)dis[i]=mod;//初始化
dis[s]=0;
priority_queue<node>q;//堆优化
q.push((node){0,s});//起点push进去
while(!q.empty())
{
node tmp=q.top();q.pop();
ll u=tmp.u,d=tmp.d;
if(d!=dis[u])continue;//松弛操作剪枝
for(register int i=head[u];i;i=G[i].next)//链式前向星
{
ll v=G[i].v,w=G[i].w;
if(dis[u]+w<dis[v])//符合条件就更新
{
dis[v]=dis[u]+w;
q.push((node){dis[v],v});//沿着边往下走
}
}
}
}
int main()
{
scanf("%lld %lld %lld",&n,&m,&s);
for(register int i=1;i<=m;++i)
{
ll x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
addedge(x,y,z);//建图
}
Dijkstra();
for(register int i=1;i<=n;++i)
printf("%lld ",dis[i]);
printf("\n");
return 0;
} 2.更优的线段树优化
先考虑一下如果要优化dijkstra算法，优先队列需要哪些操作，让线段树来实现它们。查询队列是否为空，即还有没有要用来松弛其它点的点。取出dist值最小的元素，并删除修改一个点的dist值如果我们用线段树来维护dist数组，那么修改操作就是非常简单的单点修改。
我们只要用线段树来维护区间dist最小元素是谁(minpos，简称mp)即可。
但是线段树是不支持删除元素的，我们可以把dist[0]设置为恒为inf，如果要删除一个元素只要让它对应的叶节点mp值=0即可。这样的话就会保证查询dist最小元素的时候一定不会查到它；如果查到它就说明“优先队列”已经空了。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define maxn 100005
#define inf 2147483647
using namespace std;
typedef long long ll;
int read() {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
return x * f;
}
int n, m;
struct edge {
int to, w, nxt;
edge() {}
edge(int t, int ww, int nn) {to = t, w = ww, nxt = nn;}
}e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v, int w) {e[k] = edge(v, w, head[u]); head[u] = k++;}
ll ans[maxn];
struct node {
ll dis; int x;
node() {}
node(ll d, int xx) {dis = d, x = xx;}
}dis[maxn << 2];
//建树初始化，主要是编号也要返回所以要先预处理一下
void build(int p, int l, int r) {
if(l == r) {dis[p].x = l; return;}
int mid = l + r >> 1;
build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
dis[p].x = dis[p << 1].x;
}
void change(int p, int l, int r, int x, int y) {
if(l == r) {dis[p].dis = y; return;}
int mid = l + r >> 1;
if(x <= mid) change(p << 1, l, mid, x, y);
else change(p << 1 | 1, mid + 1, r, x, y);//单点修改的板子操作
if(dis[p << 1].dis < dis[p << 1 | 1].dis) dis[p] = dis[p << 1];
else dis[p] = dis[p << 1 | 1];
}
//因为用距离得到最小，但是需要的是编号，所以返回node
node ask(int p, int l, int r, int ls, int rs) {
if(ls <= l && r <= rs) {return dis[p];}
int mid = l + r >> 1; node ans = node(inf, 0), tmp;
if(ls <= mid) ans = ask(p << 1, l, mid, ls, rs);
if(rs > mid) {
node tmp = ask(p << 1 | 1, mid + 1, r, ls, rs);
if(ans.dis > tmp.dis) ans = tmp;
}
return ans;
}
int S;
void dij() {
for(int k = 1; k < n; k++) {//n-1次够用的。虽然我也不知道为什么最后n次跑的比n-1次还要快……
register int u = ask(1, 1, n, 1, n).x;
for(int i = head[u]; ~i; i = e[i].nxt) {
register int v = e[i].to;
if(ans[u] + e[i].w < ans[v]) {//最短路更新
ans[v] = ans[u] + e[i].w, change(1, 1, n, v, ans[v]);//单点修改
}
}
change(1, 1, n, u, inf);//取出来过后要赋值INF，以免再次取用
}
}
int main() {
memset(head, -1, sizeof head);
n = read(), m = read(), S = read();
for(int u, v, w, i = 1; i <= m; i++) u = read(), v = read(), w = read(), add(u, v, w);
//初始化
for(int i = 1; i <= (n << 2); i++) dis[i].dis = inf;
for(int i = 1; i <= n; i++) ans[i] = inf;
//线段树初始化，dis是线段树，ans是答案
build(1, 1, n);
change(1, 1, n, S, 0); ans[S] = 0;
dij();
for(int i = 1; i <= n; i++) printf("%lld ", ans[i]);
return 0;
}
3.最强的zkw线段树优化
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define dwn(I, A, B) for (int I = (A); I >= (B); --I)
#define erp(I, X) for (int I = head[X]; I; I = next[I])
const int maxn = 1e5 + 207, maxm = 2e5 + 207, inf = INT_MAX;
int v[maxm], w[maxm], head[maxn], next[maxm], tot;
int dist[maxn], mp[maxn << 2], M = 1;
int n, m, s;
template <typename T> inline void read(T& t) {
int f = 0, c = getchar(); t = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
if (f) t = -t;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
inline void ae(int x, int y, int z) { v[++tot] = y; w[tot] = z; next[tot] = head[x]; head[x] = tot; }
inline int cmp(int a, int b) { return dist[a] < dist[b] ? a : b; }
inline void build(int n) {
while (M < n + 2) M <<= 1;
mp[0] = n + 1;
}
inline void modify(int x, int nv) {
for (int i = x + M; dist[mp[i]] > nv; i >>= 1)
mp[i] = x;
dist[x] = nv;
}
inline void del(int x) {
for (mp[x += M] = 0, x >>= 1; x; x >>= 1)
mp[x] = cmp(mp[x << 1], mp[x << 1 | 1]);
}
inline void dijkstra(int s) {
rep(i, 0, n) dist[i] = inf;
build(n); modify(s, 0);
rep(t, 1, n - 1) {
int x = mp[1]; del(x);
erp(i, x) if (dist[v[i]] > dist[x] + w[i])
modify(v[i], dist[x] + w[i]);
}
}
int main() {
read(n),read(m),read(s);
rep(i, 1, m) {
int x, y, z; read(x),read(y),read(z); ae(x, y, z);
}
dijkstra(s);
rep(i, 1, n) write(dist[i]), putchar(' ');
puts("");
return 0;
} 二、SPFA算法
关于SPFA，它已经死了
国外一般叫“队列优化的算法”
SPFA算法一般在判断有无负环的时候用，并且如果该图中有负权值的话SPFA算法依旧可以正常工作。
SPFA算法的时间复杂度为，其中k是一个很小的常数，但是如果图是网格图等特殊构造的话，SPFA会退化到
的时间复杂度上，就会很容易就被卡掉了。
比如这道P4779 【模板】单源最短路径（标准版）就是专门来卡SPFA的嘤嘤嘤
所以SPFA要谨慎使用！
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e6+7;
const int M = 5e6+7;//注意这里数据范围要用M
int nex[M],ver[M],head[N],edge[M],tot;
void add(int u,int v,int val){
ver[++tot] = v;
edge[tot] = val;
nex[tot] = head[u];
head[u] = tot;
}
queue<int>q;
bool vis[N];
int d[N];
int n,m;
void spfa(int s){
//memset(d,0x3f,sizeof d);
for(int i = 1; i<= n;++i)
d[i] = 2147483647;
memset(vis,0,sizeof vis);
d[s] = 0;
vis[s] = 1;
q.push(s);
while(q.size()){
int x = q.front();
q.pop();
vis[x] = 0;
//扫描所有出边
for(int i = head[x];i;i = nex[i]){
int y = ver[i];
int z = edge[i];
if(d[y] > d[x] + z){
d[y] = d[x] + z;
if(!vis[y])//不在堆里就入堆并标记一下
q.push(y),vis[y] = 1;
}
}
}
}
int s;
int main()
{
cin>>n>>m>>s;
over(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
spfa(s);
over(i,1,n){
printf("%d ",d[i]);
}
return 0;
}
三、分层图最短路
1.（二维分层图）AcWing 340. 通信线路
可以免费k条，因为决策不同走的路可能不同，但是肯定是选k条都免费，即第k+1大权值最小的为答案。所以像动态规划一样就好。
下述题解来源链接：https://www.acwing.com/solution/content/2425/
题意理解
就是让你从起点1,到终点N,找一条代价最少的路径,每一条路径的代价是这条路径上的最大权值,且你可以指定一条路径上K条边权值为零.
思路解析
首先我们一眼就可以确定这道题目是的最短路算法.毕竟题目上白纸黑字上写着要,求出最短路.
首先我们一步步分析一下,这道题目的几个关键点.
1.这道题目的路径代价是什么?
我们发现,这里的路径不同于一般的最短路,每一条路径的最大边是这条路径的花费
2.题目中有些路径可以清零,这怎么办?
所有关于边的条件或者性质,其实都可以认为是一种特殊边.
这道题目中,有些边可以代价为0,那么我们不妨设置一种特殊边.
比如说是相连的边,他们代价是
,那么如果说我们让它免费,不就是又多了一条边,
只不过他们的代价是0?
所谓的路径可以免费,就是多了一条为0的重边.
所以这道题目的性质,转换一下就是,我们可以设置K条为权值0的边.
所以我们可以设置一个数组表示从1号节点到
号节点,途中经过
条权值为0的边,
新加入的边是非0边.
那么我们面对每一条新加入的边我们的
,其中
为
权值.
新加入的边是0边.
如果新加入的边是权值为0的边,显然是.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 3e3;
const int M = 5e4+7;//注意这里数据范围要用M
int d[N][N];
int n,m,k;
int nex[M],ver[M],head[N],edge[M],tot;
void add(int u,int v,int val){
ver[++tot] = v;
edge[tot] = val;
nex[tot] = head[u];
head[u] = tot;
}
queue<int>q;
bool vis[N];
void spfa(int s){
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[s][0] = 0;
vis[s] = 0;
q.push(s);
while(q.size()){
int x = q.front();
q.pop();
vis[x] = 0;
for(int i = head[x];i;i = nex[i]){
int y = ver[i],z = edge[i];
int w = max(d[x][0],z);//不同于往常的是每一条路径的 最大边 是这条路径的花费
if(d[y][0]>w){//先算普通的最短路
d[y][0] = w;
if(!vis[y])
q.push(y),vis[y] = 1;
}
//反正就是动规，暴力所有状态转移取最小，状态转移的方式就是可以免费。
//每次对每种路径都取一次最优
for(int p = 1;p <= k;++p){//p代表的是当前只能免费p条
int w = min(d[x][p-1],max(d[x][p],z));//d[x][p-1]就是这条从x到y的边免费，用掉一次机会，此时最多只能用p次，所以只能从p-1转移过来。max(d[x][p],z)是这条边不免费，然后根据题意取最大值，最后两种免费或者不免费的情况取最优即可。
//当前的状态是从x转移到y，然后看v(x->y)这条边免费或者不免费
if(d[y][p] > w){//能更新就更新。
d[y][p] = w;
if(!vis[y])
q.push(y),vis[y] = 1;
}
}
}
}
}
int main(){
cin>>n>>m>>k;
over(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
spfa(1);
int ans = 1e9+7;
over(i,0,k){//注意是从0开始，因为也可以不选
//就真答案并不在掌握之中
//其实就是分层图，应该是 k + 1 层
ans = min(ans,d[n][i]);
}
if(ans == 1e9+7)
puts("-1");
else printf("%d\n",ans);
return 0;
} 2.（直接分层图）P4568 [JLOI2011]飞行路线
和上一道几乎相同，只不过是这道题要的是普通的最短路，答案取的是和，以及这道题我用分层图的第二种方法，直接分成k+1层图
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 6e5+7;
int nex[N],ver[N],head[N],edge[N],tot;
int n,m,k,s,t;
int dist[N];
bool vis[N];
void init(){
memset(head,-1,sizeof head);
tot = 0;
memset(dist,0x3f,sizeof dist);
memset(vis,0,sizeof vis);
}
void add(int u,int v,int val){
ver[++tot] = v;
edge[tot] = val;
nex[tot] = head[u];
head[u] = tot;
}
void dijkstra(){
priority_queue<PII,vector<PII>,greater<PII> >q;
dist[1] = 0;
//vis[s] = 1;dijkstra和spfa不一样！这里不用标记，不然就走不动啦
q.push({dist[1],1});
while(q.size()){
PII now = q.top();//这种声明的变量后面不要用逗号运算符！！！
q.pop();
int u = now.second;
if(vis[u])continue;
vis[u] = 1;
for(int i = head[u]; i != -1 ;i = nex[i]){
int v = ver[i],val = edge[i];
if(!vis[v] && dist[v] > dist[u] + val){
dist[v] = dist[u] + val;
q.push({dist[v],v});
}
}
}
}
int main()
{
init();
scanf("%d%d%d",&n,&m,&k);
over(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
for(int j = 0;j <= k;++j){
add(x + j * n,y + j * n,z);//这一层和这一层连起来
add(y + j * n,x + j * n,z);
if(j != k){//只要还有就这一层和下一层连起来，并且权值为0（就意味着这条路免费）
add(x + j * n,y + (j + 1) * n,0);
add(y + j * n,x + (j + 1) * n,0);
}
}
}
dijkstra();
int ans = INF;//dijkstra只是更新了一个dis数组，答案需要我们自己找
over(i,0,k)
ans = min(ans,dist[n + i * n]);
printf("%d\n",ans);
return 0;
} 1.P1073 (NOIP2009)最优贸易
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5+7;
const int M = 2e6+7;
int h[N],rh[N],ver[M],nex[M],tot;
int dmin[N],dmax[N];
int price[N];
bool vis[N];
int n,m;
void init(){
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
}
void add(int *h,int u,int v){
ver[tot] = v;
nex[tot] = h[u];
h[u] = tot++;
}
void spfa(int *dis,int s,int *arr,bool flag){
memset(vis,0,sizeof vis);
if(flag)memset(dis,0x3f,sizeof dmin);//注意这一点,已经两次了
queue<int>q;
q.push(s);
vis[s] = 1;
dis[s] = price[s];
while(q.size()){
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = arr[u];~i;i = nex[i]){
int v = ver[i];
if((flag && dis[v] > min(dis[u],price[v])) || (!flag && dis[v] < max(dis[u],price[v]))){
if(flag)dis[v] = min(dis[u],price[v]);
else dis[v] = max(dis[u],price[v]);
if(!vis[v])q.push(v),vis[v] = 1;
}
}
}
}
int main()
{
init();
scanf("%d%d",&n,&m);
over(i,1,n)scanf("%d",&price[i]);
over(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(h,x,y),add(rh,y,x);//反图应该是反边
if(z == 2)add(h,y,x),add(rh,x,y);
}
spfa(dmin,1,h,true);
spfa(dmax,n,rh,false);
int ans = 0;
over(i,1,n)ans = max(ans,dmax[i]-dmin[i]);
printf("%d\n",ans);
return 0;
} 2.AcWing 342. 道路与航线
任意两点间最短路径
为了求图中任意两点之间的最短路径，我们当然可以把每一个点作为起点，求n次单源最短路，但是这种情况的图一般比较稠密，使用Floyd算法可以在的时间求解
一、Floyd算法
设表示“经过若干个编号不超过k的结点”从i到j的最短路长度。
Floyd算法的实质是动态规划。
k是阶段，所以必须放在最外层循环。
i和j是附加状态，应该放置于内层循环。
然后代码就非常简单了
int dis[1000][1000],n,m;
int main()
{
cin>>n>>m;
memset(dis,0x3f,sizeof dis);
for(int i = 1;i <= n;++i)
dis[i][i] = 0;
for(int i = 1;i <= m;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
dis[x][y] = min(dis[x][y],z);//可能会重复
}
for(int k = 1;k <= n;++k)
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
printf("%d ",dis[i][j]);
return 0;
} 1.AcWing 344. 观光之旅(POJ 1734 
)(Floyd求最小环)
给定一张无向图，求图中一个至少包含3个点的环，环上的节点不重复，并且环上的边的长度之和最小。
该问题称为无向图的最小环问题。
你需要输出最小环的方案，若最小环不唯一，输出任意一个均可。
获取最小环时j应当大于i，由对称性可知最终可求出正确答案.
环的性质是dis[i][j]+a[j][k]+a[k][i]，即呈环状.
需要开long long.
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e2+7;
const int M = 2e6+7;
vector<int>path;
int n,m;
int dis[N][N];//存最终的最短路长度
int a[N][N];//存单边的数据，因为要至少3条，所以应该更新的时候用单边
int pos[N][N];//存的是两点之间借的路
void get_path(int i,int j){
if(!pos[i][j])return ;
get_path(i,pos[i][j]);//可能左边还有，要按顺序
path.push_back(pos[i][j]);
get_path(pos[i][j],j);
}
int main()
{
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof a);
over(i,1,n)a[i][i] = 0;
over(i,1,m){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
a[x][y] = a[y][x] = min(a[x][y],z);
}
int ans = INF;
memcpy(dis,a,sizeof a);
over(k,1,n){
over(i,1,k-1)over(j,i+1,k-1){
if(ans > dis[i][j] + a[j][k] + a[k][i]){//至少3条边
ans = dis[i][j] + a[j][k] + a[k][i];//注意下标这里是一个环
path.clear();
path.push_back(i);//按顺序放入
get_path(i,j);//得到从i到j为了得到这样的最短路中实际借用的那些边
path.push_back(j);
path.push_back(k);
}
}
over(i,1,n)over(j,1,n){
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){
puts("No solution.");
return 0;
}
over(i,0,path.size()-1)
printf("%d ",path[i]);
puts("");
return 0;
}
二、传递闭包
在交际网络中，给定若干个元素和若干对二元关系，且这些关系具有传递性，通过这些传递性推导出尽量多的元素之间的关系的问题叫做传递闭包。
（传递性是在逻辑学和数学中，若对所有的 a，b，c ∈X，下述语句保持有效，则集合 上的二元关系 R 是传递的：「若a 关系到 b 且 b 关系到 c， 则 a 关系到 c。」- 百度百科）
也就是说，在一个元素集里，对你说一堆：某两个元素之间有关系。然后问你这些元素中一共有多少个元素有关系。
传递闭包概念的重点就是，这个关系必须是二元的，也就是说，其他的多元关系也一定要可以分解为几个二元关系的累积。
建立邻接矩阵dis，其中表示i和j有关系，0则表示i和j没有关系，特别的，dis[i,j]始终等于1。
可以使用Floyd算法来解决传递闭包问题
int dis[1000][1000],n,m;
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;++i)
dis[i][i] = 1;
for(int i = 1;i <= m;++i){
int x,y;
scanf("%d%d",&x,&y);
dis[x][y] = dis[y][x] = 1;
}
for(int k = 1;k <= n;++k)
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
dis[i][j] |= dis[i][k] & dis[k][j];
//把整个关系梳理出来
} POJ 1094.Sorting It All Out（传递闭包/拓扑排序）
给定 n个变量和 m个不等式。其中 n小于等于26，变量分别用前 n
的大写英文字母表示。不等式之间具有传递性，即若 A>B 且 B>C ，则 A>C。请从前往后遍历每对关系，每次遍历时判断：
- 如果能够确定全部关系且无矛盾，则结束循环，输出确定的次序；
- 如果发生矛盾，则结束循环，输出有矛盾；
- 如果循环结束时没有发生上述两种情况，则输出无定解。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#define over(i,s,t) for(register int i = s;i <= t;++i)
#define lver(i,t,s) for(register int i = t;i >= s;--i)
//#define int __int128
#define lowbit(p) p&(-p)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 50+7;
const int M = 2e6+7;
int n,m;
int dis[N][N];
int e[N][N];
bool flag;
int Floyd(){
memcpy(e,dis,sizeof dis);
over(k,1,n)over(i,1,n)over(j,1,n){
e[i][j] |= e[i][k] & e[k][j];
}
over(i,1,n)over(j,1,n)
if(e[i][j] == e[j][i] && e[i][j] && i != j)return -1;//有自环，矛盾
over(i,1,n)over(j,i,n)
if(e[i][j] == e[j][i] && !e[i][j] && i != j)return 0;//条件不足
return 1;
}
//传递闭包
void solve(){
memset(dis,0,sizeof dis);
flag = 1;
over(i,1,m){
char s[10];
scanf("%s",s);
dis[s[0]-'A'+1][s[2]-'A'+1] = 1;
int now = Floyd();
if(flag){
if(now == -1){
printf("Inconsistency found after %d relations.\n",i);
flag = 0;
}
else if(now == 1){
printf("Sorted sequence determined after %d relations: ",i);
pair<int,char>ans[N];
over(j,1,n){//先初始化
ans[j].first = 0;
ans[j].second = 'A' + j - 1;
}
over(j,1,n)over(k,1,n)
if(e[j][k])++ans[j].first;//因为关系是完全的，所以如果A最小那么A就跟剩下的所有字母都有一条关系A<B等等
sort(ans+1,ans+1+n);
lver(i,n,1)printf("%c",ans[i].second);
puts(".");
flag = 0;
}
}
}
if(flag)
puts("Sorted sequence cannot be determined.");
return ;
}
int main()
{
while(scanf("%d%d",&n,&m)&&n)solve();
return 0;
}
京公网安备 11010502036488号