【洛谷 P3227】 [HNOI2013]切糕（最小割）

题目链接

每层每个位置向下一层这个位置连边，流量为下一层这个位置的\(f\)，源点向第一层连，流量第一层每个位置的费用，最后一层向汇点连，流量\(INF\)。

这样就得到了\(P*Q\)条链，不考虑\(D\)的限制的话求最小割就是答案。

现在加入限制。记结论吧，我也不知道什么原理

每个位置从\(i=D+1\)层开始，向他前后左右第\(i-D\)层连边，流量\(INF\)。

然后求出最小割即为答案。

#include <cstdio>

#include <queue>

#include <cstring>

#define INF 2147483647

using namespace std;

const int MAXN = 900010;

const int MAXM = 2000010;

inline int read(){

    int s = 0, w = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }

    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }

    return s * w;

}

struct Edge{

    int next, to, rest;

}e[MAXM];

int s, t, num = 1, n, m, a, b, c, p, q, r, d, f[45][45][45];

int head[MAXN];

inline void Add(int from, int to, int flow){

    e[++num] = (Edge){ head[from], to, flow }; head[from] = num;

    e[++num] = (Edge){ head[to], from, 0 }; head[to] = num;

}

int level[MAXN], now, sum;

queue <int> Q;

int re(){

	memset(level, 0, sizeof level);

    while(Q.size()) Q.pop();

    Q.push(s); level[s] = 1;

    while(Q.size()){

      now = Q.front(); Q.pop();

      for(int i = head[now]; i; i = e[i].next)

         if(e[i].rest && !level[e[i].to]){

           level[e[i].to] = level[now] + 1;

           Q.push(e[i].to);

         }

    }

    return level[t];

}

int findflow(int u, int flow){

	if(!flow || u == t) return flow;

	int f = 0, t;

	for(int i = head[u]; i; i = e[i].next){

		if(e[i].rest && level[e[i].to] == level[u] + 1){

			f += (t = findflow(e[i].to, min(flow - f, e[i].rest)));

			e[i].rest -= t; e[i ^ 1].rest += t;

		}

	}

	if(!f) level[u] = 0;

	return f;

}

int dinic(){

    int ans = 0;

    while(re())

      ans += findflow(s, INF);

    return ans;

}

int id(int k, int i, int j){

	if(!k) return s;

	return (k - 1) * (p * q) + (i - 1) * q + j;

}

int L[] = {233, -1, 1, 0, 0}, R[] = {666, 0, 0, -1, 1};

int main(){

    p = read(); q = read(); r = read(); d = read();

    s = 899999; t = 900000;

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

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

          Add(id(r, i, j), t, INF);

    for(int k = 1; k <= r; ++k)

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

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

             Add(id(k - 1, i, j), id(k, i, j), read());

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

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

          for(int k = 1; k <= 4; ++k){

          	 int x = i + L[k], y = j + R[k];

          	 if(!x || !y || x > p || y > q) continue;

          	 for(int o = d + 1; o <= r; ++o)

          	    Add(id(o, i, j), id(o - d, x, y), INF);

          }

    printf("%d\n", dinic());

    return 0;

}

巴特西

【洛谷 P3227】 [HNOI2013]切糕（最小割）

最新文章

热门文章