题目大意：有一字符串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;
}