首页 > 代码库 > poj 1273.PIG 解题报告
poj 1273.PIG 解题报告
网络流
关键是建图,思路在代码里
/* 最大流SAP 邻接表 思路:基本源于FF方法,给每个顶点设定层次标号,和允许弧。 优化: 1、当前弧优化(重要)。 1、每找到以条增广路回退到断点(常数优化)。 2、层次出现断层,无法得到新流(重要)。 时间复杂度(m*n^2)*/#include <iostream>#include <cstdio>#include <cstring>#define ms(a,b) memset(a,b,sizeof a)using namespace std;const int INF = 500;int G[INF][INF];struct node { int v, c, next;} edge[INF*INF*4];int pHead[INF*INF], SS, ST, nCnt;void addEdge (int u, int v, int c) { edge[++nCnt].v = v; edge[nCnt].c = c, edge[nCnt].next = pHead[u]; pHead[u] = nCnt; edge[++nCnt].v = u; edge[nCnt].c = 0, edge[nCnt].next = pHead[v]; pHead[v] = nCnt;}int SAP (int pStart, int pEnd, int N) { int numh[INF], h[INF], curEdge[INF], pre[INF]; int cur_flow, flow_ans = 0, u, neck, i, tmp; ms (h, 0); ms (numh, 0); ms (pre, -1); for (i = 0; i <= N; i++) curEdge[i] = pHead[i]; numh[0] = N; u = pStart; while (h[pStart] <= N) { if (u == pEnd) { cur_flow = 1e9; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) if (cur_flow > edge[curEdge[i]].c) neck = i, cur_flow = edge[curEdge[i]].c; for (i = pStart; i != pEnd; i = edge[curEdge[i]].v) { tmp = curEdge[i]; edge[tmp].c -= cur_flow, edge[tmp ^ 1].c += cur_flow; } flow_ans += cur_flow; u = neck; } for ( i = curEdge[u]; i != 0; i = edge[i].next) if (edge[i].c && h[u] == h[edge[i].v] + 1) break; if (i != 0) { curEdge[u] = i, pre[edge[i].v] = u; u = edge[i].v; } else { if (0 == --numh[h[u]]) continue; curEdge[u] = pHead[u]; for (tmp = N, i = pHead[u]; i != 0; i = edge[i].next) if (edge[i].c) tmp = min (tmp, h[edge[i].v]); h[u] = tmp + 1; ++numh[h[u]]; if (u != pStart) u = pre[u]; } } return flow_ans;}/* poj1149 最大流 建图: 每个顾客为一个节点,从源点到每个猪圈的第一个顾客连接一条容量为猪圈猪数目的边 从第一个顾客到同一个猪圈的其它顾客连一条容量无限的边 每个顾客到汇点的边的容量为他最大买的数量*/int k, c, m, n,x,y,z;int vis[INF],sum[INF];void solve(){ nCnt=1; for(int i=1;i<=ST;i++) for(int j=1;j<=ST;j++){ if(G[i][j]) addEdge(i,j,G[i][j]); } int ans=SAP(SS,ST,ST); printf("%d\n",ans);}int main() { /* 先用邻接矩阵统计容量,再用前向星存边,表头在pHead[],初始化nCnt=1 SS,ST分别为源点和汇点 */ scanf("%d %d",&m,&n); SS=n+1,ST=n+2; for(int i=1;i<=m;i++) scanf("%d",&sum[i]); for(int i=1;i<=n;i++){ scanf("%d",&k); for(int j=1;j<=k;j++){ scanf("%d",&x); if(!vis[x]){ G[SS][i]+=sum[x]; vis[x]=i; } else{ G[vis[x]][i]=0xffff; } } scanf("%d",&k); G[i][ST]=k; } solve(); return 0;}
poj 1273.PIG 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。