4.26 省选模拟赛 T3 状压dp 差分求答案

LINK：T3

比较好的题目考试的时候被毒瘤的T2给搞的心态爆炸这道题连正解的思路都没有想到。

一看到题求删除点的最少个可以使得不连通。

瞬间想到最小割发现对于10分直接跑最小割即可。

不过想要通过n^2需要一些奇技如从Si跑到Tj 想要得到i到j+1的答案只需要再从Tj跑到Tj+1即可。

可以发现这样做是有正确性的保证的这样最多跑n次整张图的最大流。

且增广路不断减小速度比较快。

const int MAXN = 40010;

int n, k, id, cc, len;

ll ans;

char a[MAXN][10][10];

int w[MAXN][10][2], S[MAXN], T[MAXN];

int lin[MAXN * 10], ver[MAXN * 100], nex[MAXN * 100], e[MAXN * 100], e1[MAXN * 100];

int vis[MAXN * 10], d[MAXN * 10], q[MAXN * 10];

inline void add(int x, int y, int z) {

    ver[++len] = y;

    nex[len] = lin[x];

    lin[x] = len;

    e[len] = z;

    e1[len] = z;

    ver[++len] = x;

    nex[len] = lin[y];

    lin[y] = len;

    e[len] = 0;

    e1[len] = 0;

}

inline int bfs(int S, int T) {

    ++cc;

    int h = 0, t = 0;

    q[++t] = S;

    d[S] = 1;

    vis[S] = cc;

    while (h++ < t) {

        int x = q[h];

        for (int i = lin[x]; i; i = nex[i]) {

            int tn = ver[i];

            if (vis[tn] == cc || !e[i])

                continue;

            vis[tn] = cc;

            q[++t] = tn;

            d[tn] = d[x] + 1;

            if (tn == T)

                return 1;

        }

    }

    return 0;

}

inline int dinic(int x, int flow, int T) {

    if (x == T)

        return flow;

    int rest = flow, k;

    for (int i = lin[x]; i && rest; i = nex[i]) {

        int tn = ver[i];

        if (e[i] && d[tn] == d[x] + 1) {

            k = dinic(tn, min(rest, e[i]), T);

            if (!k)

                d[tn] = 0;

            e[i] -= k;

            e[i ^ 1] += k;

            rest -= k;

        }

    }

    return flow - rest;

}

inline void bf() {

    ans = 0;

    rep(1, n, i) rep(i + 1, n, j) {

        rep(2, len, w) e[w] = e1[w];

        int flow = 0;

        while (bfs(S[i], T[j]))

            while ((flow = dinic(S[i], INF, T[j]))) ans += flow;

    }

    putl(ans);

}

inline void sol() {

    ans = 0;

    rep(1, n, i) {

        rep(2, len, w) e[w] = e1[w];

        rep(i + 1, n, j) {

            int flow = 0, cnt = 0;

            while (bfs(j - 1 == i ? S[i] : T[j - 1], T[j]))

                while ((flow = dinic((j - 1 == i) ? S[i] : T[j - 1], INF, T[j]))) cnt += flow;

            ans += cnt;

        }

    }

    putl(ans);

}

int main() {

    freopen("T3.in", "r", stdin);

    freopen("T3.out", "w", stdout);

    gt(n);

    gt(k);

    rep(1, n, i) {

        rep(1, k, j) {

            if (i != n) {

                gc(a[i][j]);

                // rep(1,k,cc)cout<<a[i][j][cc];

                // cout<<endl;

            }

            w[i][j][0] = ++id;

            w[i][j][1] = ++id;

        }

        S[i] = ++id;

        T[i] = ++id;

    }

    len = 1;

    rep(1, n, i) {

        rep(1, k, r) {

            add(w[i][r][1], T[i], INF);

            add(S[i], w[i][r][0], INF);

            add(w[i][r][0], w[i][r][1], 1);

            if (i != n)

                rep(1, k, cc) if (a[i][r][cc] == '1') add(w[i][r][1], w[i + 1][cc][0], INF);

        }

    }

    if (n <= 100)

        bf();

    else

        sol();

    return 0;

}

剩下的时间又又又去刚T2了就没细想。

正解：容易发现答案<=k 也同时存在 f(i,j)>=f(i,j+1)

由于点数较少容易想到一个状压设f[i][j][k]表示当前到了第i层此时删掉了j个点当前能到的集合为k.

一旦到达某一层集合为空就说明删掉的这些点就可以阻断。

需要求出来答案利用这个状态进行差分就能快速求出到某一层的答案。

值得一提的是由于起点不固定终点基本上固定所以倒着跑到每一个起点这样之前的dp数组还是可以使用的。

考虑转移先承接上一层的转移再考虑对当前集合删掉一些点。

枚举这个决策的时候直观的可以直接枚举子集不过这样复杂度\(3^k\).

优化就是可以利用之前的状态只需要枚举删掉哪个点就可以得到之前的状态。

细节挺多。

const int MAXN=40010;

int n,k,maxx;ll ans;

int f[2][10][1<<9];

char a[MAXN][10][10];

int go[MAXN][1<<9];

int w[MAXN],p[1<<9];

int main()

{

	freopen("T3.in","r",stdin);

	freopen("T3.out","w",stdout);

	//freopen("1.in","r",stdin);

	gt(n);gt(k);

	maxx=(1<<k)-1;

	rep(1,k,i)p[1<<(i-1)]=i;

	rep(1,n-1,i)

	{

		rep(1,k,j)

		{

			gc(a[i][j]);w[j]=0;

			rep(1,k,c)if(a[i][j][c]=='1')w[j]=w[j]|(1<<(c-1));

		}

		rep(0,maxx,j)go[i][j]=go[i][j-(j&(-j))]|w[p[j&(-j)]];

	}

	//f[i][j][k]表示到达第i层删掉的点数为j此时当前这层状态为k所能到达的最早的层数.

	memset(f,0x3f,sizeof(f));

	int u=0;

	fep(n,1,i)

	{

		u=u^1;

		rep(0,k,j)rep(0,maxx,c)f[u][j][c]=f[u^1][j][go[i][c]];

		f[u][0][0]=i;

		rep(1,k,j)rep(0,maxx,c)

		{

			for(int cc=c;cc;cc=cc-(cc&(-cc)))

			f[u][j][c]=min(f[u][j][c],f[u][j-1][c-(cc&(-cc))]);

		}

		rep(1,k,j)

		{

			if(f[u][j][maxx]>=INF)continue;

			ans+=((f[u][j-1][maxx]>=INF?n+1:f[u][j-1][maxx])-(j==k?i+1:f[u][j][maxx]))*j;

		}

	}

	putl(ans);

	return 0;

}

巴特西

4.26 省选模拟赛 T3 状压dp 差分求答案

最新文章

热门文章