我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=1149
网络流
挺不错的,刚开始想直接把pig-houses搞到图里面去,发现那样的话st网络会变成m+n+2<=1000+100+2 太恐怖了
上网查了一下,学会了简化建图,把猪圈简化掉,这样不会改变约束条件

注意顾客的先后条件

主要是建图,看不懂的话可以和我交流

推荐帖子:http://imlazy.ycool.com/post.2059102.html


#include<iostream>
using namespace std;

#define MAXN 104
#define MAXM 1001
//求网络最大流,邻接阵形式
//返回最大流量,flow返回每条边的流量
//传入网络节点数n,容量mat,源点source,汇点sink
// 测试过了
#define inf 1000000000

int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
    
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
    
if (source==sink) return inf;
    
for (i=0;i<n;i++)
        
for (j=0;j<n;flow[i][j++]=0);
    
for (;;){
        
for (i=0;i<n;pre[i++]=0);
        pre[t
=source]=source+1,d[t]=inf;
        
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
            
for (i=0;i<n;i++)
                
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
                    pre[que[q
++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
                
else if (!pre[i]&&(j=flow[i][t]))
                    pre[que[q
++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
        
if (!pre[sink]) break;
        
for (i=sink;i!=source;)
            
if (pre[i]>0)
                flow[pre[i]
-1][i]+=d[sink],i=pre[i]-1;
            
else
                flow[i][
-pre[i]-1]-=d[sink],i=-pre[i]-1;
    }

    
for (j=i=0;i<n;j+=flow[source][i++]);
    
return j;
}


int mat[MAXN][MAXN],flow[MAXN][MAXN];
int h[MAXM];
int hash[MAXM];

int main()
{  
    
int m,n,s,t;
    
int k,tmp,b;
    
int c=0;
      memset(mat,
0,sizeof(mat));
      memset(h,
0,sizeof(h));
      memset(hash,
0,sizeof(hash));
      scanf(
"%d%d",&m,&n);
      
      s
=0;t=n+1;//总共n+2个点 
      
      
for(int i=1;i<=m;i++){
              scanf(
"%d",&h[i]);
              
//mat[s][i]=h[i]; 
              c+=h[i];
      }

      
for(int i=1;i<=n;i++){
            scanf(
"%d",&k);
            
for(int j=0;j<k;j++){
               scanf(
"%d",&tmp);
               
               
if(hash[tmp]==0){
                  mat[s][i]
+=h[tmp];
                  hash[tmp]
=i;               
               }

               
else{
                  mat[hash[tmp]][i]
=c;
                 
// hash[tmp]=i;
               }

            
            }

            scanf(
"%d",&b);
            mat[i][t]
=b;
      }

      printf(
"%d\n",max_flow(n+2,mat,s,t,flow));
     
// system("pause");
    return 0;
}



posted on 2009-02-25 21:46 阅读(1634) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理