jzoj 1154_购物_最大流/树形dp

发布于 2020-08-20  935 次阅读

题目描述

GDOI商场推出优惠活动，以超低价出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究，发现商场出售的超低价商品中，不存在以下情况： 　　n(n>=3)种商品C1,C2,…..,Cn,其中Ci,Ci+1是不能同时购买的(i=1,2…,n-1)并且C1, Cn也不能同时购买。 　　编程计算可以节省的最大金额数。

思路

将每一个点同源点和汇点分别连边，然后将有冲突的点连边，那么最大流的一半就是最小的损失的金额
#include 
#include 
#include 
#include 
#define maxn 400000
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*p;
}
int add(int x,int y,int w)
{
    e[++maxE]=(edge){y,w,ls[x]};
    ls[x]=maxE;
    e[++maxE]=(edge){x,0,ls[y]};
    ls[y]=maxE;
}
int bfs(int x)
{
    queue  t;
    t.push(x);
    fill(state,0);
    state[x]=1;
    while (!t.empty())
    {
        int tt=t.front();t.pop();
        for (int i=ls[tt];i;i=e[i].next)
        {
            if (e[i].w>0&&!state[e[i].y])
            {
                state[e[i].y]=state[tt]+1;
                t.push(e[i].y);
                if (e[i].y==E)
                    return true;
            }
        }
    }
    return false;
}
int cur[maxn];
int find(int x,int mn)
{
    if (x==E||!mn) return mn;
    int ret=0;
    for (int &i=cur[x];i;i=e[i].next)
        if (state[x]+1==state[e[i].y]&&e[i].w>0)
        {
            int d=find(e[i].y,min(mn-ret,e[i].w));
            e[i].w-=d;
            e[i^1].w+=d;
            ret+=d;
            if (ret==mn) break;
        }
    return ret;
}
int main()
{
    n=read();m=read();
    S = 0; E = n * 2 +1;
    int tot = 0;
    for (int i=1;i<=n;i++)
    {
        int x=read();
        tot += x;
        add(S,i,x);
        add(i+n,E,x);
    }
    for (int i=1;i<=m;i++)
    {
        int x = read(), y =read();
        add(x, y + n, INF);
        add(y, x + n, INF);
    }
    int ans=0;
    while (bfs(S))
    {
        for (int i=0;i<=E+maxE;i++) 
            cur[i]=ls[i];
        ans+=find(S,INF);
    }
    printf("%d\n",tot - ans / 2);
}
f[i][0]表示以i为根的树不选i这个点可以达到的最大价值
f[i][0]表示以i为根的树选i这个点可以达到的最大价值 转移显然 f[now][0]=Σmax(f[son][1],f[son][0])
f[now][1]=w[now]+Σf[son][0]
#include 
#define maxn 1001
struct edge
{
    int to, next;
}e[maxn];
edge e2[maxn];
int ls[maxn], ls1[maxn], a[maxn], f[maxn][maxn];
bool fl[maxn];
int dfs(int now)
{
    fl[now] = 1;
    for (int i = ls[now]; i; i = e[i].next)
        if (fl[e[i].to] == 0)
        {
            dfs(e[i].to);
            f[now][0] += f[e[i].to][1] > f[e[i].to][0] ? f[e[i].to][1] : f[e[i].to][0];
            f[now][1] += f[e[i].to][0];
        }
    f[now][1] += a[now];
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int l = 0;
    for (int i = 1; i <= m; i++)
    {   
        int x, y;
        scanf("%d%d", &x, &y);
        e[++l] = (edge) {y, ls[x]};
        ls[x] = l;
        e[++l] = (edge) {x, ls[y]};
        ls[y] = l;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!fl[i])
        {
            dfs(i);
            ans += f[i][0] > f[i][1] ? f[i][0] : f[i][1];
        }
    printf("%d\n", ans);
}
]]>