首页 > 代码库 > hdu 4309 Seikimatsu Occult Tonneru 枚举+最大流
hdu 4309 Seikimatsu Occult Tonneru 枚举+最大流
http://blog.csdn.net/julyana_lin/article/details/8070949
题意: n个点,每个点有初始的值 ，三种 通道，1、隧道：可以用来躲避，有固定的容量，也可以用来传递。2、普通的道路，可以无限的通过。3、桥（最多有12座）：不花费的话能通过一人，修之后可以无限通过。问最少花费最大可以隐藏人数。
解：
网络流 + 枚举
官方题解：
先不考虑可以修复的桥的性质，则可以将模型简化为n个点的人通过有通过人数上限的有向边，到达一些有人数上限的特殊的边（隧道）。 可以建立最大流模型来求解，增加一个源点S，和一个汇点T。S向每个有人的点，连一条容量为人数的边，图中普通的u->v的有向边，连一条u->v的流量为无穷的边，桥的流量则为1。对于隧道，每个隧道可以虚拟出一个点，如u->v的隧道，可以虚拟一个点x，连接u->x,x->v的流量无穷的边，和x->T的流量为隧道人数上限的边，求解最大流即可得到最大人数。 现在考虑桥的问题，题目中说明了桥最多只有12座，故可以2^12枚举修复哪些桥，不修复的桥没有花费，连接的边流量为1，要修复的桥则计算花费，边的流量为无穷，这样进行2^12次最大流就可以得到最优解。
#include <cstdio>#include <cstring>const int MAXN = 205;const int MAXM = 2505;const int INF = 1000000000;struct Edge{ int u, v, next, flow;}edge[MAXM], redge[MAXM];int edgeNumber, head[MAXN], rhead[MAXN];int source = MAXN - 1;int destination = MAXN - 2;int depth[MAXN];inline int min(int x, int y){ return x < y ? x : y;}void addEdgeSub(int u, int v, int flow){ edge[edgeNumber].u = u; edge[edgeNumber].v = v; edge[edgeNumber].flow = flow; edge[edgeNumber].next = head[u]; head[u] = edgeNumber ++;}void addEdge(int u, int v, int flow){ addEdgeSub(u, v, flow); addEdgeSub(v, u, 0);}int n, m;int bridgePosition[MAXN];int bridgeCost[MAXN];int bridgeNumber;bool bfs(int start, int end){ int front = 0, rear = 0; int queue[MAXN]; memset(depth, -1, sizeof(depth)); queue[front++] = start; depth[start] = 0; while(rear < front) { int k = queue[rear++]; for(int i=head[k];i!=-1;i=edge[i].next) { int to = edge[i].v; if(-1 == depth[to] && edge[i].flow > 0) { depth[to] = depth[k] + 1; queue[front++] = to; } } } return -1 != depth[end];}int dinic(int start, int end, int sum){ if(start == end) { return sum; } int temp = sum; for(int i=head[start];i!=-1 && sum;i=edge[i].next) { if(edge[i].flow > 0 && depth[edge[i].v] == depth[start] + 1) { int a = dinic(edge[i].v, end, min(sum, edge[i].flow)); edge[i].flow -= a; edge[i^1].flow += a; sum -= a; } } return temp - sum;}int maxFlow(int start, int end){ int result = 0; while(bfs(start, end)) { result += dinic(start, end, INF); } return result;}int main(){ int u, v, w, p; while(~scanf("%d%d", &n, &m)) { int pointNumber = n + 1; edgeNumber = 0; bridgeNumber = 0; memset(head, -1, sizeof(head)); for(int i=1;i<=n;++i) { scanf("%d", &w); addEdge(source, i, w); } for(int i=0;i<m;++i) { scanf("%d%d%d%d",&u,&v,&w,&p); if(p < 0) { addEdge(u, pointNumber, INF); addEdge(pointNumber, v, INF); addEdge(pointNumber, destination, w); ++ pointNumber; } else if(p == 0) { addEdge(u, v, INF); } else { bridgePosition[bridgeNumber] = edgeNumber; bridgeCost[bridgeNumber] = w; addEdge(u, v, 1); ++ bridgeNumber; } } memcpy(redge, edge, sizeof(redge)); memcpy(rhead, head, sizeof(rhead)); int minCost = INF, maxPeople = - INF; for(int i=0;i<(1<<bridgeNumber);++i) { memcpy(edge, redge, sizeof(edge)); memcpy(head, rhead, sizeof(head)); int cost = 0; for(int j=0;j<bridgeNumber;++j) { if(i&(1 << j)) { cost += bridgeCost[j]; edge[bridgePosition[j]].flow = INF; } } int people = maxFlow(source, destination); if(people > maxPeople) { maxPeople = people; minCost = cost; } else if(people == maxPeople) { minCost = min(minCost, cost); } } if(maxPeople > 0) { printf("%d %d\n", maxPeople, minCost); } else { printf("Poor Heaven Empire\n"); } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。