我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=1325
用二分匹配hungary超时了,郁闷到要死
最大流昨晚建模算错个数,以为出啥问题了。
想了一晚刚才a了
跟前面做的题目一样。
建立一个st-网
s连上x的 y连上t
x->y
注意去掉0-0状态
int mat[MAXN][MAXN],flow[MAXN][MAXN];

int main()
{
    
int n,m,k;
    
int s,t;
    
int nd,x,y;
    
    
while(scanf("%d",&n)){
          
if(n==0)break;
          scanf(
"%d%d",&m,&k);
          memset(mat,
0,sizeof(mat));
          memset(flow,
0,sizeof(flow));
          s
=0,t=n+m-1;
          
for(int i=1;i<=n-1;i++)mat[s][i]=1;
          
for(int i=n;i<=n+m-2;i++)mat[i][t]=1;
    
         
for(int i=0;i<k;i++){
            scanf(
"%d%d%d",&nd,&x,&y);
            
if(x!=0 && y!=0){
             mat[x][y
+n-1]=1;
          }

       }

       printf(
"%d\n",max_flow(n+m,mat,s,t,flow));
       
    }

    
return 0;
}
posted on 2009-02-17 16:43 阅读(1483) 评论(0)  编辑 收藏 引用 所属分类: pku

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