Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

TLE,TLE,TLE......

Posted by 724548976 at 2009-08-25 16:51:23 on Problem 2289
二分加最大流求解狂超时,难道是我的最大流算法很烂?????不解不解(有代码)
望大牛看看啊。
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator