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;
}