首页 > 代码库 > POJ 3308 Paratroopers (二分图最小点权覆盖 -> 最小割 -> 最大流)
POJ 3308 Paratroopers (二分图最小点权覆盖 -> 最小割 -> 最大流)
POJ 3308 Paratroopers
链接:http://poj.org/problem?id=3308
题意:有一个N*M的方阵,有L个伞兵降落在方阵上。现在要将所有的伞兵都消灭掉,可以在每行每列装一个高射炮,如果在某行(某列)装上高射炮之后,能够消灭所有落在该行(该列)的伞兵。每行每列安高射炮有费用,问如何安装能够使得费用之积最小。
思路:首先题目要求乘积最小,将乘积对e取对数,会发现就变成了求和。然后抽象出一个二分图,每一行是x部的一个点,每个点有权值,权值为费用取ln。每一列是y部的一点,费用计算相同。如果有伞兵降落在方格上,那么将x部与y部连边。问题就成了求该二分图的最小点权覆盖。通过求最小割即可得到。而最小割就是最大流。所以构造一个流图。建立一个源点,源点向每一行连边,流量为费用,建立一个汇点,每列向汇点连边,流量为费用。二分图中原先的边的流量是INF。最后答案就是exp(最大流)。
细节:INF不能取太大,否则精度会有问题。
代码:
/* ID: wuqi9395@126.com PROG: LANG: C++ */ #include<map> #include<set> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<vector> #include<string> #include<fstream> #include<cstring> #include<ctype.h> #include<iostream> #include<algorithm> using namespace std; #define LINF (1LL<<60) #define INF 1e8 #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define rep(i, a, n) for (int i = a; i < n; i++) #define per(i, a, n) for (int i = n - 1; i >= a; i--) #define eps 1e-6 #define debug puts("===============") #define pb push_back //#define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m) typedef long long ll; typedef unsigned long long ULL; const int maxn = 110; const int maxm = 20000; int st, ed, n, m, l; struct node { int v; // vertex double cap; // capacity double flow; // current flow in this arc int nxt; } e[maxm * 2]; int g[maxn], cnt; void add(int u, int v, double c) { e[++cnt].v = v; e[cnt].cap = c; e[cnt].flow = 0; e[cnt].nxt = g[u]; g[u] = cnt; e[++cnt].v = u; e[cnt].cap = 0; e[cnt].flow = 0; e[cnt].nxt = g[v]; g[v] = cnt; } void init() { mem(g, 0); cnt = 1; st = 0; ed = m + n + 1; double w; int u, v; for (int i = 1; i <= m; i++) { scanf("%lf", &w); add(st, i, log(w)); } for (int i = m + 1; i < ed; i++) { scanf("%lf", &w); add(i, ed, log(w)); } for (int i = 1; i <= l; i++) { scanf("%d%d", &u, &v); add(u, m + v, INF); } n = ed + 3; } int dist[maxn], numbs[maxn], q[maxn]; void rev_bfs() { int font = 0, rear = 1; for (int i = 0; i <= n; i++) { //n为总点数 dist[i] = maxn; numbs[i] = 0; } q[font] = ed; dist[ed] = 0; numbs[0] = 1; while(font != rear) { int u = q[font++]; for (int i = g[u]; i; i = e[i].nxt) { if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue; dist[e[i].v] = dist[u] + 1; ++numbs[dist[e[i].v]]; q[rear++] = e[i].v; } } } double maxflow() { rev_bfs(); int u; double totalflow = 0; int curg[maxn], revpath[maxn]; for(int i = 0; i <= n; ++i) curg[i] = g[i]; u = st; while(dist[st] < n) { if(u == ed) { // find an augmenting path double augflow = INF; for(int i = st; i != ed; i = e[curg[i]].v) augflow = min(augflow, e[curg[i]].cap); for(int i = st; i != ed; i = e[curg[i]].v) { e[curg[i]].cap -= augflow; e[curg[i] ^ 1].cap += augflow; e[curg[i]].flow += augflow; e[curg[i] ^ 1].flow -= augflow; } totalflow += augflow; u = st; } int i; for(i = curg[u]; i; i = e[i].nxt) if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break; if(i) { // find an admissible arc, then Advance curg[u] = i; revpath[e[i].v] = i ^ 1; u = e[i].v; } else { // no admissible arc, then relabel this vertex if(0 == (--numbs[dist[u]])) break; // GAP cut, Important! curg[u] = g[u]; int mindist = n; for(int j = g[u]; j; j = e[j].nxt) if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]); dist[u] = mindist + 1; ++numbs[dist[u]]; if(u != st) u = e[revpath[u]].v; // Backtrack } } return totalflow; } int main () { int T; scanf("%d", &T); while(T--) { scanf("%d%d%d", &m, &n, &l); init(); printf("%.4f\n", exp(maxflow())); } return 0; }
POJ 3308 Paratroopers (二分图最小点权覆盖 -> 最小割 -> 最大流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。