POJ1149 PIGS

绝地灬酷狼 2021-12-20 20:15 155阅读 0赞

题目：[http://poj.org/problem?id=1149][http_poj.org_problem_id_1149]

十分巧妙的构图！连接源点和每个猪圈第一个顾客。之后新来顾客若猪圈相同，就可连在上一个这个猪圈的顾客上！

1.所以用了并查集一样的东西记录谁是顾客链的末尾。并为了最终的末尾与汇点相连而在点上记录需求前缀。

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

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int INF=1e7;
    int n,m,a[1005],head[105],front[1005],xnt=1;
    int s,sc,cnt[105],t,cur[105],mxflow,dfn[105],prs[105];
    bool in[105];
    struct Edge{
        int next,to,cap;
        Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
    }edge[20005];
    queue<int> q;
    void add(int x,int y,int k)
    {
        edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
        edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
    }
    bool bfs()
    {
        while(q.size())q.pop();
        memset(dfn,0,sizeof dfn);
        dfn[0]=1;in[0]=1;q.push(0);
        while(q.size())
        {
            int k=q.front();q.pop();
            in[k]=0;
            for(int i=head[k],v;i;i=edge[i].next)
                if(!dfn[v=edge[i].to]&&edge[i].cap)
                {
                    dfn[v]=dfn[k]+1;
                    q.push(v);
                    if(v==t)return dfn[t];
                }
        }
        return dfn[t];
    }
    int dinic(int cr,int flow)
    {
        if(cr==t)return flow;
        int used=0;
        for(int& i=cur[cr],v;i;i=edge[i].next)
            if(dfn[v=edge[i].to]==dfn[cr]+1)
            {
                int tmp=dinic(v,min(flow-used,edge[i].cap));
                if(!tmp)dfn[v]=0;
                used+=tmp;
                edge[i].cap-=tmp;
                edge[i^1].cap+=tmp;
                if(used==flow)break;
            }
    //    printf("cr=%d flow=%d used=%d\n",cr,flow,used);
        return used;
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        t=n+1;
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
    //        printf("i=%d\n",i);
            scanf("%d",&s);
            for(int j=1;j<=s;j++)
            {
                scanf("%d",&sc);
                if(front[sc+n])
                {
                    add(front[sc+n],i,INF);
                    cnt[i]+=cnt[front[sc+n]];
                    cnt[front[sc+n]]=0;
    //                printf(" +cnt[%d]\n",front[sc+n]);
                }
                else
                {
                    if(!prs[i])add(front[sc+n],i,a[sc]),prs[i]=xnt-1;
                    else edge[prs[i]].cap+=a[sc];
                }
                front[sc+n]=i;
            }
            scanf("%d",&sc);cnt[i]+=sc;
    //        for(int j=1;j<=m;j++)
    //            printf(" j=%d front[j]=%d\n",j,front[j+n]);
    //        printf(" cnt[i]=%d\n",cnt[i]);
        }
        for(int i=1;i<=n;i++)
            if(cnt[i])add(i,t,cnt[i]);
    //    for(int i=head[0];i;i=edge[i].next)
    //        printf("to=%d w=%d\n",edge[i].to,edge[i].cap);
        while(bfs())
        {
            memcpy(cur,head,sizeof head);
            mxflow+=dinic(0,INF);
        }
        printf("%d",mxflow);
        return 0;
    }

Code \#1

2.发现上面不对：1)不能用并查集，因为当那个顾客没有访问当前顾客的猪圈时，当前顾客就与他无关，不能连在他身上；故不能从猪圈开始找最新的front；

2)不能在点上记录需求。这样若一个点有多个出度的时候该怎么办？

所以尝试把顾客点拆开，记录负边权（容量）。然后发现负容量根本弄不了。

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

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int INF=1e7;
    int n,m,a[1005],head[105],front[1005],xnt=1;
    int s,sc,t,cur[105],mxflow,dfn[105],prs[105];
    bool in[105],tail[105];
    struct Edge{
        int next,to,cap;
        Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
    }edge[20205];
    queue<int> q;
    void add(int x,int y,int k)
    {
        edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
        edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
    }
    bool bfs()
    {
        while(q.size())q.pop();
        memset(dfn,0,sizeof dfn);
        dfn[0]=1;in[0]=1;q.push(0);
        while(q.size())
        {
            int k=q.front();q.pop();
            in[k]=0;
            for(int i=head[k],v;i;i=edge[i].next)
                if(!dfn[v=edge[i].to]&&edge[i].cap)
                {
                    dfn[v]=dfn[k]+1;
                    q.push(v);
                    if(v==t)return dfn[t];
                }
        }
        return dfn[t];
    }
    int dinic(int cr,int flow)
    {
        if(cr==t)return flow;
        int used=0;
        for(int& i=cur[cr],v;i;i=edge[i].next)
            if(dfn[v=edge[i].to]==dfn[cr]+1)
            {
                int tmp=dinic(v,min(flow-used,edge[i].cap));
                if(!tmp)dfn[v]=0;
                used+=tmp;
                edge[i].cap-=tmp;
                edge[i^1].cap+=tmp;
                if(used==flow)break;
            }
    //    printf("cr=%d flow=%d used=%d\n",cr,flow,used);
        return used;
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        t=n+n+1;
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
    //        printf("i=%d\n",i);
            scanf("%d",&s);
            for(int j=1;j<=s;j++)
            {
                scanf("%d",&sc);
                int k=front[sc+n];
                if(k)
                {
                    add(k,i,INF);
                    tail[k-n]=0;
                }
                else
                {
                    if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
                    else edge[prs[i]].cap+=a[sc];
                }
                front[sc+n]=n+i;
            }
            scanf("%d",&sc);
            add(i,n+i,-sc);
            tail[i]=1;
    //        for(int j=1;j<=m;j++)
    //            printf(" j=%d front[j]=%d\n",j,front[j+n]);
    //        printf(" cnt[i]=%d\n",cnt[i]);
        }
        for(int i=1;i<=n;i++)
            if(tail[i])add(i+n,t,INF);
    //    for(int i=head[0];i;i=edge[i].next)
    //        printf("to=%d w=%d\n",edge[i].to,edge[i].cap);
        while(bfs())
        {
            memcpy(cur,head,sizeof head);
            mxflow+=dinic(0,INF);
        }
        printf("%d",mxflow);
        return 0;
    }

Code \#2

3.就去看了PPT上的题解。——原来每个顾客点都要和汇点相连！！！这样真是十分合理！意义上也很合适！

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

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int INF=1e7;
    int n,m,a[1005],head[105],front[1005],xnt=1;
    int s,sc,t,cur[105],mxflow,dfn[105],prs[105];
    struct Edge{
        int next,to,cap;
        Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
    }edge[200205];
    queue<int> q;
    void add(int x,int y,int k)
    {
        edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
        edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
    }
    bool bfs()
    {
        while(q.size())q.pop();
        memset(dfn,0,sizeof dfn);
        dfn[0]=1;q.push(0);
        while(q.size())
        {
            int k=q.front();q.pop();
            for(int i=head[k],v;i;i=edge[i].next)
                if(!dfn[v=edge[i].to]&&edge[i].cap)
                {
                    dfn[v]=dfn[k]+1;
                    q.push(v);
                    if(v==t)return dfn[t];
                }
        }
        return dfn[t];
    }
    int dinic(int cr,int flow)
    {
        if(cr==t)return flow;
        int used=0;
        for(int& i=cur[cr],v;i;i=edge[i].next)
            if(dfn[v=edge[i].to]==dfn[cr]+1)
            {
                int tmp=dinic(v,min(flow-used,edge[i].cap));
                if(!tmp)dfn[v]=0;
                used+=tmp;
                edge[i].cap-=tmp;
                edge[i^1].cap+=tmp;
                if(used==flow)break;
            }
        return used;
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        t=n+1;
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s);
            for(int j=1;j<=s;j++)
            {
                scanf("%d",&sc);
                int k=front[sc];
                if(k)add(k,i,INF);
                else
                {
                    if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
                    else edge[prs[i]].cap+=a[sc];
                }
                front[sc]=i;
            }
            scanf("%d",&sc);
            add(i,t,sc);/每个人都连边！！！！！ 
        }
        while(bfs())
        {
            memcpy(cur,head,sizeof head);
            mxflow+=dinic(0,INF);
        }
        printf("%d",mxflow);
        return 0;
    }

Code \#3

4.上边的代码会TLE？！

就去看了Zinn的写法。发现顾客间连边的时候可以去重。虽然没把它当回事但还是写上了。顺便改改自己的数组大小。

然后出现了奇奇怪怪的错误！为什么memcpy cur以head的时候会把dfn清零？之类的。

终于发现是自己改数组大小的时候把cur和head改成不一样大的了。真恐怖。改成一样大的。就行了！

终于A了！去重真的很重要！本来这道题朴素似乎就是会TLE+MLE的，所以多出一堆重复的边可能很费劲。

——网络最大流对边数的多少很敏感吗？还是这里不去重的话会多出很多边呢？

总之A了真是太好了。虽然从头到尾都在借鉴别人。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int INF=1e7;
    int n,m,a[1005],head[150],front[1005],xnt=1;
    int s,sc,t,cur[150],mxflow,dfn[150],prs[150];
    bool be[150][150];
    struct Edge{
        int next,to,cap;
        Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
    }edge[25005];
    queue<int> q;
    void add(int x,int y,int k)
    {
        edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
        edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
    }
    bool bfs()
    {
        while(q.size())q.pop();
        memset(dfn,0,sizeof dfn);
        dfn[0]=1;q.push(0);
        while(q.size())
        {
            int k=q.front();q.pop();
            for(int i=head[k],v;i;i=edge[i].next)
                if(!dfn[v=edge[i].to]&&edge[i].cap)
                {
                    dfn[v]=dfn[k]+1;
                    q.push(v);
                    if(v==t)return dfn[t];
                }
        }
        return dfn[t];
    }
    int dinic(int cr,int flow)
    {
        if(cr==t)return flow;
        int used=0;
        for(int& i=cur[cr],v;i;i=edge[i].next)
            if(dfn[v=edge[i].to]==dfn[cr]+1&&edge[i].cap)
            {
                int tmp=dinic(v,min(flow-used,edge[i].cap));
                if(!tmp)dfn[v]=0;
                used+=tmp;
                edge[i].cap-=tmp;
                edge[i^1].cap+=tmp;
                if(used==flow)return used;
            }
        return used;
    }
    int main()
    {
        scanf("%d%d",&m,&n);
        t=n+1;
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&s);
            for(int j=1;j<=s;j++)
            {
                scanf("%d",&sc);
                int k=front[sc];
                if(k&&!be[k][i])add(k,i,INF),be[k][i]=1;/ 
                else
                {
                    if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
                    else edge[prs[i]].cap+=a[sc];
                }
                front[sc]=i;
            }
            scanf("%d",&sc);
            add(i,t,sc);/每个人都连边！！！！！ 
        }
        while(bfs())
        {
            memcpy(cur,head,sizeof head);//cur和head的数组大小必须一样！！！ 
            mxflow+=dinic(0,INF);
        }
        printf("%d",mxflow);
        return 0;
    }

转载于:https://www.cnblogs.com/Narh/p/8620723.html

[http_poj.org_problem_id_1149]: http://poj.org/problem?id=1149
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/9f3648c0e88b4fa8a3c703f49fbe13fb.png