Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
TLE,TLE,TLE......二分加最大流求解狂超时,难道是我的最大流算法很烂?????不解不解(有代码) 望大牛看看啊。 TLE代码: #include<stdio.h> #include<string.h> #include<math.h> #define MAX 1510 int con[MAX][MAX],cx[MAX][MAX]; int n,m; char ch[10000]; int s,t,queue[MAX],head,tail,pre[MAX],visit[MAX]; bool findroad() { int i,k; memset(visit,0,sizeof(visit)); head=tail=0; queue[tail++]=s; pre[s] = -1; while(tail > head){ k = queue[head++]; for(i = 0; i <=n+m+1; i++) if(!visit[i] && con[k][i] > 0){ pre[i] = k; visit[i] = 1; if(i == t) return true; queue[tail++] = i; } } return false; } int Maxflow() { int j,maxflow = 0;; while(findroad()){ int min = 0x7FFFFFFF; for(j = t; j != s; j = pre[j]) if(min > con[pre[j]][j]) min = con[pre[j]][j]; maxflow += min; for(j = t; j != s; j = pre[j]){ con[pre[j]][j] -= min; con[j][pre[j]] += min; } } return maxflow; } int main() { int i,a[5],j,k,d,f,ss; while(scanf("%d%d",&n,&m)!=EOF) { getchar(); if(n==0&&m==0)break; memset(con,0,sizeof(con)); for(i=1;i<=n;i++) { f=0; gets(ch); for(j=0;j<=strlen(ch);j++) { d=0; if(ch[j]>='0'&&ch[j]<='9') a[f++]=ch[j]-'0'; else { if(f!=0) { for(k=f-1;k>=0;k--) d+=(int)(pow(10.0,f-1-k))*a[k]; con[i][d+n+1]=1; f=0; }//if t }//else }//for j }//for i for(i=1;i<=n;i++) con[0][i]=1; s=0; t=m+n+1; int l=1,r=n,mid; for(i=0;i<=m+n;i++) for(j=0;j<=m+n;j++) cx[i][j]=con[i][j]; while(l<r) { for(i=0;i<=m+n;i++) for(j=0;j<=m+n;j++) con[i][j]=cx[i][j]; mid=(l+r)/2; for(i=n+1;i<=m+n;i++) con[i][m+n+1]=mid; ss=Maxflow(); if(ss==n)r=mid; else l=mid+1; } printf("%d\n",mid+1); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator