首页 > 代码库 > BZOJ 1001:[BeiJing2006]狼抓兔子(最小割)
BZOJ 1001:[BeiJing2006]狼抓兔子(最小割)
http://www.lydsy.com/JudgeOnline/problem.php?id=1001
题意:中文。
思路:很明显是最小割,转化为最大流做。一开始看那么多点,但还是试了一下,居然过了。迷。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 using namespace std; 7 #define N 1000010 8 #define INF 0x3f3f3f3f 9 struct Edge {10 int v, cap, nxt;11 } edge[N*6];12 int head[N], cur[N], pre[N], tot, gap[N], dis[N], S, T;13 14 void Add(int u, int v, int cap) {15 edge[tot] = (Edge) {v, cap, head[u]}; head[u] = tot++;16 edge[tot] = (Edge) {u, cap, head[v]}; head[v] = tot++;17 }18 19 int BFS() {20 memset(gap, 0, sizeof(gap));21 memset(dis, INF, sizeof(dis));22 queue<int> que;23 que.push(T);24 dis[T] = 0; gap[0] = 1;25 while(!que.empty()) {26 int u = que.front(); que.pop();27 for(int i = head[u]; ~i; i = edge[i].nxt) {28 int v = edge[i].v;29 if(INF != dis[v]) continue;30 dis[v] = dis[u] + 1;31 gap[dis[v]]++;32 que.push(v);33 }34 }35 }36 37 int ISAP(int n) {38 BFS();39 memcpy(cur, head, sizeof(cur));40 int flow, ans = 0, u = pre[S] = S, i, index;41 while(dis[S] < n) {42 if(u == T) {43 flow = INF;44 for(i = S; i != T; i = edge[cur[i]].v)45 if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;46 for(i = S; i != T; i = edge[cur[i]].v)47 edge[cur[i]].cap -= flow, edge[cur[i]^1].cap += flow;48 ans += flow; u = index;49 }50 for(i = cur[u]; ~i; i = edge[i].nxt) if(edge[i].cap > 0 && dis[edge[i].v] == dis[u] - 1) break;51 if(~i) {52 cur[u] = i; pre[edge[i].v] = u; u = edge[i].v;53 } else {54 if(--gap[dis[u]] == 0) break;55 int md = n + 1;56 for(i = head[u]; ~i; i = edge[i].nxt)57 if(edge[i].cap > 0 && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;58 gap[dis[u] = md + 1]++;59 u = pre[u];60 }61 }62 return ans;63 }64 65 int main() {66 int n, m, w;67 scanf("%d%d", &n, &m);68 memset(head, -1, sizeof(head));69 tot = 0;70 for(int i = 0; i < n; i++)71 for(int j = 2; j <= m; j++)72 scanf("%d", &w), Add(j - 1 + i * m, j + i * m, w);73 for(int i = 1; i < n; i++)74 for(int j = 1; j <= m; j++)75 scanf("%d", &w), Add(j + (i - 1) * m, j + i * m, w);76 for(int i = 1; i < n; i++)77 for(int j = 2; j <= m; j++)78 scanf("%d", &w), Add(j - 1 + (i - 1) * m, j + i * m, w);79 S = 1, T = n * m;80 printf("%d\n", ISAP(T + 1));81 return 0;82 }
BZOJ 1001:[BeiJing2006]狼抓兔子(最小割)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。