hdu 5406 CRB and Apple, 2015多校聯合訓練賽，費用流

CRB and Apple

Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 336    Accepted Submission(s): 101

Problem Description In Codeland there are many apple trees.

One day CRB and his girlfriend decided to eat all apples of one tree.

Each apple on the tree has height and deliciousness.

They decided to gather all apples from top to bottom, so an apple can be gathered only when it has equal or less height than one just gathered before.

When an apple is gathered, they do one of the following actions.

1.  CRB eats the apple.

2.  His girlfriend eats the apple.

3.  Throw the apple away.

CRB(or his girlfriend) can eat the apple only when it has equal or greater deliciousness than one he(she) just ate before.

CRB wants to know the maximum total number of apples they can eat.

Can you help him?

Input There are multiple test cases. The first line of input contains an integer  T , indicating the number of test cases. For each test case:

The first line contains a single integer  N  denoting the number of apples in a tree.

Then  N  lines follow,  i -th of them contains two integers  Hi  and  Di  indicating the height and deliciousness of  i -th apple.

1 ≤  T  ≤ 48

1 ≤  N  ≤ 1000

1 ≤  Hi ,  Di  ≤  109

Output For each test case, output the maximum total number of apples they can eat.  

Sample Input

1
5
1 1
2 3
3 2
4 3
5 1
        

Sample Output

4
        

Author KUT（DPRK）  

Source 2015 Multi-University Training Contest 10

Accepted

5406

296MS

2204K

3031 B

G++

參考内容來自：

http://blog.csdn.net/mxymxy1994mxy/article/details/47818397

這篇部落格中提供的思路大約邊都為原來的50分之一了，優化好厲害。學習了。

http://blog.csdn.net/l_ecry/article/details/47830927

用棧優化時間快了4倍左右！！也是6666

對于spfa的優化，對于隊列而言确實能夠有不少的優化。如下：

http://www.cnblogs.com/cj695/archive/2012/07/27/2611215.html

對于這題建圖：

建立s,t,  把i點拆為i,i+n,建立虛拟節點限制流量s1， 

s->s1  容量2，

s->i, i->t,容量1，

除了i->i+n的費用為-1，其他邊費用都為0

對h從小到大排序，d從大到小排序，

邊優化：對于a+n->x, a+n->y 如果x >= y 那麼a+n不需要對y連邊，因為通過x也可以到達y。

這就是部落格1中單調塊的思想。但是，會出現單調塊的入口被占據的情況，

那麼建邊的同時建立一條a->x的路徑，表示路過a點，直接通路a能到達的點。

費用流好久沒用了，好神奇。！！！！

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define maxn 2017
#define maxm 200000
#define inf 10000000
using namespace std;
int head[maxn],tail;
int queue[maxn],pre[maxn],flag[maxn];
int dist[maxn],maxFlow[maxn];
struct Edge{
    int v,u,next,cost,w;
    Edge(){}//費用，權值
    Edge(int u,int v,int next,int cost,int w):u(u),v(v),next(next),cost(cost),w(w){}
} edge[maxm];
void add_edge(int u,int v,int cost,int w){
    edge[tail] = Edge(u,v,head[u],cost,w);
    head[u] = tail++;
    edge[tail] = Edge(v,u,head[v],-cost,0);
    head[v] = tail++;
}
void init(){
    memset(head,-1,sizeof(head));
    tail=0;
}
int SPFA(int start,int end){
    int i,u,v,front,rear;
    front = rear = 0;
    memset(flag,0,sizeof(flag));
    memset(dist,0x1f,sizeof(dist));
    memset(pre,-1,sizeof(pre));
    dist[start] = 0, dist[end] = inf ,flag[start]=1;
    maxFlow[start] = inf, queue[rear++] = start;
    while(front != rear){//增廣
        u = queue[--rear];
        //if(front >= maxn) front = 0;
        flag[u] = 0;
        for(i = head[u]; i!=-1;i=edge[i].next){
            v=edge[i].v;
            if(edge[i].w&&dist[v]>dist[u]+edge[i].cost){
                dist[v]=dist[u]+edge[i].cost;
                maxFlow[v]=min(edge[i].w,maxFlow[u]);
                pre[v]=i;//記錄邊下标
                if(!flag[v]){
                    queue[rear++]=v;
                   // if(rear>=maxn)rear=0;
                    flag[v] =1;
                }
            }
        }
    }
    return dist[end] != inf;
}
//開始點，結束點
int MFMC(int start,int end){
    int min_cost = 0,v;
    while(SPFA(start,end)){
        v = end;
        while(pre[v]>=0){
            edge[pre[v]].w-=maxFlow[end];
            edge[pre[v]^1].w+=maxFlow[end];
            v=edge[pre[v]].u;
        }//跟新費用
        min_cost+=dist[end]*maxFlow[end];
    }
    return min_cost;
}
struct Node{
    int h,d;
};
Node p[1001];
int comp(Node a,Node b){
    if(a.h == b.h) return a.d > b.d;
    return a.h < b.h;
}
int main(){
    int t,n,h,d;
    //freopen("1001.in","r",stdin);
    //freopen("1001x.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 0 ;i < n; i++){
            scanf("%d%d",&p[i].h,&p[i].d);
        }
        sort(p,p+n,comp);
        init();
        int s1 = n*2, S = s1+1, T = S+1;
        for(int i = 0;i < n; i++){
            add_edge(s1,i,0,2);
            add_edge(i+n,T,0,1);
            add_edge(i,i+n,-1,1);
        }
        add_edge(S,s1,0,2);
        for(int i = 0;i < n; i++){
            int x = -10;
            for(int j = i+1;j < n; j++){
                if(p[j].d <= p[i].d && p[j].d > x){
                    add_edge(i+n,j,0,1);
                    add_edge(i,j,0,1);
                    x = p[j].d;
                }
            }
        }
        int ans = 0;
        ans = MFMC(S,T);
        printf("%d\n",-ans);
    }
    return 0;
}