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