Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

pku 1149 PIGS

#include <iostream>
using namespace std;
#define N 105

int Edmonds_Karp(int g[][N],int n,int s,int t,int f[][N]) 

    
int i,j,k,c,head,tail,flow=0 ; 
    
int r[N][N]; 
    
int prev[N],visit[N],q[N]; 
    
for(i=s;i<=t;i++)for(j=s;j<=t;j++
    

        f[i][j]
=0 ; 
        r[i][j]
=g[i][j]; 
    }
 
    
while(1
    

        head
=tail=0 ; 
        memset(visit,
0,sizeof(visit)); 
        q[tail
++]=s ; 
        prev[s]
=-1 ; 
        visit[s]
=1 ; 
        
while(head<tail) 
        

            k
=q[head++]; 
            
for(i=s;i<=t;i++//注意修改
                if(!visit[i]&&r[k][i]>0
                

                    visit[i]
=1 ; 
                    prev[i]
=k ; 
                    
if(i==t)goto next ; 
                    q[tail
++]=i ; 
                }
 
        }
 
        next : 
        
if(!visit[t])break ; 
        
for(c=INT_MAX,j=t;j!=s;j=i) 
        

            i
=prev[j]; 
            
if(c>r[i][j])c=r[i][j]; 
        }
 
        
for(j=t;j!=s;j=i) 
        

            i
=prev[j]; 
            f[i][j]
+=c ; 
            f[j][i]
=-f[i][j]; 
            r[i][j]
=g[i][j]-f[i][j]; 
            r[j][i]
=g[j][i]-f[j][i]; 
        }
 
        flow
+=c ; 
    }
 
    
return flow ; 
}


int g[N][N]; 
int f[N][N];

int main() 

    
int i,j,k,x; 
    
int n,m; 
    
int s,t; 
    scanf(
"%d%d",&m,&n);
    
int num[1005];
    
int ff[1005];
    
for(i=1;i<=m;i++)
    
{
        scanf(
"%d",&num[i]);
        ff[i]
=0;
    }

    
for(j=1;j<=n;j++)
    
{
        
int temp;
        scanf(
"%d",&temp);
        
for(k=0;k<temp;k++)
        
{
           scanf(
"%d",&x);
           
if(ff[x]==0)
           
{
            g[
0][j]+=num[x];
            ff[x]
=j;
           }

           
else {g[ff[x]][j]=INT_MAX;ff[x]=j;}
        }

        scanf(
"%d",&temp);
        g[j][n
+1]=temp;
    }

    s
=0;t=n+1;
    printf(
"%d\n",Edmonds_Karp(g,n,s,t,f)); 
    
return 0
}

posted on 2009-08-16 21:57 Drolca 阅读(134) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理