做个公司网站一般需要多少钱,上海公司网站建设哪家好,网站设计远程培训,长沙 网页制作教程题义很简单#xff0c;还记得方格取数(1)的时候#xff0c;使用状态压缩写的#xff0c;这里由于行列数太大#xff0c;因此无法进行压缩。所以要运用的最小割最大流的思想来解这道题。 大概是这样分析的#xff0c;题义是要我们求在一个方格内取出N个点#xff0c;使得这… 题义很简单还记得方格取数(1)的时候使用状态压缩写的这里由于行列数太大因此无法进行压缩。所以要运用的最小割最大流的思想来解这道题。 大概是这样分析的题义是要我们求在一个方格内取出N个点使得这N个独立的不相邻点集的和最大。我们可以将问题转化为最小割来求解。首先我们将方格进行黑白相间的染色然后再将任意一种颜色黑色作为源点一种颜色白色作为汇点。我们的算法过程就是一个不断寻找增广路的过程。当我们找到最大流的时也就是此时不存在从黑色到白色的路径也即不存在不相邻的两个方格能够连通了。而此时的最大流就是分割两个区间的最小割拿总合值减去这个最小割就是我们想要得到的结果。 代码如下 #include cstring
#include cstdlib
#include cstdio
#include queue
#define RE(x) (x)^1
#define INF 0x3fffffff
#define MAXN 50
using namespace std;int N, M, dis[MAXN*MAXN10], head[MAXN*MAXN10], idx, source, sink;
int G[MAXN10][MAXN10];int dir[4][2] {0, 1, 1, 0, 0, -1, -1, 0};struct Edge
{int v, cap, next;
}e[200000];void init()
{idx -1;source N*M, sink N*M1;memset(head, 0xff, sizeof (head));
}int to(int x, int y)
{return (x-1)*My-1;
}void insert(int a, int b, int c)
{idx;e[idx].v b, e[idx].cap c;e[idx].next head[a], head[a] idx;
}bool judge(int x, int y)
{if (x 1 || x N || y 1 || y M) {return false;}else {return true;}
}bool bfs()
{int u;queueintq;memset(dis, 0xff, sizeof (dis));dis[source] 0;q.push(source);while (!q.empty()) {u q.front();q.pop();for (int i head[u]; i ! -1; i e[i].next) {if (dis[e[i].v] -1 e[i].cap 0) {dis[e[i].v] dis[u] 1;q.push(e[i].v);}}}return dis[sink] ! -1;
}int dfs(int u, int flow)
{if (u sink) {return flow;}int tf 0, sf;for (int i head[u]; i ! -1; i e[i].next) {if (dis[u]1 dis[e[i].v] e[i].cap 0 (sf dfs(e[i].v, min(flow-tf, e[i].cap)))) {e[i].cap - sf, e[RE(i)].cap sf;tf sf;if (tf flow) {return flow;}}}if (!tf) {dis[u] -1;}return tf;
}int Dinic()
{int ans 0;while (bfs()) {ans dfs(source, INF);}return ans;
}int main()
{int sum;while (scanf(%d %d, N, M) 2) {sum 0;init();for (int i 1; i N; i) {for (int j 1; j M; j) {scanf(%d, G[i][j]);sum G[i][j];}}for (int i 1; i N; i) {for (int j 1; j M; j) {if (!((ij)1)) { insert(source, to(i, j), G[i][j]);insert(to(i, j), source, 0);for (int k 0; k 4; k) {int xx idir[k][0], yy jdir[k][1]; if (judge(xx, yy)) {insert(to(i, j), to(xx, yy), G[i][j]);insert(to(xx, yy), to(i, j), 0);}}} else {insert(to(i, j), sink, G[i][j]);insert(sink, to(i, j), 0);}}}printf(%d\n, sum - Dinic());}return 0;
}
