首页 > 代码库 > LA3276
LA3276
费用流
这种棋盘模型大概都是网络流吧
首先我们知道棋子之间不会影响到达目标的步数,那么就好做了,枚举终点,然后就是最小权匹配了,因为就是寻找总和最小,然后费用流就行了。
#include<bits/stdc++.h> using namespace std; const int N = 110, inf = 0x3f3f3f3f; struct data { int x, y; } a[N]; struct edge { int nxt, to, f, c; } e[N * N]; int n, S, T, tot, cnt = 1, ans, kase; int head[N], dis[N], q[N], Map[N][N], pree[N], prevv[N], inq[N]; void link(int u, int v, int f, int c) { e[++cnt].nxt = head[u]; head[u] = cnt; e[cnt].to = v; e[cnt].f = f; e[cnt].c = c; } void insert(int u, int v, int f, int c) { link(u, v, f, c); link(v, u, 0, -c); } bool spfa() { int l = 1, r = 0; memset(dis, 0x3f3f, sizeof(dis)); dis[0] = 0; q[++r] = 0; while(l <= r) { int u = q[l++]; inq[u] = 0; for(int i = head[u]; i; i = e[i].nxt) if(e[i].f && dis[e[i].to] > dis[u] + e[i].c) { pree[e[i].to] = i; prevv[e[i].to] = u; dis[e[i].to] = dis[u] + e[i].c; if(!inq[e[i].to]) { inq[e[i].to] = 1; q[++r] = e[i].to; } } } return dis[T] != 0x3f3f3f3f; } int getflow() { int now = T, delta = inf; while(now) { delta = min(delta, e[pree[now]].f); now = prevv[now]; } now = T; while(now) { e[pree[now]].f -= delta; e[pree[now] ^ 1].f += delta; now = prevv[now]; } return delta * dis[T]; } int maxcostflow() { int ret = 0; while(spfa()) ret += getflow(); return ret; } void build() { memset(head, 0, sizeof(head)); cnt = 1; for(int i = 1; i <= n; ++i) insert(S, i, 1, 0); for(int i = 1; i <= n; ++i) for(int x = 1; x <= n; ++x) for(int y = 1; y <= n; ++y) if(Map[x][y]) insert(i, Map[x][y], 1, abs(a[i].x - x) + abs(a[i].y - y)); for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) if(Map[i][j]) insert(Map[i][j], T, 1, 0); } int main() { while(scanf("%d", &n)) { if(!n) break; T = 2 * n + 1; ans = inf; for(int i = 1; i <= n; ++i) scanf("%d%d", &a[i].x, &a[i].y); for(int i = 1; i <= n; ++i) { memset(Map, 0, sizeof(Map)); tot = n; for(int j = 1; j <= n; ++j) Map[i][j] = ++tot; build(); ans = min(ans, maxcostflow()); memset(Map, 0, sizeof(Map)); tot = n; for(int j = 1; j <= n; ++j) Map[j][i] = ++tot; build(); ans = min(ans, maxcostflow()); } memset(Map, 0, sizeof(Map)); tot = n; for(int i = 1; i <= n; ++i) Map[i][i] = ++tot; build(); ans = min(ans, maxcostflow()); memset(Map, 0, sizeof(Map)); tot = n; for(int i = 1; i <= n; ++i) Map[i][n - i + 1] = ++tot; build(); ans = min(ans, maxcostflow()); printf("Board %d: %d moves required.\n\n", ++kase, ans); } return 0; }
LA3276
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。