首页 > 代码库 > 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;}
View Code

 

poj 1273.PIG 解题报告