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
爬 閱讀(1534)
評論(0) 編輯 收藏 引用 所屬分類:
pku