Codeforces 1009G Allowed Letters 最大流转最小割 sosdp

最直观的想法是贪心取，然后网络流取check可不可行，然后T了。

想到最大流可以等于最小割，那么我们状压枚举字符代表的6个点连向汇点是否断掉，

然后再枚举64个本质不同的位置，是否需要切段原点联想它的边，单次check复杂度64 * 64

用sosdp能优化到64 * 6

#include<bits/stdc++.h>

#define LL long long

#define LD long double

#define ull unsigned long long

#define fi first

#define se second

#define mk make_pair

#define PLL pair<LL, LL>

#define PLI pair<LL, int>

#define PII pair<int, int>

#define SZ(x) ((int)x.size())

#define ALL(x) (x).begin(), (x).end()

using namespace std;

const int N = 2e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

const double PI = acos(-);

template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}

template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < ) a += mod;}

template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}

template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;}

int n, m, mask[N], c[N], cnt[N], sos[N];

char s[N], t[N], ans[N];

bool check() {

    int sum = , ret = inf;

    for(int i = ; i < ; i++) sum += c[i];

    for(int i = ; i < ; i++) sos[i] = cnt[i];

    for(int i = ; i < ; i++)

        for(int j = ; j < ; j++)

            if(j >> i & ) sos[j] += sos[j ^ ( << i)];

    for(int s1 = ; s1 < ; s1++) {

        int tmp = ;

        for(int i = ; i < ; i++)

            if(s1 >> i & ) tmp += c[i];

        tmp += sum - sos[s1];

        chkmin(ret, tmp);

    }

    return sum == ret;

}

inline int getId(char c) {

    return c - 'a';

}

int main() {

    scanf("%s", s + );

    n = strlen(s + );

    for(int i = ; i <= n; i++) c[getId(s[i])]++;

    scanf("%d", &m);

    while(m--) {

        int p; scanf("%d%s", &p, t + );

        for(int i = ; t[i]; i++) mask[p] |=  << getId(t[i]);

    }

    for(int i = ; i <= n; i++) {

        if(!mask[i]) mask[i] = ;

        cnt[mask[i]]++;

    }

    for(int i = ; i <= n; i++) {

        bool flag = false;

        for(int j = ; j < ; j++) {

            if(c[j] && mask[i] >> j & ) {

                c[j]--;

                cnt[mask[i]]--;

                flag = check();

                if(flag) {

                    ans[i] = 'a' + j;

                    break;

                }

                c[j]++;

                cnt[mask[i]]++;

            }

        }

        if(!flag) return puts("Impossible"), ;

    }

    ans[n + ] = '\0';

    puts(ans + );

    return ;

}

/*

*/