PAT-T-1004 To Buy or Not to Buy

//最小费用最大流
//源点向每种字母连边，容量为t中该种字母的需求
//每种字母向每个字符串连边，容量为每个字符串自身有多少该种字母
//每个字符串向汇点连边，容量为无限大，费用为字符串自身的长度
//看最大流量是不是等于t的长度，如果等于则输出Yes，最少费用
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
const int inf=1e9;
int n;
string S[maxn];
int cnt[256][maxn];
int s,t;
int visit[maxn];
int dis[maxn];//源点到每个点的最小花费（最短路）
int pre[maxn];//前驱
int lst[maxn];//每个点所连的前一条边
int flow[maxn];//源点到此处的流量
int maxflow;//最大流
int mincost;//最小费用
struct node {
    int u,v,flow,dis,nxt;
}edge[maxn*2];
int tot;
int head[maxn];
void addedge (int u,int v,int flow,int dis) {
    edge[tot].u=u;
    edge[tot].v=v;
    edge[tot].flow=flow;
    edge[tot].dis=dis;
    edge[tot].nxt=head[u];
    head[u]=tot++;
    
    
    edge[tot].u=v;
    edge[tot].v=u;
    edge[tot].flow=0;
    edge[tot].dis=-dis;
    edge[tot].nxt=head[v];
    head[v]=tot++;
} 
bool spfa (int s,int t) {
    for (int i=0;i<maxn;i++) dis[i]=inf,flow[i]=inf,visit[i]=0;
    queue<int> q;
    q.push(s);
    visit[s]=1;
    dis[s]=0;
    pre[t]=-1;
    while (!q.empty()) {
        int u=q.front();
        q.pop();
        visit[u]=0;
        for (int i=head[u];i!=-1;i=edge[i].nxt) {
            if (edge[i].flow>0&&dis[edge[i].v]>dis[u]+edge[i].dis) {
                dis[edge[i].v]=dis[u]+edge[i].dis;
                pre[edge[i].v]=u;
                lst[edge[i].v]=i;
                flow[edge[i].v]=min(flow[u],edge[i].flow);
                if (!visit[edge[i].v]) {
                    visit[edge[i].v]=1;
                    q.push(edge[i].v);
                }
            }
        }
    }
    return pre[t]!=-1;
} 
void MCMF () {
    while (spfa(s,t)) {
        int u=t;
        maxflow+=flow[t];
        mincost+=dis[t];
        while (u!=s) {
            edge[lst[u]].flow-=flow[t];
            edge[lst[u]^1].flow+=flow[t];
            u=pre[u];
        }
    }
} 
int main () {
    cin>>S[0];
    scanf("%d",&n);
    for (int i=0;i<maxn;i++) head[i]=-1;
    for (int i=1;i<=n;i++) cin>>S[i];
    for (int i=0;i<=n;i++) {
        for (int j=0;j<S[i].length();j++) {
            cnt[S[i][j]][i]++;
        }
    } 
    //源点是0
    //1~256是每种字母
    //256+1~256+1+n是每种字符串
    //256+1+n+1是汇点
    s=0;
    t=258+n;
    for (int i=1;i<=256;i++) addedge(s,i,cnt[i-1][0],0);
    for (int i=1;i<=256;i++) {
        for (int j=1;j<=n;j++) {
            addedge(i,j+256,cnt[i-1][j],0);
        }
    } 
    for (int i=1;i<=n;i++) addedge(256+i,t,inf,S[i].length());
    MCMF();
    if (maxflow<S[0].length()) {
        printf("No %d
",S[0].length()-maxflow);
    }
    else {
        int ans=0;
        for (int i=0;i<tot;i+=2) if (edge[i^1].flow) ans+=edge[i].dis;
        printf("Yes %d
",ans-S[0].length());
    } 
}