POJ 3155最大密度子图裸题(二)
0);head[v]=tol++; } int Q[maxn]; bool bfs(int start,int end){ memset(dep,-1,sizeof(dep)); int front=0,rear=0; dep[start]=0;Q[rear++]=start; while(front!=rear){ int u=Q[front++]; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to;if(dep[v]==-1&&edge[i].cap>0){ Q[rear++]=v,dep[v]=dep[u]+1; if(v==end)return 1; } } } return 0; } double dinic(int s,int t){ int i,top;double res=0; int S[maxn],cur[maxn]; while(bfs(s,t)){ memcpy(cur,head,sizeof(head)); int u=s;top=0; while(1){ if(u==t){ double min=INF;int loc; for(int i=0;i
edge[S[i]].cap) min=edge[S[i]].cap,loc=i; for(int i=0;i
0&&dep[u]+1==dep[edge[i].to])break; if(cur[u]!=-1)S[top++]=cur[u],u=edge[cur[u]].to; else{ if(top==0)break; dep[u]=-1;u=edge[S[--top]^1].to; } } } return res; } int start[1111],end[1111]; double check(double mid){ memset(head,-1,sizeof(head));tol=0; for(int i=1;i<=n;i++)addedge(i,n+m+1,mid); for(int i=1;i<=m;i++){ addedge(0,n+i,1.0); addedge(n+i,start[i],INF); addedge(n+i,end[i],INF); } return m-dinic(0,n+m+1); } int fun(){ char ch;int flag=1,a=0; while(ch=getchar())if((ch>='0'&&ch<='9')||ch=='-')break; if(ch=='-')flag=-1;else a=ch-'0'; while(ch=getchar()){ if(ch>='0'&&ch<='9')a=10*a+ch-'0'; else break; } return flag*a; } int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=m;i++){ start[i]=fun(); end[i]=fun(); } if(!m){ puts("1\n1"); continue; } double l=0,r=m; while(r-l>eps){ double mid=(l+r)/2; double ret=check(mid); if(ret>0)l=mid; else r=mid; } //cout<<"hahha: "<