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 |
为什么用c就wa,gcc就a了啊???这个是我的程序,请大家找找原因 #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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator