• 第73期：图论-2022/7/19学习报告

    目录

    1. 链式向前星（数组模拟链表实现邻接表）

    2. 单源最短路径 Dijkstra算法(非负)（链式向前星+优先队列 优化）

    3. SPFA算法（可负）（Shortest Path Fast Algorithm）

    4. EX: POJ-3662-Telephone Lines

    做法一：分层图最短路

    做法二：二分答案+双端队列BFS

    做法三：二分答案+dijkstra

    5. EX CH6101 / P1073 最优贸易

    6. EX BZOJ2200 [Usaco2011 Jan] 道路和航线

    7. 任意两点间最短路径

    8. EX POJ1094 Sorting It All Out

    9. EX POJ1734 Sightseeing trip

    10. POJ3613 EX Cow Relays

    1. 链式向前星（数组模拟链表实现邻接表）

    链式向前星的空间复杂度：O(n+m)

    1. const int N=100010;//点
    2. const int M=1000010;//边
    3. int head[N],ver[M],edge[M],Next[M],d[N];//头节点，边的尾点，权值，指向的上一条边，点N到起点的距离
    4. int n,m,tot;
    5.  
    6. //加入有向边(x,y),权值为z
    7. void add(int x,int y,int z){
    8.     ver[++tot]=y,edge[tot]=z; // 真实数据
    9.     Next[tot]=head[x],head[x]=tot; //从表头x处插入
    10. }
    11.  
    12. //初始化
    13. void init(){
    14.     tot=0;
    15.     memset(head,0,sizeof head);
    16. }
    17.  
    18. //访问从x出发的所有边
    19. for(int i=head[x];i;i=Next[i]){
    20.     int y=ver[i],z=edge[i];
    21.     // 找到了一条有向边(x,y),权值为z
    22. }

    2. 单源最短路径 Dijkstra算法(非负)（链式向前星+优先队列 优化）

    1. //dijkstra单源最短路径：链式向前星+优先队列 O((m+n)logn)
    2. #include
    3. using namespace std;
    4. const int N=100010;
    5. const int M=1000010;
    6. const int INF=0x3f3f3f3f;
    7. int head[N],ver[M],edge[M],Next[M],d[N];//头节点，边的尾点，权值，指向的上一条边，点N到起点的距离
    8. bool v[N];
    9. int n,m,tot;
    10. priority_queueint,int> > pq;//大根堆，pair第二维为节点编号，第一维为dist的相反数（利用相反数变成小根堆）
    11. void add(int x,int y,int z){
    12.     ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
    13. }
    14. void init(){
    15.     tot=0;
    16.     memset(head,0,sizeof head);
    17. }
    18. void dijkstra(){
    19.     int s=1; // 起点
    20.     memset(d,0x3f,sizeof d); //dist数组
    21.     memset(v,0,sizeof v); //节点标记
    22.     d[s]=0;
    23.     pq.push(make_pair(-d[s],s)); //起点入队
    24.     while(pq.size()){
    25.         int x=pq.top().second; pq.pop(); //取出堆顶
    26.         if(v[x]) continue; //已经找到最短路
    27.         v[x]=1;
    28.         //扫描所有边
    29.         for(int i=head[x];i;i=Next[i]){
    30.             int y=ver[i],z=edge[i];
    31.             if(d[y]>d[x]+z){
    32.                 //更新，把新的二元组插入堆
    33.                 d[y]=d[x]+z;
    34.                 pq.push(make_pair(-d[y],y));
    35.             }
    36.         }
    37.     }
    38. }
    39. int main(){
    40.     while(cin>>n>>m&&n&&m){
    41.         init();
    42.         for(int i=1;i<=m;i++){
    43.             int x,y,z;
    44.             cin>>x>>y>>z;
    45.             add(x,y,z);
    46.             add(y,x,z);
    47.         }
    48.         dijkstra();
    49.         cout<
    50.     }
    51.     return 0;
    52. }

    3. SPFA算法（可负）（Shortest Path Fast Algorithm）

    1. #include
    2. using namespace std;
    3. const int INF=INT_MAX/10;
    4. const int N=100010;
    5. const int M=1000010;
    6. int head[N],ver[M],edge[M],Next[M],d[N];//头节点，边的尾点，权值，指向的上一条边，点N到起点的距离
    7. int Neg[M]; //判断负圈
    8. int pre[N]; //记录前驱节点
    9. bool inq[N]; //inq[i]=true表示节点i在队列中
    10. int n,m,tot;
    11. void print_path(int s,int t){ //打印从s到t的最短路径
    12.     if(s==t){cout<return;} //打印起点
    13.     print_path(s,pre[t]); //先打印前一个点
    14.     cout<//后打印当前点，最后打印的是终点t
    15. }
    16. void init(){
    17.     tot=0;
    18.     memset(head,0,sizeof head);
    19. }
    20. void add(int x,int y,int z){
    21.     ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
    22. }
    23. int spfa(int s){//s是起点
    24.     memset(Neg,0,sizeof Neg);
    25.     Neg[s]=1;
    26.     for(int i=1;i<=n;i++){d[i]=INF,inq[i]=false;} //初始化
    27.     d[s]=0; //起点到自己距离为0
    28.     queue<int> q;
    29.     q.push(s);
    30.     inq[s]=true; //起点进入队列
    31.     while(q.size()){
    32.         int u=q.front(); q.pop(); //队头出队
    33.         inq[u]=false; 
    34.         for(int i=head[u];i;i=Next[i]){
    35.             int v=ver[i],w=edge[i];
    36.             if(d[v]>d[u]+w){ //u的第i个邻居v,它借道u,到s更近
    37.                 d[v]=d[u]+w; //更新第i个邻居到s的距离
    38.                 pre[v]=u;
    39.                 if(!inq[v]){//邻居v更新状态了，但是它不在队列中，把它放进队列
    40.                     inq[v]=true;
    41.                     q.push(v);
    42.                     Neg[v]++;
    43.                     if(Neg[v]>n) return 1;  //出现负圈
    44.                 }
    45.             }
    46.         }
    47.     }
    48.     cout<//从s到n的最短距离
    49.     //print_path(s,n);
    50.     return 0;
    51. }
    52. int main(){
    53.     while(cin>>n>>m&&n&&m){
    54.         init();
    55.         while(m--){
    56.             int u,v,w;
    57.             cin>>u>>v>>w;
    58.             add(u,v,w);
    59.             add(v,u,w);
    60.         }
    61.         spfa(1);
    62.     }   
    63.     return 0;
    64. }

    4. EX: POJ-3662-Telephone Lines

    做法一：分层图最短路

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int n, p, k, vis[1010][1010], d[1010][1010];
    7. typedef pair<int,int> P;
    8. struct Nod {
    9.     int v, c, w;
    10.     bool operator < (const Nod &a) const {
    11.         return w > a.w;
    12.     }
    13. };
    14. vector
       G[1010];
    15. void spfa(int s) {
    16.     memset(d,-1,sizeof(d));memset(vis,0,sizeof(vis));
    17.     d[s][0] = 0;
    18.     priority_queue que;
    19.     que.push((Nod){s,0,0});
    20.     while(!que.empty()) {
    21.         int u = que.top().v, c = que.top().c; que.pop();
    22.         if(vis[u][c])continue;
    23.         vis[u][c] = 1;
    24.         for(int i = 0; i < G[u].size(); i ++) {
    25.             int v = G[u][i].first, w = G[u][i].second;
    26.             if(!vis[v][c] && (d[v][c] == -1 || d[v][c] > max(d[u][c],w))) {
    27.                 d[v][c] = max(d[u][c], w);
    28.                 que.push((Nod){v,c,d[v][c]});
    29.             }
    30.             if(c < k) {
    31.                 if(!vis[v][c+1] && (d[v][c+1] == -1 || d[v][c+1] > d[u][c])) {
    32.                     d[v][c+1] = d[u][c];
    33.                     que.push((Nod){v,c+1,d[v][c+1]});
    34.                 }
    35.             }
    36.         }
    37.     }
    38. }
    39. int main() {
    40.     ios::sync_with_stdio(false);
    41.     cin>>n>>p>>k;
    42.     int s = 1, t = n;
    43.     for(int i = 1; i <= p; i ++) {
    44.         int u, v, w;
    45.         cin>>u>>v>>w;
    46.         G[u].push_back(P(v,w));
    47.         G[v].push_back(P(u,w));
    48.     }
    49.     spfa(s);
    50.     int ans = 10000010;
    51.     for(int i = 0; i <= k; i ++) ans = min(ans,d[t][i]);
    52.     printf("%d\n",ans);
    53.     return 0;
    54. }

    做法二：二分答案+双端队列BFS

    对于边权只有0和1的最短路问题，可以使用双端队列BFS求解，复杂度O((N+P)\log MAX\_L)。

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. using namespace std;
    7. #define maxv 1005
    8. struct edge
    9. {
    10.     int v, w;
    11.     edge(int a=0,int b=0){v=a,w=b;}
    12. };
    13. int V, E, K, d[maxv];
    14. bool used[maxv];
    15. vector G[maxv];
    16.  
    17. int bfs(int m)
    18. {
    19.     memset(d, 0x3f, sizeof(d));
    20.     memset(used, 0, sizeof(used));
    21.     deque<int> q;
    22.     d[1] = 0;
    23.     q.push_back(1);
    24.     while (!q.empty())
    25.     {
    26.         int u = q.front();
    27.         q.pop_front();
    28.         if (used[u])
    29.             continue;
    30.         used[u] = 1;
    31.         for (int i = 0; i < (int)G[u].size(); ++i)
    32.         {
    33.             edge &e = G[u][i];
    34.             if (e.w > m)
    35.             {
    36.                 if (d[e.v] > d[u] + 1)
    37.                     d[e.v] = d[u] + 1, q.push_back(e.v);
    38.             }
    39.             else
    40.             {
    41.                 if (d[e.v] > d[u])
    42.                     d[e.v] = d[u], q.push_front(e.v);
    43.             }
    44.         }
    45.     }
    46.     return d[V];
    47. }
    48.  
    49. int main()
    50. {
    51.     scanf("%d%d%d", &V, &E, &K);
    52.     int maxl = 0;
    53.     for (int i = 0; i < E; ++i)
    54.     {
    55.         int u, v, w;
    56.         scanf("%d%d%d", &u, &v, &w);
    57.         maxl = max(maxl, w);
    58.         G[v].push_back(edge(u, w));
    59.         G[u].push_back(edge(v, w));
    60.     }
    61.     if (bfs(maxl))
    62.     {
    63.         puts("-1");
    64.         return 0;
    65.     }
    66.     int lb = -1, ub = maxl;
    67.     while (ub - lb > 1)
    68.     {
    69.         int mid = (lb + ub) >> 1;
    70.         if (bfs(mid) <= K)
    71.             ub = mid;
    72.         else
    73.             lb = mid;
    74.     }
    75.     printf("%d\n", ub);
    76.     return 0;
    77. }

    做法三：二分答案+dijkstra

    对于二分的判定，dijkstra求最短路，复杂度O(P\log N\log MAX\_L)。

    5. EX CH6101 / P1073 最优贸易

    1. #include
    2. using namespace std;
    3. const int N = 1e5 + 6, M = 1e6 + 6;
    4. int n, m, tot, Price[N], Ans;
    5. int Head[N], Side[M], Next[M], ans[N];
    6. int fHead[N], fSide[M], fNext[M], fans[N];
    7. priority_queueint, int> > q;
    8. priority_queueint, int> > fq;
    9.  
    10. int main() {
    11. 	cin >> n >> m;
    12. 	for (int i = 1; i <= n; i++) scanf("%d", &Price[i]);
    13. 	for (int i = 1; i <= m; i++) {
    14. 		int x, y, z;
    15. 		scanf("%d %d %d", &x, &y, &z);
    16. 		Side[++tot] = y;
    17. 		Next[tot] = Head[x];
    18. 		Head[x] = tot;
    19. 		fSide[tot] = x;
    20. 		fNext[tot] = fHead[y];
    21. 		fHead[y] = tot;
    22. 		if (z == 2) {
    23. 			Side[++tot] = x;
    24. 			Next[tot] = Head[y];
    25. 			Head[y] = tot;
    26. 			fSide[tot] = y;
    27. 			fNext[tot] = fHead[x];
    28. 			fHead[x] = tot;
    29. 		}
    30. 	}
    31. 	memset(ans, 0x3f, sizeof(ans));
    32. 	memset(fans, 0xcf, sizeof(fans));
    33. 	ans[1] = Price[1];
    34. 	fans[n] = Price[n];
    35. 	q.push(make_pair(-ans[1], 1));
    36. 	fq.push(make_pair(fans[n], n));
    37. 	while (q.size()) {
    38. 		int x = q.top().second;
    39. 		q.pop();
    40. 		for (int i = Head[x]; i; i = Next[i]) {
    41. 			int y = Side[i];
    42. 			if (ans[y] > ans[x]) {
    43. 				ans[y] = ans[x];
    44. 				ans[y] = min(ans[y], Price[y]);
    45. 				q.push(make_pair(-ans[y], y));
    46. 			}
    47. 		}
    48. 	}
    49. 	while (fq.size()) {
    50. 		int x = fq.top().second;
    51. 		fq.pop();
    52. 		for (int i = fHead[x]; i; i = fNext[i]) {
    53. 			int y = fSide[i];
    54. 			if (fans[y] < fans[x]) {
    55. 				fans[y] = fans[x];
    56. 				fans[y] = max(fans[y], Price[y]);
    57. 				fq.push(make_pair(fans[y], y));
    58. 			}
    59. 		}
    60. 	}
    61. 	for (int i = 1; i <= n; i++) Ans = max(Ans, fans[i]-ans[i]);
    62. 	cout << Ans << endl;
    63. 	return 0;
    64. }

    6. EX BZOJ2200 [Usaco2011 Jan] 道路和航线

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. using namespace std;
    9. typedef long long ll;
    10. const int N=3e5+10,M=3e5+10;
    11. const int INF=0x7f7f7f7f;
    12. inline int read()
    13. {
    14.     int x=0,f=1; char ch=getchar();
    15.     while(ch<'0' || ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    16.     while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    17.     return x*f;
    18. }
    19. struct edge
    20. {
    21.     int x,y,c,next;
    22. }a[N]; int len,last[N];
    23. void ins(int x,int y,int c)
    24. {
    25.     a[++len].x=x;a[len].y=y;a[len].c=c;
    26.     a[len].next=last[x];last[x]=len;
    27. }
    28.  
    29. bool v[N];
    30. int cnt;
    31. vector<int> has[N];
    32. int bl[N];
    33. void dfs(int x)
    34. {
    35.     v[x]=1;
    36.     has[cnt].push_back(x);
    37.     for(int k=last[x];k;k=a[k].next)
    38.     {
    39.         int y=a[k].y;
    40.         if(!v[y])bl[y]=bl[x],dfs(y);
    41.     }
    42. }
    43.  
    44. struct node
    45. {
    46.     int d,id;
    47.     bool operator <(const node &b) const
    48.     {
    49.         return d>b.d;
    50.     }
    51. };
    52.  
    53. priority_queueint,int> > q;
    54. int deg[N];
    55. int n,R,P,st;
    56. int list[M],head,tail;
    57. int dis[N];
    58. int main()
    59. {
    60. //	freopen("a.in","r",stdin);
    61. //	freopen("a.out","w",stdout);
    62.     n=read(); R=read(); P=read(); st=read();
    63.     len=0; memset(last,0,sizeof(last));
    64.     for(int i=1;i<=R;i++)
    65.     {
    66.         int x=read(),y=read(),c=read();
    67.         ins(x,y,c);
    68.         ins(y,x,c);
    69.     }
    70. //get scc
    71.     cnt=0; memset(bl,0,sizeof(bl));
    72.     memset(v,0,sizeof(v));
    73.     for(int i=1;i<=n;i++)
    74.         if(!v[i])
    75.         {
    76.             cnt++; bl[i]=cnt;
    77.             dfs(i);
    78.         }
    79. //rebuild to DAG
    80.     memset(deg,0,sizeof(deg));
    81.     for(int i=1;i<=P;i++)
    82.     {
    83.         int x=read(),y=read(),c=read();
    84.         ins(x,y,c); ins(bl[x]+n,bl[y]+n,c);
    85.     }
    86. //Get deg
    87.     head=1,tail=1;
    88.     list[1]=bl[st]+n;
    89.     memset(v,0,sizeof(v));
    90.     while(head<=tail)
    91.     {
    92.         int x=list[head];
    93.         for(int k=last[x];k;k=a[k].next)
    94.         {
    95.             int y=a[k].y;
    96.             if(!v[y])v[y]=1,list[++tail]=y;
    97.             deg[y-n]++;
    98.         }
    99.         head++;
    100.     }
    101. //Dij+Topsort
    102.     memset(dis,0x7f,sizeof(dis)); dis[st]=0;
    103.     memset(v,0,sizeof(v));
    104.     head=1,tail=1;
    105.     list[1]=bl[st];
    106.     while(head<=tail)
    107.     {
    108.         int cc=list[head];
    109. //        for(int i=1;i<=n;i++)if(bl[i]==cc)q.push(make_pair(-dis[i],i));
    110.         int siz=has[cc].size();
    111.         for(int i=0;ipush(make_pair(-dis[has[cc][i]],has[cc][i]));
    112.         while(q.size())
    113.         {
    114.             int x=q.top().second;q.pop();
    115.             if(v[x])continue;
    116.             v[x]=1;
    117.             for(int k=last[x];k;k=a[k].next)
    118.             {
    119.                 int y=a[k].y;
    120.                 if(bl[x]!=bl[y]){deg[bl[y]]--;
    121.                         if(deg[bl[y]]==0)list[++tail]=bl[y];}
    122.                 if(dis[y]>dis[x]+a[k].c)
    123.                 {
    124.                     dis[y]=dis[x]+a[k].c;
    125.                     if(bl[x]==bl[y])q.push(make_pair(-dis[y],y));
    126.                 }
    127.             }
    128.         }
    129.         
    130.         head++;
    131.     }
    132.  
    133.     for(int i=1;i<=n;i++)
    134.     {
    135.         if(dis[i]==INF) puts("NO PATH");
    136.         else printf("%d\n",dis[i]);
    137.     }
    138.     return 0;
    139. }

    7. 任意两点间最短路径

    Floyd算法 O(n^3)

    1. #include
    2. using namespace std;
    3. const int MAXN=105;
    4. const int INF=0x3f3f3f3f;
    5. int graph[MAXN][MAXN];//邻接矩阵存图
    6. int n,m;//n个点，m个边
    7. void floyd(){
    8.     int s=1; //定义起点
    9.     for(int k=1;k<=n;k++)
    10.         for(int i=1;i<=n;i++)
    11.             if(graph[i][k]!=INF)
    12.             for(int j=1;j<=n;j++)
    13.                 if(graph[i][j]>graph[i][k]+graph[k][j])
    14.                     graph[i][j]=graph[i][k]+graph[k][j];
    15.     cout<
    16. }
    17. int main(){
    18.     while(~scanf("%d%d",&n,&m)&&n&&m){
    19.         for(int i=1;i<=n;i++)
    20.             for(int j=1;j<=n;j++)
    21.                 graph[i][j]=INF;//任意两点间初始距离为无穷大
    22.         while(m--){
    23.             int a,b,c;
    24.             cin>>a>>b>>c;
    25.             graph[a][b]=graph[b][a]=c;//邻接矩阵存图
    26.         }
    27.         floyd();
    28.     }
    29.     return 0;
    30. }

    传递闭包

    1. //传递闭包 floyd算法
    2. #include
    3. using namespace std;
    4. const int MAXN=105;
    5. const int INF=0x3f3f3f3f;
    6. int graph[MAXN][MAXN];//邻接矩阵存图
    7. int n,m;//n个点，m个边
    8. void floyd(){
    9.     int s=1; //定义起点
    10.     for(int k=1;k<=n;k++)
    11.         for(int i=1;i<=n;i++)
    12.             if(graph[i][k]!=INF)
    13.             for(int j=1;j<=n;j++)
    14.                 graph[i][j] |= graph[i][k] & graph[k][j];
    15.     cout<
    16. }
    17. int main(){
    18.     while(~scanf("%d%d",&n,&m)&&n&&m){
    19.         for(int i=1;i<=n;i++)
    20.             for(int j=1;j<=n;j++)
    21.                 graph[i][j]=INF;//任意两点间初始距离为无穷大
    22.         while(m--){
    23.             int a,b,c;
    24.             cin>>a>>b>>c;
    25.             graph[a][b]=graph[b][a]=c;//邻接矩阵存图
    26.         }
    27.         floyd();
    28.     }
    29.     return 0;
    30. }

    8. EX POJ1094 Sorting It All Out

    9. EX POJ1734 Sightseeing trip

    10. POJ3613 EX Cow Relays

  • 相关阅读:
    手机自动直播系统源码交付与代理加盟注意事项解析！
    学习Python低手之路【三】python基础之函数
    折半查找的判定树
    专注于绘画，不受限制！尝试Growly Draw for Mac的快速绘画应用
    两个对象相等（==、equals、hashCode）详解
    Docker安装Jenkins
    计算机网络 第一章计算机网络体系结构
    想知道怎样p漫画脸？？用这两个方法，分分钟出片
    流媒体服务器
    【小题练手】----平方矩阵
  • 原文地址：https://blog.csdn.net/qq_57351574/article/details/125878388