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
爬 阅读(1508)
评论(0) 编辑 收藏 引用 所属分类:
pku