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