HDU 5406【费用流或 dp+树状数组】

Myth丶恋晨 2022-08-04 13:57 162阅读 0赞

拆点，容量为1表示每个点只能用一次，费用为-1表示经过了几个点  
建立超级源向源点连接容量为2的边，表示两个上升序列。

spfa用了栈就可以过了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define ls (idx<<1)
    #define rs (idx<<1|1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    const int N=2005,M=2000005;
    struct Graph
    {
        struct node
        {
            int v,next,w,flow;
            node(){};
            node(int a,int b,int c,int d){
                next=a;v=b;w=c;flow=d;
            }
        }E[2*M];
        int head[N],pre[N],dis[N];
        int beg,end,flow,cost;
        bool h[N];
        int path[N];
        int NE,NV;
        void resize(int n)
        {
            this->NV=n;
        }
        void init(int n)
        {
            NE=0;
            NV=n;
            memset(head,-1,sizeof(int)*(n+10));
        }
        void insert(int u,int v,int flow,int w)
        {
            E[NE]=node(head[u],v,w,flow);
            head[u]=NE++;
            E[NE]=node(head[v],u,-w,0);
            head[v]=NE++;
        }
        bool update(int u,int v,int w)
        {
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                return true;
            }
            return false;
        }
        int st[N];
        bool spfa()
        {
            CLR(pre,-1);
            CLR(h,0);
            for(int i=0;i<=NV;i++)
                dis[i]=INF;
            dis[beg]=0;
            int top=0;
            st[top++]=beg;
            while(top)
            {
                top--;
                int u=st[top];
                h[u]=0;
                for(int i=head[u];i!=-1;i=E[i].next)
                {
                    int v=E[i].v;
                    if(E[i].flow>0&&update(u,v,E[i].w))
                    {
                        pre[v]=u;
                        path[v]=i;
                        if(!h[v])
                        {
                            h[v]=1;
                            st[top++]=v;
                        }
                    }
                }
            }
            if(pre[end]==-1)
                return false;
            return true;
        }
        int mincost_maxflow(int s,int t)
        {
            this->beg=s;this->end=t;
            flow=0,cost=0;
            while(spfa())
            {
                int Min=INT_MAX;
                for(int i=end;i!=beg;i=pre[i])
                    if(Min>E[path[i]].flow)
                        Min=E[path[i]].flow;
                for(int i=end;i!=beg;i=pre[i])
                {
                    E[path[i]].flow-=Min;
                    E[path[i]^1].flow+=Min;
                }
                flow+=Min;
                cost+=dis[end];
            }
            return cost;
        }
    }g;
    
    struct apple
    {
        int h,v;
    }a[N];
    
    bool cmp(apple a,apple b)
    {
        if(a.h==b.h) return a.v<b.v;
        return a.h>b.h;
    }
    int n,i,j,s,t,ss;
    const int MAXN=3000;
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%d",&n);
            for(i=1;i<=n;i++)
                scanf("%d%d",&a[i].h,&a[i].v);
            sort(a+1,a+1+n,cmp);
            s=0;t=2*n+2;ss=2*n+1;
            g.init(2*n+3);
    
            g.insert(s,ss,2,0);
            for(i=1;i<=n;i++)
            {
                g.insert(ss,i,1,0);
                g.insert(i,n+i,1,-1);
                g.insert(n+i,t,1,0);
            }
            for(i=1;i<=n;i++)
                for(j=i+1;j<=n;j++)
                    if(a[i].v<=a[j].v)
                        g.insert(n+i,j,1,0);
    
            int ans=g.mincost_maxflow(s,t);
            printf("%d\n",-ans);
        }
        return 0;
    }

建图图上进行dp，dp\[i\]\[j\]表示表示两个人分别在 第i个点和第j个点时候能吃的最多苹果树，可以限制下 i<=j减少有效状态，还有就是一些无用的边不需要构造出来 ，比如说

a->b b->c 那么 就不需要连a->c的边，这里边表示的是 吃完a可以吃b。然后就图上跑一遍dp就行了。注意事项见代码。

#include <queue>
    #include <limits>
    #include <vector>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    #define INF 1000000050
    #define MAXN 1111
    vector<int> e[MAXN];
    int in[MAXN];
    int q[MAXN];
    int dis[MAXN];
    int d[MAXN][MAXN];
    int id[MAXN];
    struct g {
        int h, d;
    } s[MAXN];
    bool cmp(g a, g b) {
        if (a.h == b.h)
            return a.d < b.d;
        return a.h > b.h;
    }
    
    int main() {
        int tt;
        scanf("%d", &tt);
        while (tt--) {
            int n;
            scanf("%d", &n);
            for (int i = 1; i <= n; ++i)
                scanf("%d%d", &s[i].h, &s[i].d);
            sort(s + 1, s + 1 + n, cmp);
            for (int i = 0; i <= n + 1; ++i) {
                dis[i] = in[i] = 0;
                e[i].clear();
            }
    
            //进行拓扑排序，根据拓扑序进行dp
            for (int i = 1; i <= n; ++i) {
                e[0].push_back(i);
                in[i]++;
                for (int j = i + 1; j <= n; ++j) {
                    if (s[i].d <= s[j].d) {
                        e[i].push_back(j);
                        in[j]++;
                    }
                }
                e[i].push_back(n + 1);
                in[n + 1]++;
            }
            int tail = 0;
            q[tail++] = 0;
            dis[0] = 0;
            id[0] = 0;
            for (int i = 0; i < tail; ++i) {
                int u = q[i];
                id[u] = i;
                for (int j = 0; j < e[u].size(); ++j) {
                    int v = e[u][j];
                    if (dis[v] < dis[u] + 1)
                        dis[v] = dis[u] + 1;
                    in[v]--;
                    if (in[v] == 0)
                        q[tail++] = v;
                }
            }
    
            for (int i = 0; i <= n + 1; ++i)
                for (int j = 0; j <= n + 1; ++j) {
                    d[i][j] = -INF;
                }
            for (int i = 0; i <= n + 1; ++i)
                e[i].clear();
            s[n + 1].d = INF;
            for (int i = n; i >= 0; --i) {
       //加边的时候注意不要加一些无用的边
                int mm = INF + 50;
                for (int j = i + 1; j <= n + 1; ++j) {
                    if (mm <= s[j].d)
                        continue;
                    if (s[i].d <= s[j].d) {
                        e[i].push_back(j);
                        mm = min(s[j].d, mm);
                    }
                }
            }
    
            d[0][0] = 0;
            for (int i = 0; i <= n + 1; ++i) {
                int u = q[i];
                for (int j = i; j <= n + 1; ++j) {
                    int v = q[j];
                    if (d[i][j] < 0)
                        continue;
                    for (int k = 0; k < e[u].size(); ++k) {
       //每次只从编号小的转移
                        int x = id[e[u][k]];
                        if (x == j) {
                            d[x][j] = max(d[x][j], d[i][j]);
                        }
                        if (x < j) {
                            d[x][j] = max(d[x][j], d[i][j] + 1);
                        }
                        if (x > j) {
                            d[j][x] = max(d[j][x], d[i][j] + 1);
                        }
                    }
    
                }
            }
    
            printf("%d\n", d[n + 1][n + 1] - 1);
        }
    }