uva 1349（费用流）-白红宇

uva 1349（费用流）

阅读量：6370 次

发布时间：2019-06-23

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

题意：有若干城市组成一张有向图权值是花费，要你设计一个公交线路图是每个城市都经过一遍，然后要求总的花费最少。线路数量不限制只要覆盖到所有城市有且仅有一次就可以，输出最小费用。

思路：liurujia分在二分图里面的题目，第一眼看上去就像是费用流的题，想了一个多小时二分图做法没成功，还是用费用流a了。仔细观察我们可以发现设计出来的线路图必满足最大匹配数等于城市数（二分图两边都为城市）然后在这基础上费用最小。接下来就是建图套模版了。

补充：其实直接KM就能解决此题。。果断对算法理解还不到位。

代码如下：

1 /**************************************************  2  * Author     : xiaohao Z  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/  4  * Last modified : 2014-02-26 00:33  5  * Filename     : uva_1349.cpp  6  * Description     :   7  * ************************************************/  8   9 #include 
      
        10 #include 
       
         11 #include 
        
          12 #include 
         
           13 #include 
          
            14 #include 
           
             15 #include 
            
              16 #include 
             
               17 #include 
              
                18 #include 
               
                 19 #include 
                 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair
                 
                   pii; 26 typedef pair
                  
                    puu; 27 typedef pair
                   
                     pid; 28 typedef pair
                    
                      pli; 29 typedef pair
                     
                       pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int MAXN = 10000; 34 const int MAXM = 100000; 35 struct Edge{ int to,next,cap,flow,cost;}edge[MAXM]; 36 int head[MAXN],tol; 37 int pre[MAXN],dis[MAXN]; 38 bool vis[MAXN]; 39 int N;//节点总个数，节点编号从0~N-1 40 41 void init(int n) 42 { 43 N = n; 44 tol = 0; 45 memset(head,-1,sizeof(head)); 46 } 47 48 void addedge(int u,int v,int cap,int cost) 49 { 50 edge[tol].to = v; 51 edge[tol].cap = cap; 52 edge[tol].cost = cost; 53 edge[tol].flow = 0; 54 edge[tol].next = head[u]; 55 head[u] = tol++; 56 edge[tol].to = u; 57 edge[tol].cap = 0; 58 edge[tol].cost = -cost; 59 edge[tol].flow = 0; 60 edge[tol].next = head[v]; 61 head[v] = tol++; 62 } 63 bool spfa(int s,int t) 64 { 65 queue
                      
                       q; 66 for(int i = 0; i < N; i++) 67 { 68 dis[i] = INF; 69 vis[i] = false; 70 pre[i] = -1; 71 } 72 dis[s] = 0; 73 vis[s] = true; 74 q.push(s); 75 while(!q.empty()) 76 { 77 int u = q.front(); 78 q.pop(); 79 vis[u] = false; 80 for(int i = head[u]; i != -1; i = edge[i].next) 81 { 82 int v = edge[i].to; 83 if(edge[i].cap > edge[i].flow && 84 dis[v] > dis[u] + edge[i].cost ) 85 { 86 dis[v] = dis[u] + edge[i].cost; 87 pre[v] = i; 88 if(!vis[v]) 89 { 90 vis[v] = true; 91 q.push(v); 92 } 93 } 94 } 95 } 96 if(pre[t] == -1)return false; 97 else return true; 98 } 99 //返回的是最大流，cost存的是最小费用100 int minCostMaxflow(int s,int t,int &cost)101 {102 int flow = 0;103 cost = 0;104 while(spfa(s,t))105 {106 int Min = INF;107 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])108 {109 if(Min > edge[i].cap - edge[i].flow)110 Min = edge[i].cap - edge[i].flow;111 }112 for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])113 {114 edge[i].flow += Min;115 edge[i^1].flow -= Min;116 cost += edge[i].cost * Min;117 }118 flow += Min;119 }120 return flow;121 }122 123 int main()124 {125 // freopen("in.txt", "r", stdin);126 127 int n, a, b;128 while(scanf("%d", &n)!=EOF && n){129 init(2*n+2); 130 for(int i=0; i

View Code

转载于:https://www.cnblogs.com/shu-xiaohao/p/3568186.html

你可能感兴趣的文章