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

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

阅读量：4114 次

发布时间：2019-05-25

本文共 3982 字，大约阅读时间需要 13 分钟。

题意：给你n个节点，中间连接有m条边，每条边有一定的权值，求两种1号节点走到n号节点没有公共边的走法中

总的权值最小的走法，输出这个最小值；

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                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
               
                 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<
                <<" "<
                 
                  <
                  
                   0) { memset(dist,inf,sizeof(dist)); memset(inq,0,sizeof(inq)); dist[s]=0; queue
                   
                     q; q.push(s); inq[s]=1; while(!q.empty()) { int u=q.front(); q.pop();inq[u]=0; for(int j=0;j
                    
                     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 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                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
               
                 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<
                <<" "<
                 
                  <
                  
                   0) { memset(dist,inf,sizeof(dist)); dist[s]=0; bool update=true; while(update) { update=false; for(int u=1;u
                   
                    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"<
                    
                     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 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                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
               
                 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<
                <<" "<
                 
                  <
                  
                   0) { memset(dist,inf,sizeof(dist)); dist[s]=0; bool update=true; while(update) { update=false; for(int u=1;u
                   
                    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"<
                    
                     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; }