| ||||||||||
| 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