CF 237E(字母选取-费用流)

题目大意:有一字符串S,你需要从n个字符串中选取一些来拼出这个串,第i个字符串代价为i,限制取P次,问最小代价(无解输出-1)

建立超源S=0,超汇T=n+26+1 

1-n的结点为字符串 n+1-n+26的结点为字符

则可得——————————————————

从S向字符串连(最多可取数量),费用为i

从字符向T连(欲取数量)

从字符串向字符连(字符串可取该字母的数量)

得到图

跑费用……

!负数的布尔值为1.

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>
#include<functional>
#include<iostream>
using namespace std;
#define MAXN (200+10)
#define M26 100
#define A 96
#define NONE (2139062143)
int map[MAXN][MAXN]={0},cost[MAXN][MAXN]={0},stf[M26]={0};
int start=0,end,n;
char s[5000];

int d[MAXN],pre[MAXN],q[MAXN*8];
bool b[MAXN];
void spfa()
{
    memset(b,0,sizeof(b));
    memset(d,127,sizeof(d));
    memset(q,0,sizeof(q));
    memset(pre,0,sizeof(pre));

    int head=1,tail=1;
    q[1]=start;b[start]=1;d[start]=0;
    while (head<=tail)
    {
        int now=q[head];
        for (int i=0;i<=end;i++)
        if (map[now][i]>0&&d[now]+cost[now][i]<d[i])
        {
            d[i]=d[now]+cost[now][i];
            pre[i]=now;
            if (!b[i])
            {
                q[++tail]=i;
                b[i]=1;
            }

        }

        b[now]=0;
        head++;
    }

}
void hllp()
{
    int totalcost=0;
    while (1)
    {
        spfa();
        if (d[end]==NONE) break;
        int flow=NONE,i=end;
        do
        {
            flow=min(flow,map[pre[i]][i]);
            i=pre[i];
        }while (i!=start);
        i=end;
        do
        {
            totalcost+=flow*cost[pre[i]][i];
            map[pre[i]][i]-=flow;
            map[i][pre[i]]+=flow;           
            i=pre[i];
        }while (i!=start);

    }
    for (int i=end-27;i<end;i++)
    if (map[i][end]) 
    {
        cout<<"-1\n";
        return;

    }
    cout<<totalcost<<endl;
}

int main()
{
//  freopen("c.in","r",stdin);
    scanf("%s",s);
    scanf("%d",&n);
    int len=strlen(s);
    for (int i=0;i<len;i++) stf[s[i]-A]++;
    end=n+27;
    for (int i=1;i<=26;i++) map[n+i][end]=stf[i];
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s);
        scanf("%d",&map[start][i]);
        memset(stf,0,sizeof(stf));
        for (int j=0;j<strlen(s);j++) stf[s[j]-A]++;
        for (int j=1;j<=26;j++) map[i][n+j]=stf[j];
        cost[0][i]=i;
        cost[i][0]=-cost[0][i];
    }
/*  for (int i=0;i<=end;i++)
        for (int j=0;j<=end;j++)
            if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/  hllp();
    cout<<'\n';
/*  for (int i=0;i<=end;i++)
        for (int j=0;j<=end;j++)
            if (map[i][j]) cout<<i<<' '<<j<<' '<<map[i][j]<<endl;
*/  
    return 0;
}