注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

qus的博客

 
 
 

日志

 
 

网络流  

2009-09-13 10:19:02|  分类: 资料 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
#define inf 1000000000
#define MAXN 105
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int pig[1003][MAXN];
int N,M;
int solve()
{
 int pre[MAXN],que[MAXN],d[MAXN];
 int i,j,t=N+2,s=1;
 for(i=0;i<=N+2;i++)
  for(j=0;j<=N+2;j++)
   flow[i][j]=0;
 while(1)
 {
  memset(pre,0,sizeof(pre));
  int head=0,tail=1;
  pre[s]=s;
  d[s]=inf;
  que[0]=s;
  while(head<tail && pre[t]==0)
  {
   i=que[head];
   for(j=1;j<=N+2;j++)
   {
    if(pre[j]==0)
    {
     if(mat[i][j]>flow[i][j])
     {
      pre[j]=i;
      que[tail]=j;
             d[j]=d[i]<mat[i][j]-flow[i][j]?d[i]:mat[i][j]-flow[i][j];
      tail++;
     }
     else if(flow[j][i]>0)
     {
      pre[j]=-i;
      que[tail]=j;
      d[j]=d[i]<flow[j][i]?d[i]:flow[j][i];
      tail++;
     }
    }
   }
   head++;
  }
  if(pre[t]==0){break;}
  i=t;
  while(i!=s)
  {
   j=abs(pre[i]);
   if(pre[i]>0){flow[j][i]+=d[t];}
   else{flow[i][j]-=d[t];}
   i=j;
  }
 }
 int ans=0;
 for(i=1;i<=N+2;i++)
 {
  ans+=flow[s][i];
 }
 printf("%d\n",ans);
 return 0;
}
int main()
{
 int i,j;
 while(scanf("%d%d",&M,&N)!=EOF)
 {
  for(i=1;i<=M;i++)
  {
   scanf("%d",&pig[i][1]);
   pig[i][103]=1;
  }
  for(i=2;i<=N+1;i++)
  {
   int A;
   scanf("%d",&A);
   for(j=1;j<=A;j++)
   {
    int key;
    scanf("%d",&key);
    if(pig[key][103]==1){mat[1][i]+=pig[key][1];}
    int k;
    for(k=pig[key][103];k>=2;k--){
     mat[pig[key][k]][i]=inf;
    }
    pig[key][++pig[key][103]]=i;
   }
   int B;
   scanf("%d",&B);
   mat[i][N+2]=B;
  }
  solve();
 }
}
  评论这张
 
阅读(59)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017