精华内容
下载资源
问答
  • floyd求最小环

    2019-10-02 14:33:55
    hdu1599 floyd求最小环 其实floyd求最小环就相当于找出一个一条只包括1到k-1中节点的路径,然后把这个路径与k这个节点相连。这样是正确的原因是,最小环中一定有一个最大节点k,当最外层节点是k时,我们一定会枚举到...

    hdu1599 floyd求最小环

    其实floyd求最小环就相当于找出一个一条只包括1到k-1中节点的路径,然后把这个路径与k这个节点相连。这样是正确的原因是,最小环中一定有一个最大节点k,当最外层节点是k时,我们一定会枚举到k两端的两个节点,这样就统计出了答案。至于为什么不能直接用最短路径,而是要用前k-1个节点跑出来的最短路径,是因为不知道最短路径有没有经过k。

    反正这个算法是对的就对了。

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    const int maxn=105, INF=1e9;
    int n, m, minm, dis[maxn][maxn], ori[maxn][maxn];
    
    int main(){
        while (~scanf("%d%d", &n, &m)){
            for (int i=1; i<=n; ++i)
                for (int j=1; j<=n; ++j){
                    dis[i][j]=dis[j][i]=INF;
                    ori[i][j]=ori[j][i]=INF;
                }
            int x, y, v; minm=INF;
            for (int i=1; i<=m; ++i){
                scanf("%d%d%d", &x, &y, &v);
                ori[x][y]=ori[y][x]=min(ori[x][y], v);
                dis[x][y]=dis[y][x]=min(ori[x][y], v);
            }
            for (int k=1; k<=n; ++k){
                for (int i=1; i<=n; ++i)
                    for (int j=1; j<=n; ++j)
                    //三点都要不相同。ij不一定,但是相同的点ori一定是INF。
                    //所以只需要判断i!=j。
                    if (i!=j&&dis[i][j]!=INF&&ori[j][k]!=INF
                            &&ori[k][i]!=INF)
                        minm=min(minm, dis[i][j]+ori[j][k]+ori[k][i]);
                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]);
            }
            if (minm==INF) printf("It's impossible.\n");
            else printf("%d\n", minm);
        }
    }

    转载于:https://www.cnblogs.com/MyNameIsPc/p/7905673.html

    展开全文
  • Floyd求最小环

    2019-11-17 17:35:57
    Floyd求最小环 原理: 当第三层循环到点k时, 所有点之间的最短路只通过[1,k)更新, 记disu,vdis_{u,v}disu,v​是从u到v且仅经过编号在区间[1,k)[1,k)[1,k)中的点的最短路。 最小环至少要有3个顶点, 最小环通过一条最...

    Floyd求最小环

    原理:

    1. 当第三层循环到点k时, 所有点之间的最短路只通过[1,k)更新, 记disu,vdis_{u,v}是从uv仅经过编号在区间[1,k)[1,k)中的点的最短路。
    2. 最小环至少要有3个顶点, 最小环通过一条最短路枚举一个点的2条边来更新 ans=min(ans,disu,v+g[u][k]+g[k][v])ans=min(ans,dis_{u,v}+g[u][k]+g[k][v])

    算法的疑问?

    1. 如果g[u][k]+g[k][v]改为dis[u][k]+dis[k][v]错误: 因为uv的最短路可能会重复,不成环,只能用边来枚举
    2. 至少有三个点,所以三层循环i!=j

    POJ 1734

    • path记录路径
    • pre[i][j]记录:最短路径中j点的上一个点是谁

    #include <cstring>
    #include <stdio.h>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn = 110;
    const int inf  = 9999999;
    int n,m,tot;
    int g[maxn][maxn],dis[maxn][maxn];
    int pre[maxn][maxn],path[maxn];
    
    int main() {
        cin >> n >> m;
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=n; ++j) {
                g[i][j] = dis[i][j] = inf;
                pre[i][j] = i;
            }
        for (int i=1; i<=m; ++i) {
            int u,v,w;
            cin >> u >> v >> w;
            g[u][v] = g[v][u]= dis[u][v] = dis[v][u] = min(g[u][v],w);
        }
        int ans = inf;
        for (int k=1; k<=n; ++k) {
            for (int i=1; i<k; ++i)
                for (int j=i+1;j<k; ++j) {
                    int temp = dis[i][j] + g[i][k] + g[k][j];
                    if (temp < ans) {
                        ans = temp;
                        tot = 0;
                        int p = j;
                        while (p != i) {
                            path[tot++] = p;
                            p = pre[i][p];
                        }
                        path[tot++] = i;
                        path[tot++] = 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];
                        pre[i][j] = pre[k][j];
                    }
        }
        if(ans==inf)
            cout << "No solution." << endl;
        else {
            for (int i=0; i<tot; ++i)
                cout << path[i] << " ";
            cout << endl;
        }
        return 0;
    }
    
    
    展开全文
  • FLOYD 求最小环

    2014-02-15 15:35:09
    首先 先介绍一下 FLOYD算法的基本思想   设d[i,j,k]是在只允许经过结点1…k的情况下i到j的最短路长度则它有两种情况(想一想,为什么):最短路经过点k,d[i,j,k]=d[i,k,k-1]+d[k,j,k-1]最短路不经过点k,d[i,j...


    首先 先介绍一下 FLOYD算法的基本思想

     

    设d[i,j,k]是
    在只允许经过结点1…k的情况下
    i到j的最短路长度
    则它有两种情况(想一想,为什么):
    最短路经过点k,d[i,j,k]=d[i,k,k-1]+d[k,j,k-1]
    最短路不经过点k,d[i,j,k]=d[i,j,k-1]
    综合起来: d[i,j,k]=min{d[i,k,k-1]+d[k,j,k-1],d[i,j,k-1]}
    边界条件: d[i,j,0]=w(i,j)(不存在的边权为∞

    floyd算法的流程:
    把k放外层循环,可以节省内存
    对于每个k,计算每两点的目前最短路
    代码(需记忆)
    for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if (d[i,k]<∞)and(d[k,j]<∞)
           and(d[i,k]+d[k,j]<d[i,j]) then
              d[i,j]:=d[i,k]+d[k,j]               (以上2段引自刘汝佳的课件)
    时间复杂度:O(n^3)
    FLOYD算法的复杂度虽然是O(n^3)但是它计算出任意一对点之间的最短路。
    FLOYD的代码具有一种简洁美,当时间不允许写其他算法时的时候,写一个FLOYD,骗一部分的分,也是一个不错的选择。
    另一方面,它不怕负权边,也可以判断负权回路。

    接下来通过几个例题让我们看看FLOYD 算法的神奇威力。
    第一. 求最小环
    有向图的最小环和无向图的最小环完全是两种不一样的问题。
    其一般解法都是枚举一条边uv删除,然后求一条uv间的最短路径(假设长S)然后用S+边uv的长,来更新答案。
    如果用SPFA来求最短路,那么复杂度是O(m*km) k的取值取决于 图本身。
    但是FLOYD算法可以在O(n^3)内很轻松地解决这个问题。
    首先对于有向图
     由于一条边UV只能从U到V,而不能逆行之,那么我们只需要更新出图中任意2个点之间的最短路径。
    记F[U,V]表示U到V的最短距离
    G[U,V] 是原图中U到V的边的长
    对于每对(U,V)我们只要将G[U,V]+F[V,U]来更新答案就行了。
    无向图的最小环相对麻烦一些。
    因为我们要避免一条无向边被2次走过(被当做2条边)的情况。
    FOR EXAMPLE
    u v之间有且只有一条边e   我们大可以从U 走到V 然后从V走回U  但是这并不是一个环
    算法:
    在floyd的同时,顺便算出最小环
       g[i][j]=(i,j之间的边长)
       dist:=g;
       for k:=1 to n do
        begin
          for i:=1 to k-1 do
            for j:=i+1 to k-1 do
                answer:=min(answer,dist[i][j]+g[i][k]+g[k][j]);
          for i:=1 to n do
             for j:=1 to n do
                 dist[i][j]:=min(dist[i][j],dist[i][k]+dist[k][j]);
        end;
       关于算法<2>的证明:
        一个环中的最大结点为k(编号最大),与他相连的两个点为i,j,这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
        根据floyd的原理,在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路径
        综上所述,该算法一定能找到图中最小环。

    第二.求经过K条边的最短路径
    例题:给出了一张有N个点M条边的加权有向无环图,接下来有Q个询问,每个询问包括2个节点X和Y,要求算出从X到Y的一条路径,使得密度最小(密度的定义为,路径上边的权值和除以边的数量)。
     有1 ≤ N ≤ 50,1 ≤ M ≤ 1000,1 ≤ W ≤ 100000,1 ≤ Q ≤ 100000
    这道题十分坑爹。
    题目里说好是无环图,但是数据里到处都是环。
    我刚开始想的方法是用SPFA拆点做
    把原图中每个点拆成N-1个点,分别表示经过I条边到达的这个点。因为最多经过N-1条边。
    数据中这种环就会像负权环一样导致SPFA永远做下去。

    但是暂且不管数据如何。对于这个题目,除了上面讲的SPFA 拆点的做法,FLOYD 也是可以很好解决的
    首先这个“密度”很特殊,IJ之间最小密度路径加上JK之间最小路径,不一定就是IK之间的最小密度路径。
    所以我们要先枚举经过了P条边 (1<=P<=N-1)

    定义状态f(i,j,k)表示从i到j恰好经过k条边的最短路,类似Floyd的算法得出DP方程:
            f(i,j,k)=Min{f(i,h,g)+f(h,j,k-g)}。
    这个方程是5维的,会超时,如何减小维数呢?
    考虑在何处重复决策。注意到f(i,j,k)的选择路径V1-V2-...-Vk,实际上我们只要找到这里的一个点决策即可,而不需每个点都判断过去。这样就很容易想到在最后一个点进行决策。
            f(i,j,k)=Min{f(i,h,k-1)+f(h,j,1)}。
    这样这个方法的时间复杂度就是0(N^4) 空间复杂度O(N^3)
    问题得到了很好的解决。


    展开全文
  • Floyd求最小环模板

    2018-12-07 15:04:15
    /******Floyd求最小环******/ //#include&lt;bits/stdc++.h&gt; #include&lt;cstdio&gt; #include&lt;cstring&gt; #include&lt;string&gt; #include&lt;iostream&gt; #...

    模板题:poj1734

    【模板】

    /******Floyd求最小环******/
    //#include<bits/stdc++.h>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int maxn=305;
    const int inf=1e8;
    
    int dis[maxn][maxn],g[maxn][maxn];
    int pre[maxn][maxn],path[maxn];
    
    int n,m,num,minc;
    
    void Floyd()
    {
    	minc=inf;
    	int tmp,p;
    	for(int k=1;k<=n;k++)
    	{
    		for(int i=1;i<k;i++)
    		for(int j=i+1;j<k;j++)
    		{
    			tmp=dis[i][j]+g[i][k]+g[k][j];
    			if(tmp<minc)
    			{
    				minc=tmp;
    				num=0;
    				p=j;
    				while(p!=i)
    				{
    					path[num++]=p;
    					p=pre[i][p];
    				}
    				path[num++]=i;
    				path[num++]=k;
               	}
           	}
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
              	tmp=dis[i][k]+dis[k][j];
              	if(dis[i][j]>tmp)
             	{
              		dis[i][j]=tmp;
              		pre[i][j]=pre[k][j];
               	}
            }
         }
    }
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
        	for(int i=1;i<=n;i++)
        	for(int j=1;j<=n;j++)
        	{
        		g[i][j]=inf;
        		dis[i][j]=inf;
        		pre[i][j]=i;
            }
            while(m--)
            {
            	int u,v,w;
            	scanf("%d%d%d",&u,&v,&w);
                w=min(g[u][v],w);          //处理重边
                g[u][v]=g[v][u]=dis[u][v]=dis[v][u]=w;
            }
            Floyd();
            if(minc==inf)printf("No solution.\n");
            else
            {
            	printf("%d",path[0]);
                for(int i=1;i<num;i++)
                    printf(" %d",path[i]);
                printf("\n");
            }
        }
        return 0;
    }

     

    展开全文
  • floyd求最小环 模板

    2014-05-04 20:38:14
    floyd求最小环 2011-08-14 9:42 1 定义: 通常来说最小环是针对有向图而言 从一个点出发,经过一条简单路径回到起点成为环.图的最小环就是所有环中长度最小的. 2.怎样求最小环呢? 1传

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 512
精华内容 204
关键字:

floyd求最小环