uva 10594（最小费用最大流）

题意：在一个无向网络中，告诉你边的容量与费用。现在需要传送d个数据问你你否能传送成功，若成功则最小费用是多少。

思路：显然是最小费用最大流问题，这道题的见图比较简单。只需要添加一个原点费用为D指向1就行了。接下来的事情就是套模版了。

代码如下：

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

View Code

奔跑吧！少年！趁着你还年轻