poj 2135 Farm Tour 最小费用流 spfa优化 16_05_14

2024-01-13 02:48
文章标签 16 优化 最小 05 14 poj spfa 费用 tour 2135 farm

本文主要是介绍poj 2135 Farm Tour 最小费用流 spfa优化 16_05_14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=2135
题意：给你n个节点，中间连接有m条边，每条边有一定的权值，求两种1号节点走到n号节点没有公共边的走法中
总的权值最小的走法，输出这个最小值； 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a) memset(a,0,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
const int N = 500;
const int M=20000;
struct edge{
   int to,cap,cost,rev;
};
vector<edge> G[1005];
int dist[1005],inq[1005],prev[1005],prel[1005];
int n,m,x,y,c;
void add_edge(int u,int v,int cost)
{
    G[u].push_back(edge{v,1,cost,G[v].size()});
    G[v].push_back(edge{u,0,-cost,G[u].size()-1});
    //cout<<u<<" "<<G[u].size()<<endl;
}
int mincost(int s,int t,int f)
{
    int ans=0;
    while(f>0)
    {
      memset(dist,inf,sizeof(dist));
      memset(inq,0,sizeof(inq));
      dist[s]=0;
      queue<int> q;
      q.push(s);
      inq[s]=1;
      while(!q.empty())
      {
          int u=q.front();
          q.pop();inq[u]=0;
          for(int j=0;j<G[u].size();j++)
            {
                edge &e=G[u][j];
                if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
                   {
                       dist[e.to]=dist[u]+e.cost;
                       prev[e.to]=u;
                       prel[e.to]=j;
                       if(!inq[e.to])
                       {
                           q.push(e.to);
                           inq[e.to]=1;
                       }
                   }
            }
       }
       for(int i=t;i>s;)
       {
           int f=prev[i];
           int j=prel[i];
           G[f][j].cap-=1;
           G[i][G[f][j].rev].cap+=1;
           ans+=G[f][j].cost;
           i=prev[i];
       }
       f-=1;
    }
    return ans;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d %d",&x,&y,&c);
            add_edge(x,y,c);
            add_edge(y,x,c);
        }
        printf("%d\n",mincost(1,n,2));
    }
    return 0;
}

上面是SPFA，下面是朴素的bellman 

   
  • #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    using namespace std;
    #define MM(a) memset(a,0,sizeof(a))
    typedef long long ll;
    typedef unsigned long long ULL;
    const int mod = 1000000007;
    const double eps = 1e-10;
    const int inf = 0x3f3f3f3f;
    const int big=50000;
    int max(int a,int b) {return a>b?a:b;};
    int min(int a,int b) {return a<b?a:b;};
    const int N = 500;
    const int M=20000;
    struct edge{
       int to,cap,cost,rev;
    };
    vector<edge> G[1005];
    int dist[1005],inq[1005],prev[1005],prel[1005];
    int n,m,x,y,c;
    void add_edge(int u,int v,int cost)
    {
        G[u].push_back(edge{v,1,cost,G[v].size()});
        G[v].push_back(edge{u,0,-cost,G[u].size()-1});
        //cout<<u<<" "<<G[u].size()<<endl;
    }
    int mincost(int s,int t,int f)
    {
        int ans=0;
        while(f>0)
        {
          memset(dist,inf,sizeof(dist));
          dist[s]=0;
          bool update=true;
          while(update)
          {
            update=false;
            for(int u=1;u<n;u++)
              for(int j=0;j<G[u].size();j++)
                {
                    edge &e=G[u][j];
                    if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
                       {
                           dist[e.to]=dist[u]+e.cost;
                           prev[e.to]=u;
                           prel[e.to]=j;
                           update=true;
                           //cout<<"4"<<endl;
                       }
                }
           }
           for(int i=t;i>s;)
           {
               int f=prev[i];
               int j=prel[i];
               G[f][j].cap-=1;
               G[i][G[f][j].rev].cap+=1;
               ans+=G[f][j].cost;
               i=prev[i];
           }
           f-=1;
        }
        return ans;
    }
    int main()
    {
        while(~scanf("%d %d",&n,&m))
        {
            for(int i=1;i<=m;i++)
            {
                scanf("%d %d %d",&x,&y,&c);
                add_edge(x,y,c);
                add_edge(y,x,c);
            }
            printf("%d\n",mincost(1,n,2));
        }
        return 0;
    }


分析：两条路不能有任意一条公共边，就决定了这道题目只能用流量为2的最小费用流，而不是最短路

下面是wa的代码：注意边的连接：无向路

   
  •      
    • #include <iostream>
      #include <cstdio>
      #include <cstring>
      #include <cstdlib>
      #include <cmath>
      #include <vector>
      #include <queue>
      #include <map>
      #include <algorithm>
      #include <set>
      using namespace std;
      #define MM(a) memset(a,0,sizeof(a))
      typedef long long ll;
      typedef unsigned long long ULL;
      const int mod = 1000000007;
      const double eps = 1e-10;
      const int inf = 0x3f3f3f3f;
      const int big=50000;
      int max(int a,int b) {return a>b?a:b;};
      int min(int a,int b) {return a<b?a:b;};
      const int N = 500;
      const int M=20000;
      struct edge{
         int to,cap,cost,rev;
      };
      vector<edge> G[1005];
      int dist[1005],inq[1005],prev[1005],prel[1005];
      int n,m,x,y,c;
      void add_edge(int u,int v,int cost)
      {
          G[u].push_back(edge{v,1,cost,G[v].size()});
          G[v].push_back(edge{u,0,-cost,G[u].size()-1});
          //cout<<u<<" "<<G[u].size()<<endl;
      }
      int mincost(int s,int t,int f)
      {
          int ans=0;
          while(f>0)
          {
            memset(dist,inf,sizeof(dist));
            dist[s]=0;
            bool update=true;
            while(update)
            {
              update=false;
              for(int u=1;u<n;u++)
                for(int j=0;j<G[u].size();j++)
                  {
                      edge &e=G[u][j];
                      if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
                         {
                             dist[e.to]=dist[u]+e.cost;
                             prev[e.to]=u;
                             prel[e.to]=j;
                             update=true;
                             //cout<<"4"<<endl;
                         }
                  }
             }
             for(int i=t;i>s;)
             {
                 int f=prev[i];
                 int j=prel[i];
                 G[f][j].cap-=1;
                 G[i][G[f][j].rev].cap+=1;
                 ans+=G[f][j].cost;
                 i=prev[i];
             }
             f-=1;
          }
          return ans;
      }
      int main()
      {
          while(~scanf("%d %d",&n,&m))
          {
              for(int i=1;i<=m;i++)
              {
                  scanf("%d %d %d",&x,&y,&c);
                  add_edge(x,y,c);
                  add_edge(y,x,c);
              }
              printf("%d\n",mincost(1,n,2));
          }
          return 0;
      }



这篇关于poj 2135 Farm Tour 最小费用流 spfa优化 16_05_14的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/599997。

相关文章

Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
HDFS—存储优化（纠删码）

HDFS—存储优化（纠删码）

纠删码原理 HDFS 默认情况下，一个文件有3个副本，这样提高了数据的可靠性，但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码，采用计算的方式，可以节省约50％左右的存储空间。 此种方式节约了空间，但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件，都会执行此策略。 默认只开启对 RS-6-3-1024k
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hdu 2602 and poj 3624(01背包)

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...
poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259： 题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
poj 1287 Networking（prim or kruscal最小生成树）

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。 注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];
阅读更多...
poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）

poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）

题目很麻烦，因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚，不适合新手。自己写一个。 题意：给你点的坐标，然后两点间可以有两种方式来通信：第一种是卫星通信，第二种是无线电通信。 卫星通信：任何两个有卫星频道的点间都可以直接建立连接，与点间的距离无关； 无线电通信：两个点之间的距离不能超过D，无线电收发器的功率越大，D越大，越昂贵。 计算无线电收发器D
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2