BZOJ 1001 狼抓兔子 (网络流最小割/平面图的对偶图的最短路)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1001

算法讨论:

1、可以用最大流做,最大流等于最小割。

2、可以把这个图转化其对偶图,然后在对偶图上跑最短路即可。

一个平面图的最小割等价于其对偶图从S到T的最短路。并不是所有的图都有对偶图,平面图也有一定的要求,自己可以百度一下。

代码(用BZOJ的数据测过了,但是在BZOJ上过不去。爆WA,并不知道是为什么,里面有个特判,并不知道有没有用处。)

 #include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstdio> using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f; int n, cnt, m;
int head[N], que[N], dis[N];
bool vis[N]; struct Edge {
int from, to, dis, next;
}edges[N * ]; void add(int u, int v, int dis) {
++ cnt;
edges[cnt].from = u; edges[cnt].to = v;
edges[cnt].dis = dis; edges[cnt].next = head[u];
head[u] = cnt;
++ cnt;
edges[cnt].from = v; edges[cnt].to = u;
edges[cnt].dis = dis; edges[cnt].next = head[v];
head[v] = cnt;
} void spfa(int s, int t) {
int h = , tail = ;
for(int i = s; i <= t; ++ i) {
dis[i] = inf;
vis[i] = false;
}
vis[s] = true; dis[s] = ;
que[h] = s;
while(h <= tail) {
int x = que[h];
vis[x] = false;
for(int i = head[x]; i; i = edges[i].next) {
int v = edges[i].to;
if(dis[v] > dis[x] + edges[i].dis) {
dis[v] = dis[x] + edges[i].dis;
if(!vis[v]) {
que[++ tail] = v;
vis[v] = true;
}
}
}
++ h;
}
printf("%d\n", dis[t]);
} #define stone int main() {
#ifndef stone freopen("bjrabbit.in", "r", stdin);
freopen("bjrabbit.out", "w", stdout); #endif int tmp, s, t, x, mn = 0x3f3f3f3f;
scanf("%d%d", &n, &m);
s = ; t = (n - ) * (m - ) * + ;
tmp = (m - ) * ;
for(int i = ; i <= n; ++ i) {
for(int j = ; j < m; ++ j) {
scanf("%d", &x);
mn = min(x, mn);
if(i == ) {
add(j * + tmp * (i - ), t, x);
}
else if(i == n) {
add(s, j * + tmp * (i - ) - , x);
}
else {
add(j * + tmp * (i - ), j * + tmp * (i - ) - , x);
}
}
}
for(int i = ; i < n; ++ i) {
for(int j = ; j <= m; ++ j) {
scanf("%d", &x);
mn = min(x, mn);
if(j == ) {
add(s, tmp * (i - ) + , x);
}
else if(j == m) {
add(tmp * i, t, x);
}
else {
add(tmp * (i - ) + * (j - ), tmp * (i - ) + * (j - ) + , x);
}
}
}
for(int i = ; i < n; ++ i) {
for(int j = ; j < m; ++ j) {
scanf("%d", &x);
mn = min(mn, x);
add(tmp * (i - ) + j * , tmp * (i - ) + j * - , x);
}
}
if(n == || m == ) printf("%d\n", mn);
else spfa(s, t); #ifndef stone fclose(stdin); fclose(stdout); #endif return ;
}

1001

上一篇:Java三大主流开源工作流引擎技术分析


下一篇:SQL Server相似度比较函数