poj 1273.PIG （最大流）

深藏阁楼爱情的钟 2022-01-05 11:51 196阅读 0赞

网络流

关键是建图，思路在代码里

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

/*
          最大流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;
    }

转载于:https://www.cnblogs.com/keam37/p/3973519.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211229/ffaf0fd9095b436b8b64155ea3869fb5.png