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

为什么用c就wa,gcc就a了啊???

Posted by zw7840 at 2010-03-25 14:10:46 on Problem 3155
这个是我的程序,请大家找找原因
#include <stdio.h>

#define oo 2000000000
#define turn(i) ((i&1)?(i+1):(i-1))

long e[50005]={0},last[50005]={0},now[5005]={0},totm=0;
double cap[50005]={0},value[5005]={0};

struct case1
{
 long x,y;
}link[5005]={{0,0}};

void addedge(long x,long y,double c)
{
 e[++totm]=y;
 last[totm]=now[x];now[x]=totm;
 cap[totm]=c;
 
 e[++totm]=x;
 last[totm]=now[y];now[y]=totm;
 cap[totm]=0;
}

double sap(long s,long t,long n)
{
 long dist[5005]={0},num;
 long gap[5005]={0},pre[5005]={0},edge[5005]={0};
 long i,j,k,minj=oo;
 double min=oo,maxflow=0;
 
 gap[0]=n;
 for(i=s;dist[s]<n;)
   {
	for(k=now[i];k;k=last[k])
	  {
	   j=e[k];
	   if(dist[j]+1==dist[i]&&cap[k]>0)
	    {
		 edge[j]=k;
	     pre[j]=i;
	     i=j;
	     break;
	    }
	  }
	if(i==t)
	 {
	  for(j=i,min=oo;pre[j];j=pre[j])
	    if(cap[edge[j]]<min)
	     min=cap[edge[j]];
	  maxflow+=min;
	  for(j=i;pre[j];j=pre[j])
	    {
		 cap[edge[j]]-=min;
		 cap[turn(edge[j])]+=min;
		}
	  i=s;
	 }
	else if(!k)
	 {
	  if(gap[dist[i]]==1)
	   return maxflow;
	  gap[dist[i]]--;
	  for(k=now[i],minj=n;k;k=last[k])
	    {
		 j=e[k];
		 if(cap[k]>0&&dist[j]<minj)
		  minj=dist[j];
	    }
	  dist[i]=minj+1;
	  gap[minj+1]++;
	  if(pre[i])
	   i=pre[i];
	 }
   }
   
 return maxflow;
}
long work(long n,long m,double mid)
{
 long i;
 double s=m,maxflow=0;
 
 totm=0;
 now[m+n+1]=now[m+n+2]=0;
 for(i=1;i<=n;i++)
    now[i]=0;
 for(i=1;i<=m;i++)
   {
	now[i+n]=0;
	addedge(n+i,link[i].x,oo);
	addedge(n+i,link[i].y,oo);
	addedge(n+m+1,n+i,1);
   }
 for(i=1;i<=n;i++)
   addedge(i,n+m+2,mid);
   
 maxflow=sap(n+m+1,n+m+2,n+m+2);
 
 if(s-maxflow-0.000001<=0)
  return 1;
 return 0;
}

int main()
{
 long i;
 long n,m,x,y,dui[5005]={0},closed=0,open=0,hash[5005]={0},tot;
 double mid=0,l,r;
 double n1,m1;
 double limit;
 
 //freopen("hard.in","r",stdin);
 //freopen("hard.out","w",stdout);
 
 scanf("%ld%ld",&n,&m);
 n1=n;
 m1=m;
 
 for(i=1;i<=m;i++)
   scanf("%ld%ld",&link[i].x,&link[i].y);
 
 l=1/n1,r=m1;
 limit=1/(n1*n1);
 for(;r-l>=0.000001;)
   {
	mid=(l+r)/2;
    if(work(n,m,mid))
     r=mid;
    else
     l=mid;
   }
 
 if(mid==0)
  {
   printf("1\n1\n");
   return 0;
  }
 
 work(n,m,mid-0.000001);
 
 dui[open++]=n+m+1;
 hash[n+m+1]=1;
 for(;closed<open;)
   {
	x=dui[closed++];
	for(i=now[x];i;i=last[i])
	  {
	   y=e[i];
	   if(cap[i]>0&&hash[y]==0)
	    {
		 hash[y]=1;
		 if(y<=n)
		  tot++;
		 dui[open++]=y;
	    }
	  }
   }
 
 printf("%ld\n",tot);
 for(i=1;i<=n;i++)
   if(hash[i]==1)
    printf("%ld\n",i);
 
 return 0;
}

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