HDU-5383 - Yu-Gi-Oh! - 最小费用网络流

Problem

合怪升级，每只怪有他的等级和攻击力，以及是否为 tuner monster. 合怪必须一只 tuner monster 与一只 non-tuner monster 合，并且他们的等级之和必须等于合成的怪。只有特定等级和攻击力的怪可以被合成。某些合成怪必须用特定的某一只或某两只怪才能合成。

Solution

看懂题目后建图跑网络流。主要难点在建图。
将 tuner monster(t1) 连到源点，将 non-tuner monster(t2) 连到汇点， capacity 均为 1， cost 均为0。并且列举将该怪与所有另一种怪的组合，以合成等级为索引保存。注意最大等级上限为12，超过12的组合直接 pass 掉。
然后处理合成怪。在合成怪对应等级中搜索对应满足条件的组合，加入到 t1, t2 矩阵中。这里有一个必须搞的优化，就是只选攻击力最大且大于两只被合成怪的合成怪，对满足的 t1，t2 连 capacity 为 1， cost 为 t1 攻击力 加 t2 攻击力 减 合成怪攻击力。
另外这题有个坑点，就是要在跑 mincost 的时候判断 cost，如果 cost 增加了，就退出...
可能是最小费用最大流优先保障最大流，而该题不需要保障最大流，故而优先保障最小费用。
涨姿势...

Code

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(_array,val) memset(_array,val,sizeof(_array))
#define MEM0(_array) MEM(_array,0)
#define MEMZ(_array) MEM(_array,0)
#define FORUP(_v,_b,_n) for(int _v=(_b);_v<=(_n);++_v)
#define FORDOWN(_v,_b,_n) for(int _v=(_b);_v>=(_n);--_v)
#define NXTINT(_v) scanf("%d",&(_v))
#define NXTLL(_v) scanf("%lld",&(_v))
#define TCASES() int _T;NXTINT(_T);while (_T--)

const int MAXN=310;
const int MAXM=MAXN*MAXN*2;
int N,M;

struct EDG
{
    int u,v,cap,flow,cost;
} es[MAXM];
int fst[MAXN],nxt[MAXM];
int coe;
inline void mkedg(int u,int v,int cap,int cost)
{
    es[++coe]=EDG{u,v,cap,0,cost};
    nxt[coe]=fst[u];
    fst[u]=coe;
    es[++coe]=EDG{v,u,0,0,-cost};
    nxt[coe]=fst[v];
    fst[v]=coe;
}
inline void init()
{
    coe=1; MEM0(fst);
}
//inline void printG()
//{
//    for (int i=0;i<=N+1;++i)
//    {
//        printf("------ Point: %d ------\n",i);
//        int cnt=0;
//        for (int k=fst[i];k;k=nxt[k]) {
//            ++cnt;
////            printf("v: %d\t cap: %d\t cost: %d\n",es[k].v,es[k].cap,es[k].cost);
//        }
//        printf("%d\n",cnt);
//    }
//}

const int INF=0x7FFFFFFF;
int S,T;
int d[MAXN]; // distance
int p[MAXN]; // path edge indexes
int a[MAXN]; // max available capability
bool inq[MAXN]; // in queue
bool spfa()
{
    fill(d,d+MAXN,INF);
    MEM0(inq);

    // find current lowest cost path
    queue<int> Q;
    d[S]=0; p[S]=0; a[S]=INF;
    Q.push(S); inq[S]=1;
    while (!Q.empty())
    {
        int u=Q.front(); Q.pop();
        inq[u]=0;
        for(int k=fst[u];k;k=nxt[k])
        {
            EDG& e=es[k];
            if (e.cap>e.flow && d[e.v]>d[u]+e.cost)
            {
                d[e.v]=d[u]+e.cost;
                p[e.v]=k;
                a[e.v]=min(a[u],e.cap-e.flow);
                if (!inq[e.v]) {
                    Q.push(e.v); inq[e.v]=1;
                }
            }
        }
    }
    return d[T]!=INF;
}
int mincost(int s,int t)
{
    int flow=0,cost=0;
    S=s; T=t;
    int res=0;
    while (spfa())
    {
        flow+=a[T];
        cost+=d[T]*a[T];
        if (cost>res) return res;
        else res=cost;
        for (int u=T;u!=S;u=es[p[u]].u) {
            es[p[u]].flow+=a[T];
            es[p[u]^1].flow-=a[T];
        }
    }
    return res;
}

const int MAXLV=13;
struct MON
{
    int lv,atk;
    int id;
} mon0[MAXN],mon1[MAXN];
int cm0,cm1;
int refe[MAXN],reftp[MAXN];
struct COMBO
{
    int m0,m1;
    int atk;
} combo[MAXLV+1][MAXN*MAXN];
int cocbm[MAXLV+1];
inline void combine(int m0,int m1)
{
    int cblv=mon0[m0].lv+mon1[m1].lv;
    if (cblv>MAXLV) return;
    combo[cblv][++cocbm[cblv]]=COMBO{m0,m1,mon0[m0].atk+mon1[m1].atk};
}
int G[MAXN][MAXN];
inline void cbedg(int i0,int i1,int atk)
{
    G[i0][i1]=max(G[i0][i1],atk);
}

int main()
{
#ifdef LOCAL
    freopen("IN1.txt","r",stdin);
#endif

    LL sum;
    TCASES()
    {
        init();
        sum=0;
        MEM0(cocbm);
        cm0=cm1=0;
        MEM0(G);
        scanf("%d%d",&N,&M);
        for(int i=1;i<=N;++i) {
            int tp,lv,atk;
            scanf("%d%d%d",&tp,&lv,&atk);
            sum+=atk;
            if (tp==0)
            {
                mon0[++cm0]=MON{lv,atk,i};
                mkedg(0,i,1,0);
                refe[i]=cm0; reftp[i]=tp;
                for(int j=1;j<=cm1;++j) combine(cm0,j);
            }
            else
            {
                mon1[++cm1]=MON{lv,atk,i};
                mkedg(i,N+1,1,0);
                refe[i]=cm1; reftp[i]=tp;
                for(int j=1;j<=cm0;++j) combine(j,cm1);
            }
        }
//        for(int i=1;i<dip;++i)
//        for(int j=dip;j<=N;++j)
//            mkedg(mon[i].id,mon[j].id,1,0);
        for(int i=1;i<=M;++i)
        {
            int lv,atk,coc,i0,i1;
            scanf("%d%d%d",&lv,&atk,&coc);
            if (coc==2) {
                scanf("%d%d",&i0,&i1);
                if (reftp[i0]==1) swap(i0,i1);
                cbedg(refe[i0],refe[i1],atk);
            } else if (coc==1) {
                scanf("%d",&i0);
                if (reftp[i0]==0) {
                    for(int j=1;j<=cocbm[lv];++j)
                        if (combo[lv][j].m0==refe[i0])
                            cbedg(refe[i0],combo[lv][j].m1,atk);
                } else {
                    for(int j=1;j<=cocbm[lv];++j)
                        if (combo[lv][j].m1==refe[i0])
                            cbedg(combo[lv][j].m0,refe[i0],atk);
                }
            } else {
                for(int j=1;j<=cocbm[lv];++j)
                    cbedg(combo[lv][j].m0,combo[lv][j].m1,atk);
            }
        }
        for (int i=1;i<=cm0;++i)
        for (int j=1;j<=cm1;++j)
        {
            int diff=mon0[i].atk+mon1[j].atk-G[i][j];
            if (diff<0) mkedg(mon0[i].id,mon1[j].id,1,diff);
        }
        //printG();
        printf("%lld\n",sum-mincost(0,++N));
    }

    return 0;
}

Comments

虽然之前写过一遍这个的题解了。但是貌似贴在 github 上的代码不是 AC 代码 emmmmmm...
然后就索性重新认真写了下题解，（在掌握了 md 和 highlight, 自己编写了 md2post 这样的黑科技的帮助下233）。