CF 321B Ciel and Duel(费用流)

时间：2022-08-09 08:32:38

题目链接：http://codeforces.com/problemset/problem/321/B

题意：两个人，分别有n、m张牌。每张牌有两个属性类型和能力，类型为攻击或者防守。B的m张牌的属性均为攻击。模拟以下过程：

（1）B所有的牌都使用过，结束；否则，B此时想要结束则结束，不想结束转（2）；

（2）B从自己未使用过的牌中选出一张，设其能力值为X，转（3）；

（3）A所有牌都使用过，A受到的伤害值为X，转（1）；否则转（4）；

（4）B从A未使用过的牌中选出一张，设其能力值为Y，若这张牌类型为攻击，能当X>=Y时，此轮进行，A受到伤害值X-Y；若类型为防守，则当X>Y时此轮进行，A不受到伤害。此轮一旦进行，结束后两个人使用的牌均标记使用过。转（1）。

帮助B设计一个方案使得A受到的伤害值最大？

思路：使用费用流，三个问题：

（1）A在使用完所有牌后若B还有剩余则那些剩余牌的伤害值才能加入答案；也就是若A还有牌要先保证使用完A的牌

（2）B在任意时刻可以决定结束；

（3）此题是求最大值，而费用流是求最小费用；

我们这样建图，A的n张牌拆开，编号i和i+n，B的m张牌编号n+n+1到n+n+m，增加原点S=n+n+m+1,t=n+n+m+2。

（1）(i,i+n,1,-2*INF)，(i+n,T,1,0)，费用-INF*2，保证一定在答案中；(1<=i<=n)

（2）(0,n+n+i,1,0)；  （1<=i<=m)

（3）(n+n+i,j,1,INF-(Xi-Yj))（攻击型），(n+n+i,j,1,INF)（防守型），最大改最小，符合最小费用，1<=i<=m,1<=j<=n

（4）(n+n+i,T,1,INF)，A用完之后剩下的B直接加入答案；

（5）(S,0,x,0)这里的x是枚举的，枚举1到m，代表B在任意时刻可以决定是否结束。

计算最小费用后转换为实际答案就好。

struct node
{
    int u,v,flow,next;
    i64 cost;
};

node edges[N];
int head[N],e;

void add(int u,int v,int flow,i64 cost)
{
    edges[e].u=u;
    edges[e].v=v;
    edges[e].flow=flow;
    edges[e].cost=cost;
    edges[e].next=head[u];
    head[u]=e++;
}

void Add(int u,int v,int flow,i64 cost)
{
    add(u,v,flow,cost);
    add(v,u,0,-cost);
}

int pre[N],F[N],visit[N],s,t;
i64 C[N];

int SPFA(int s,int t)
{
    int i;
    for(i=0;i<=t;i++) C[i]=inf*1000,F[i]=0,visit[i]=0;
    queue<int> Q;
    Q.push(s); C[s]=0; F[s]=INF;
    int u,v,f;
    i64 c;
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();

        visit[u]=0;
        for(i=head[u];i!=-1;i=edges[i].next)
        {
            v=edges[i].v;
            f=edges[i].flow;
            c=edges[i].cost;
            if(f>0&&C[v]>C[u]+c)
            {
                C[v]=C[u]+c;
                F[v]=min(F[u],f);
                pre[v]=i;
                if(!visit[v]) Q.push(v),visit[v]=1;
            }
        }
    }
    return F[t];
}

i64 MCMF(int s,int t)
{
    i64 ans=0;
    int i,temp,x;
    while(temp=SPFA(s,t))
    {
        for(i=t;i!=s;i=edges[pre[i]].u)
        {
            x=pre[i];
            ans+=temp*edges[x].cost;
            edges[x].flow-=temp;
            edges[x^1].flow+=temp;
        }
    }
    return ans;
}

string S[105];
int a[105],b[105],n,m;

i64 cal(int x)
{
    int i,j;
    s=n+n+m+1; t=n+n+m+2; clr(head,-1); e=0;
    FOR1(i,n) Add(i,n+i,1,-2*inf);
    FOR1(i,n) Add(n+i,t,1,0);
    FOR1(i,m) Add(0,n+n+i,1,0);
    Add(s,0,x,0);
    FOR1(i,m)
    {
        FOR1(j,n)
        {
            if(S[j]=="ATK")
            {
                if(b[i]>=a[j]) Add(n+n+i,j,1,inf-(b[i]-a[j]));
            }
            else
            {
                if(b[i]>a[j]) Add(n+n+i,j,1,inf);
            }
        }
    }
    FOR1(i,m) Add(n+n+i,t,1,inf-b[i]);
    i64 ans=MCMF(s,t);
    ans=ans+2*inf*min(x,n);
    ans=x*inf-ans;
    return ans;
}

int main()
{
    RD(n,m);
    int i;
    FOR1(i,n) RD(S[i]),RD(a[i]);
    FOR1(i,m) RD(b[i]);
    i64 ans=0;
    for(i=1;i<=m;i++)
    {
        ans=max(ans,cal(i));
    }
    PR(ans);
    return 0;
}

相关文章