CF243B Hydra

枚举点 \(u,v\)，或者说枚举边。然后找出 \(u,v\) 分别所连的点。

有数组 \(st\)，结点 \(x\) 仅与 \(u\) 相邻则 \(st[x]=1\)，仅与 \(v\) 相邻则 \(st[x]=2\)，与两个点都相邻则 \(st[x]=3\)。

用数组 \(rest\) 记录 \(st[x]=3\) 的所有 \(x\)。先优先选走至多 \(h\) 个 \(x|st[x]=1\)，再选走至多 \(t\) 个 \(x|st[x]=2\)。如果还不够就动用 \(rest\) 里面的。这个贪心很显然。

\(h,t\) 很小，复杂度可以保证。注意清空 \(st\) 不能直接 memset。

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=100010;
using namespace std;

int n, m, h, t, st[N];
vector<int> g[N];
int rest[N], k;

int main()
{
    #ifdef Jerrywang
    freopen("in.txt", "r", stdin);
    #endif
    scanf("%d%d%d%d", &n, &m, &h, &t);
    rep(i, 1, m)
    {
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    rep(u, 1, n) for(int v:g[u])
    {
        if(g[u].size()<=h || g[v].size()<=t) continue;
        for(int x:g[u]) if(x!=v)
            st[x]=1;
        k=0;
        for(int x:g[v]) if(x!=u)
        {
            st[x]+=2;
            if(st[x]==3) rest[++k]=x;
        }
        vector<int> head, tail;
        for(int x:g[u]) if(x!=v && st[x]==1)
        {
            head.push_back(x);
            if(head.size()>=h) break;
        }
        for(int x:g[v]) if(x!=u && st[x]==2)
        {
            tail.push_back(x);
            if(tail.size()>=t) break;
        }
        while(head.size()<h && k)
            head.push_back(rest[k--]);
        while(tail.size()<t && k)
            tail.push_back(rest[k--]);
        if(head.size()>=h && tail.size()>=t)
        {
            puts("YES");
            printf("%d %d\n", u, v);
            for(int x:head) printf("%d ", x);
            puts("");
            for(int x:tail) printf("%d ", x);
            return 0;
        }
        for(int x:g[u]) st[x]=0;
        for(int x:g[v]) st[x]=0;
    }
    puts("NO");
    
    return 0;
}

CF237E Build String

比较简单的费用流。

对源字符串和字母建点。

对于目标字符串中的每个字符 \(c\)，建边 \((c, t)\)，容量为 \(1\)，费用为 \(0\)。

然后考虑源字符串，计算费用。对于字符串 \(i\) 中的每个字符 \(c\)，建边 \((i, c)\)，容量为 \(1\)，费用为 \(i\)。

最后考虑限制，限制字符串 \(i\) 最多取 \(x\) 个字符，相当于建边 \((s, i)\)，容量为 \(x\)，费用为 \(0\)。

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
const int N=100010, inf=1e9;
using namespace std;

struct edge
{
    int v, c, w, n;
} e[N]; int hd[N], tot=1, n, m, s, t, siz;
void add(int u, int v, int c, int w)
{
    e[++tot]={v, c,  w, hd[u]}, hd[u]=tot;
    e[++tot]={u, 0, -w, hd[v]}, hd[v]=tot;
}
int d[N], in[N], f[N], pre[N];
bool spfa()
{
    rep(i, 1, t) d[i]=inf, in[i]=0;
    queue<int> q; q.push(s);
    d[s]=0, in[s]=1; f[s]=inf;
    while(q.size())
    {
        int u=q.front(); q.pop(); in[u]=0;
        for(int i=hd[u]; i; i=e[i].n)
        {
            int v=e[i].v, c=e[i].c, w=e[i].w;
            if(c && d[u]+w<d[v])
            {
                d[v]=d[u]+w;
                f[v]=min(f[u], c); pre[v]=i;
                if(!in[v]) in[v]=1, q.push(v);
            }
        }
    }
    return d[t]<inf;
}
int EK()
{
    int res=0, flow=0;
    while(spfa())
    {
        int u=t;
        while(u!=s)
        {
            int i=pre[u];
            e[i].c-=f[t], e[i^1].c+=f[t];
            u=e[i^1].v;
        }
        res+=f[t]*d[t], flow+=f[t];
    }
    if(flow<siz) res=-1;
    return res;
}
char a[N];
int main()
{
    #ifdef Jerrywang
    freopen("in.txt", "r", stdin);
    #endif
    scanf("%s%d", a+1, &n);
    s=n+26+1, t=s+1;
    siz=strlen(a+1); int x;
    rep(j, 1, siz)
    {
        x=a[j]-'a'+1;
        add(n+x, t, 1, 0);
    }
    rep(i, 1, n)
    {
        scanf("%s%d", a+1, &x);
        add(s, i, x, 0);
        m=strlen(a+1);
        rep(j, 1, m)
        {
            x=a[j]-'a'+1;
            add(i, n+x, 1, i);
        }
    }
    printf("%d", EK());
    
    return 0;
}