首页 > 代码库 > HDU 2485 Destroying the bus stations(费用流)

HDU 2485 Destroying the bus stations(费用流)

http://acm.hdu.edu.cn/showproblem.php?pid=2485

题意:

现在要从起点1到终点n,途中有多个车站,每经过一个车站为1时间,现在要在k时间内到达终点,问至少要破坏多少个车站。

 

思路:

把每个点拆分为两个点,容量为1,费用为0。之后相邻的车站连边,容量为INF,费用为1,表示经过一个车站需要1时间。

这样一来,跑一遍费用流计算出在费用不大于k的情况下的最大流,也就是最小割,即至少要破坏的车站数。

在网络中寻求关于f的最小费用增广路,就等价于在伴随网络中寻求从Vs到Vt的最短路。

  1 #include<iostream>  2 #include<algorithm>  3 #include<cstring>  4 #include<cstdio>  5 #include<sstream>  6 #include<vector>  7 #include<stack>  8 #include<queue>  9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef long long ull; 15 typedef pair<int,int> pll; 16 const int INF = 0x3f3f3f3f; 17 const int maxn = 1000 + 5; 18  19 int n, m, k; 20  21 struct Edge 22 { 23     int from, to, cap, flow, cost; 24     Edge(int u, int v, int c, int f, int w) :from(u), to(v), cap(c), flow(f), cost(w) {} 25 }; 26  27 struct MCMF 28 { 29     int n, m; 30     vector<Edge> edges; 31     vector<int> G[maxn]; 32     int inq[maxn]; 33     int d[maxn]; 34     int p[maxn]; 35     int a[maxn]; 36  37     void init(int n) 38     { 39         this->n = n; 40         for (int i = 0; i<n; i++) G[i].clear(); 41         edges.clear(); 42     } 43  44     void AddEdge(int from, int to, int cap, int cost) 45     { 46         edges.push_back(Edge(from, to, cap, 0, cost)); 47         edges.push_back(Edge(to, from, 0, 0, -cost)); 48         m = edges.size(); 49         G[from].push_back(m - 2); 50         G[to].push_back(m - 1); 51     } 52  53     bool BellmanFord(int s, int t, int &flow, int & cost) 54     { 55         for (int i = 0; i<n; i++) d[i] = INF; 56         memset(inq, 0, sizeof(inq)); 57         d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; 58  59         queue<int> Q; 60         Q.push(s); 61         while (!Q.empty()){ 62             int u = Q.front(); Q.pop(); 63             inq[u] = 0; 64             for (int i = 0; i<G[u].size(); i++){ 65                 Edge& e = edges[G[u][i]]; 66                 if (e.cap>e.flow && d[e.to]>d[u] + e.cost){ 67                     d[e.to] = d[u] + e.cost; 68                     p[e.to] = G[u][i]; 69                     a[e.to] = min(a[u], e.cap - e.flow); 70                     if (!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; } 71                 } 72             } 73         } 74  75         if(d[t]>k)  return false;  //增广到大于k的时候就可以结束了 76         if (d[t] == INF) return false; 77         flow += a[t]; 78         cost += d[t] * a[t]; 79         for (int u = t; u != s; u = edges[p[u]].from) 80         { 81             edges[p[u]].flow += a[t]; 82             edges[p[u] ^ 1].flow -= a[t]; 83         } 84         return true; 85     } 86  87     int MincostMaxdflow(int s, int t){ 88         int flow = 0, cost = 0; 89         while (BellmanFord(s, t, flow, cost)); 90         return flow; 91     } 92 }t; 93  94 int main() 95 { 96     //freopen("in.txt","r",stdin); 97     while(~scanf("%d%d%d",&n,&m,&k) &&n && m &&k) 98     { 99         int src=http://www.mamicode.com/1,dst=n;100         t.init(2*n);101 102         for(int i=2;i<n;i++)  t.AddEdge(i,i+n,1,0);103 104         for(int i=0;i<m;i++)105         {106             int u,v;107             scanf("%d%d",&u,&v);108             if(u==src)  t.AddEdge(u,v,INF,1);109             else if(u==dst)  continue;110             else t.AddEdge(u+n,v,INF,1);111         }112         printf("%d\n",t.MincostMaxdflow(src,dst));113     }114     return 0;115 }

 

HDU 2485 Destroying the bus stations(费用流)