HDU 3618 Good Plan(费用流)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3618

Problem Description

FJ has two same houses for rant. Now he has n (1 ≤ n ≤ 1000) piece of order, the orders are given in the form:

s t v

means that someone want to rant a house from the day s to t paying v yuan totally (including the day s and t, 0 ≤ s ≤ t ≤ 400, 0 ≤ v ≤ 100,0000).

A house can be only rant to one person, and FJ should either accept an order totally or reject it.

Input

The first line of input file is a single integer T - The number of test cases. For each test case, the first line is a single integer n then there n lines, each line gives an order.

Output

For each data set, print a single line containing an integer, the maximum total income for the data set.

此题用来测试了一下SPFA费用流的模版。建图：每个s到t连一条容量为1，代价为v的边，每一天与下一天连一条容量为2，代价为0的边，S与第0天连边，T与最后一天连边，容量为2，代价为0，最大费用最大流即为答案。

  1 #include<cstdio>   
  2 #include<cstring>   
  3 #include<algorithm>   
  4 #include<queue>   
  5 #define INF 0x7fffffff   
  6 using namespace std;   
  7 const int MAXN=500,MAXM=4000;   
  8 struct mcflow{   
  9        int N,M,S,T;   
 10        int head[MAXN],next[MAXM],to[MAXM],cost[MAXM],f[MAXM],ecnt;   
 11        int pre[MAXN],d[MAXN];   
 12        bool vis[MAXN];   
 13        #define CL(x) memset(x, 0, sizeof(x));   
 14        void init(){   
 15             CL(head); CL(next); CL(to); CL(cost);   
 16             ecnt = 2;   
 17             T = S = N = M = 0;   
 18        }   
 19        void make_edge(int a, int b, int cc, int d){   
 20             next[ecnt] = head[a];   
 21             head[a] = ecnt;   
 22             to[ecnt] = b;   
 23             f[ecnt] = cc;   
 24             cost[ecnt++] = d;   
 25        }   
 26        void insert(int a, int b, int cc, int d){   
 27             make_edge(a, b, cc, d);   
 28             make_edge(b, a, 0, -d);   
 29        }   
 30        bool spfa(){   
 31             CL(vis);   
 32             for(int i = 0; i <= T; ++i)   
 33                 d[i] = INF;   
 34             queue<int> Q;   
 35             Q.push(S);   
 36             vis[S]=1;   
 37             d[S] = 0;   
 38             while(!Q.empty()){   
 39                 int u = Q.front(); Q.pop();   
 40                 vis[u] = 0;   
 41                 for(int p = head[u]; p; p = next[p]){   
 42                     if(f[p] > 0 && d[to[p]] > d[u] + cost[p]){   
 43                         d[to[p]] = d[u] + cost[p];   
 44                         pre[to[p]] = p;   
 45                         if(!vis[to[p]]){   
 46                             vis[to[p]]=1;   
 47                             Q.push(to[p]);   
 48                         }   
 49                     }   
 50                 }   
 51             }   
 52             return d[T] < INF;   
 53        }   
 54        void min_cost_flow(int &Flow, int &fee){   
 55             Flow = fee = 0;   
 56             while(spfa()){   
 57                 fee += d[T];   
 58                 int u = T, tmp = INF;   
 59                 while(u != S){   
 60                     tmp=min(f[pre[u]], tmp);   
 61                     u=to[pre[u]^1];   
 62                 }   
 63                 u=T;   
 64                 while(u != S){   
 65                     f[pre[u]] -= tmp;   
 66                     f[pre[u]^1] += tmp;   
 67                     u = to[pre[u]^1];   
 68                 }   
 69                 Flow += tmp;   
 70             }   
 71        }   
 72        int mincost(){   
 73            int ret, tmp;   
 74            min_cost_flow(tmp, ret);   
 75            return ret;   
 76        }   
 77        int maxflow(){   
 78            int ret, tmp;   
 79            min_cost_flow(ret, tmp);   
 80            return ret;   
 81        }   
 82 }G;   
 83        
 84 int main()   
 85 {   
 86     int T,m,s,t,v,i;   
 87     scanf("%d",&T);   
 88     while(T--){   
 89         G.init();   
 90         scanf("%d",&m);   
 91         while(m--){   
 92             scanf("%d%d%d",&s,&t,&v);   
 93             G.insert(s,t+1,1,-v);   
 94         }   
 95         G.S = 401; G.T = 402;   
 96         G.insert(G.S,0,2,0); G.insert(400,G.T,2,0);   
 97         for(i = 0; i < 400; ++i) G.insert(i,i+1,2,0);   
 98         printf("%d\n",-G.mincost());   
 99     }   
100     return 0;   
101 }

View Code

更新（2015年11月7日）：

上面的模板只在每次流量增量是1的时候才是对的。增量不是1就会出错。