POJ1149 PIGS

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

题目：http://poj.org/problem?id=1149

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

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int INF=1e7;
  7. int n,m,a[1005],head[105],front[1005],xnt=1;
  8. int s,sc,cnt[105],t,cur[105],mxflow,dfn[105],prs[105];
  9. bool in[105];
  10. struct Edge{
  11.     int next,to,cap;
  12.     Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
  13. }edge[20005];
  14. queue<int> q;
  15. void add(int x,int y,int k)
  16. {
  17.     edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
  18.     edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
  19. }
  20. bool bfs()
  21. {
  22.     while(q.size())q.pop();
  23.     memset(dfn,0,sizeof dfn);
  24.     dfn[0]=1;in[0]=1;q.push(0);
  25.     while(q.size())
  26.     {
  27.         int k=q.front();q.pop();
  28.         in[k]=0;
  29.         for(int i=head[k],v;i;i=edge[i].next)
  30.             if(!dfn[v=edge[i].to]&&edge[i].cap)
  31.             {
  32.                 dfn[v]=dfn[k]+1;
  33.                 q.push(v);
  34.                 if(v==t)return dfn[t];
  35.             }
  36.     }
  37.     return dfn[t];
  38. }
  39. int dinic(int cr,int flow)
  40. {
  41.     if(cr==t)return flow;
  42.     int used=0;
  43.     for(int& i=cur[cr],v;i;i=edge[i].next)
  44.         if(dfn[v=edge[i].to]==dfn[cr]+1)
  45.         {
  46.             int tmp=dinic(v,min(flow-used,edge[i].cap));
  47.             if(!tmp)dfn[v]=0;
  48.             used+=tmp;
  49.             edge[i].cap-=tmp;
  50.             edge[i^1].cap+=tmp;
  51.             if(used==flow)break;
  52.         }
  53. //    printf("cr=%d flow=%d used=%d\n",cr,flow,used);
  54.     return used;
  55. }
  56. int main()
  57. {
  58.     scanf("%d%d",&m,&n);
  59.     t=n+1;
  60.     for(int i=1;i<=m;i++)scanf("%d",&a[i]);
  61.     for(int i=1;i<=n;i++)
  62.     {
  63. //        printf("i=%d\n",i);
  64.         scanf("%d",&s);
  65.         for(int j=1;j<=s;j++)
  66.         {
  67.             scanf("%d",&sc);
  68.             if(front[sc+n])
  69.             {
  70.                 add(front[sc+n],i,INF);
  71.                 cnt[i]+=cnt[front[sc+n]];
  72.                 cnt[front[sc+n]]=0;
  73. //                printf(" +cnt[%d]\n",front[sc+n]);
  74.             }
  75.             else
  76.             {
  77.                 if(!prs[i])add(front[sc+n],i,a[sc]),prs[i]=xnt-1;
  78.                 else edge[prs[i]].cap+=a[sc];
  79.             }
  80.             front[sc+n]=i;
  81.         }
  82.         scanf("%d",&sc);cnt[i]+=sc;
  83. //        for(int j=1;j<=m;j++)
  84. //            printf(" j=%d front[j]=%d\n",j,front[j+n]);
  85. //        printf(" cnt[i]=%d\n",cnt[i]);
  86.     }
  87.     for(int i=1;i<=n;i++)
  88.         if(cnt[i])add(i,t,cnt[i]);
  89. //    for(int i=head[0];i;i=edge[i].next)
  90. //        printf("to=%d w=%d\n",edge[i].to,edge[i].cap);
  91.     while(bfs())
  92.     {
  93.         memcpy(cur,head,sizeof head);
  94.         mxflow+=dinic(0,INF);
  95.     }
  96.     printf("%d",mxflow);
  97.     return 0;
  98. }

Code #1

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

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

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int INF=1e7;
  7. int n,m,a[1005],head[105],front[1005],xnt=1;
  8. int s,sc,t,cur[105],mxflow,dfn[105],prs[105];
  9. bool in[105],tail[105];
  10. struct Edge{
  11.     int next,to,cap;
  12.     Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
  13. }edge[20205];
  14. queue<int> q;
  15. void add(int x,int y,int k)
  16. {
  17.     edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
  18.     edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
  19. }
  20. bool bfs()
  21. {
  22.     while(q.size())q.pop();
  23.     memset(dfn,0,sizeof dfn);
  24.     dfn[0]=1;in[0]=1;q.push(0);
  25.     while(q.size())
  26.     {
  27.         int k=q.front();q.pop();
  28.         in[k]=0;
  29.         for(int i=head[k],v;i;i=edge[i].next)
  30.             if(!dfn[v=edge[i].to]&&edge[i].cap)
  31.             {
  32.                 dfn[v]=dfn[k]+1;
  33.                 q.push(v);
  34.                 if(v==t)return dfn[t];
  35.             }
  36.     }
  37.     return dfn[t];
  38. }
  39. int dinic(int cr,int flow)
  40. {
  41.     if(cr==t)return flow;
  42.     int used=0;
  43.     for(int& i=cur[cr],v;i;i=edge[i].next)
  44.         if(dfn[v=edge[i].to]==dfn[cr]+1)
  45.         {
  46.             int tmp=dinic(v,min(flow-used,edge[i].cap));
  47.             if(!tmp)dfn[v]=0;
  48.             used+=tmp;
  49.             edge[i].cap-=tmp;
  50.             edge[i^1].cap+=tmp;
  51.             if(used==flow)break;
  52.         }
  53. //    printf("cr=%d flow=%d used=%d\n",cr,flow,used);
  54.     return used;
  55. }
  56. int main()
  57. {
  58.     scanf("%d%d",&m,&n);
  59.     t=n+n+1;
  60.     for(int i=1;i<=m;i++)scanf("%d",&a[i]);
  61.     for(int i=1;i<=n;i++)
  62.     {
  63. //        printf("i=%d\n",i);
  64.         scanf("%d",&s);
  65.         for(int j=1;j<=s;j++)
  66.         {
  67.             scanf("%d",&sc);
  68.             int k=front[sc+n];
  69.             if(k)
  70.             {
  71.                 add(k,i,INF);
  72.                 tail[k-n]=0;
  73.             }
  74.             else
  75.             {
  76.                 if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
  77.                 else edge[prs[i]].cap+=a[sc];
  78.             }
  79.             front[sc+n]=n+i;
  80.         }
  81.         scanf("%d",&sc);
  82.         add(i,n+i,-sc);
  83.         tail[i]=1;
  84. //        for(int j=1;j<=m;j++)
  85. //            printf(" j=%d front[j]=%d\n",j,front[j+n]);
  86. //        printf(" cnt[i]=%d\n",cnt[i]);
  87.     }
  88.     for(int i=1;i<=n;i++)
  89.         if(tail[i])add(i+n,t,INF);
  90. //    for(int i=head[0];i;i=edge[i].next)
  91. //        printf("to=%d w=%d\n",edge[i].to,edge[i].cap);
  92.     while(bfs())
  93.     {
  94.         memcpy(cur,head,sizeof head);
  95.         mxflow+=dinic(0,INF);
  96.     }
  97.     printf("%d",mxflow);
  98.     return 0;
  99. }

Code #2

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

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int INF=1e7;
  7. int n,m,a[1005],head[105],front[1005],xnt=1;
  8. int s,sc,t,cur[105],mxflow,dfn[105],prs[105];
  9. struct Edge{
  10.     int next,to,cap;
  11.     Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
  12. }edge[200205];
  13. queue<int> q;
  14. void add(int x,int y,int k)
  15. {
  16.     edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
  17.     edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
  18. }
  19. bool bfs()
  20. {
  21.     while(q.size())q.pop();
  22.     memset(dfn,0,sizeof dfn);
  23.     dfn[0]=1;q.push(0);
  24.     while(q.size())
  25.     {
  26.         int k=q.front();q.pop();
  27.         for(int i=head[k],v;i;i=edge[i].next)
  28.             if(!dfn[v=edge[i].to]&&edge[i].cap)
  29.             {
  30.                 dfn[v]=dfn[k]+1;
  31.                 q.push(v);
  32.                 if(v==t)return dfn[t];
  33.             }
  34.     }
  35.     return dfn[t];
  36. }
  37. int dinic(int cr,int flow)
  38. {
  39.     if(cr==t)return flow;
  40.     int used=0;
  41.     for(int& i=cur[cr],v;i;i=edge[i].next)
  42.         if(dfn[v=edge[i].to]==dfn[cr]+1)
  43.         {
  44.             int tmp=dinic(v,min(flow-used,edge[i].cap));
  45.             if(!tmp)dfn[v]=0;
  46.             used+=tmp;
  47.             edge[i].cap-=tmp;
  48.             edge[i^1].cap+=tmp;
  49.             if(used==flow)break;
  50.         }
  51.     return used;
  52. }
  53. int main()
  54. {
  55.     scanf("%d%d",&m,&n);
  56.     t=n+1;
  57.     for(int i=1;i<=m;i++)scanf("%d",&a[i]);
  58.     for(int i=1;i<=n;i++)
  59.     {
  60.         scanf("%d",&s);
  61.         for(int j=1;j<=s;j++)
  62.         {
  63.             scanf("%d",&sc);
  64.             int k=front[sc];
  65.             if(k)add(k,i,INF);
  66.             else
  67.             {
  68.                 if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
  69.                 else edge[prs[i]].cap+=a[sc];
  70.             }
  71.             front[sc]=i;
  72.         }
  73.         scanf("%d",&sc);
  74.         add(i,t,sc);/每个人都连边！！！！！ 
  75.     }
  76.     while(bfs())
  77.     {
  78.         memcpy(cur,head,sizeof head);
  79.         mxflow+=dinic(0,INF);
  80.     }
  81.     printf("%d",mxflow);
  82.     return 0;
  83. }

Code #3

4.上边的代码会TLE？！

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

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

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

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

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

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

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<queue>
  5. using namespace std;
  6. const int INF=1e7;
  7. int n,m,a[1005],head[150],front[1005],xnt=1;
  8. int s,sc,t,cur[150],mxflow,dfn[150],prs[150];
  9. bool be[150][150];
  10. struct Edge{
  11.     int next,to,cap;
  12.     Edge(int n=0,int t=0,int c=0):next(n),to(t),cap(c) {}
  13. }edge[25005];
  14. queue<int> q;
  15. void add(int x,int y,int k)
  16. {
  17.     edge[++xnt]=Edge(head[x],y,k);head[x]=xnt;
  18.     edge[++xnt]=Edge(head[y],x,0);head[y]=xnt;
  19. }
  20. bool bfs()
  21. {
  22.     while(q.size())q.pop();
  23.     memset(dfn,0,sizeof dfn);
  24.     dfn[0]=1;q.push(0);
  25.     while(q.size())
  26.     {
  27.         int k=q.front();q.pop();
  28.         for(int i=head[k],v;i;i=edge[i].next)
  29.             if(!dfn[v=edge[i].to]&&edge[i].cap)
  30.             {
  31.                 dfn[v]=dfn[k]+1;
  32.                 q.push(v);
  33.                 if(v==t)return dfn[t];
  34.             }
  35.     }
  36.     return dfn[t];
  37. }
  38. int dinic(int cr,int flow)
  39. {
  40.     if(cr==t)return flow;
  41.     int used=0;
  42.     for(int& i=cur[cr],v;i;i=edge[i].next)
  43.         if(dfn[v=edge[i].to]==dfn[cr]+1&&edge[i].cap)
  44.         {
  45.             int tmp=dinic(v,min(flow-used,edge[i].cap));
  46.             if(!tmp)dfn[v]=0;
  47.             used+=tmp;
  48.             edge[i].cap-=tmp;
  49.             edge[i^1].cap+=tmp;
  50.             if(used==flow)return used;
  51.         }
  52.     return used;
  53. }
  54. int main()
  55. {
  56.     scanf("%d%d",&m,&n);
  57.     t=n+1;
  58.     for(int i=1;i<=m;i++)scanf("%d",&a[i]);
  59.     for(int i=1;i<=n;i++)
  60.     {
  61.         scanf("%d",&s);
  62.         for(int j=1;j<=s;j++)
  63.         {
  64.             scanf("%d",&sc);
  65.             int k=front[sc];
  66.             if(k&&!be[k][i])add(k,i,INF),be[k][i]=1;/ 
  67.             else
  68.             {
  69.                 if(!prs[i])add(k,i,a[sc]),prs[i]=xnt-1;
  70.                 else edge[prs[i]].cap+=a[sc];
  71.             }
  72.             front[sc]=i;
  73.         }
  74.         scanf("%d",&sc);
  75.         add(i,t,sc);/每个人都连边！！！！！ 
  76.     }
  77.     while(bfs())
  78.     {
  79.         memcpy(cur,head,sizeof head);//cur和head的数组大小必须一样！！！ 
  80.         mxflow+=dinic(0,INF);
  81.     }
  82.     printf("%d",mxflow);
  83.     return 0;
  84. }

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

发表评论

表情：
评论列表 （有 0 条评论，313人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Pig初步

    是一个基于Hadoop的大规模数据分析工具，它提供的SQL-LIKE语言叫Pig Latin，该语言的编译器会把类SQL的数据分析请求转换为一系列经过优化处理的MapReduc

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 350 阅读

    相关 Pig Hive对比

    Pig Latin：数据流编程语言 一个Pig Latin程序是相对于输入的一步步操作。其中每一步都是对数据的一个简单的变换。 用Pig Latin编程更像在RDBMS中“

    你的名字你的名字/ 0 赞/ 293 阅读