一道最大密度子图的模板题

一道卡精度的神题

二分精度不能太大，网络流精度不能太小 （：

//Achen#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              const int N=12007;typedef double LL;const LL inf=1e18,eps=1e-12; using namespace std;int n,m,num;template
              
               void read(T &x) { char ch=getchar(); x=0; T f=1; while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar(); if(ch=='-') f=-1,ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;}struct edge{ int from,to,nx; LL cap,flow; edge(){} edge(int from,int to,LL cap,LL flow,int nx):from(from),to(to),cap(cap),flow(flow),nx(nx){}}e[N];int ecnt=1,fir[N],dd[N];void add(int u,int v,LL cap) { e[++ecnt]=edge(u,v,cap,0,fir[u]); fir[u]=ecnt; e[++ecnt]=edge(v,u,0,0,fir[v]); fir[v]=ecnt;}queue
               
                que;int c[N],d[N],cur[N],p[N];void bfs(int s,int t) { for(int i=0;i<=num;i++) d[i]=num,c[i]=0; que.push(t); d[t]=0; while(!que.empty()) { int x=que.front(); que.pop(); for(int i=fir[x];i;i=e[i].nx) { int y=e[i].to; if(d[y]==num&&e[i].cap==0) { d[y]=d[x]+1; que.push(y); } } } }LL cal(int s,int t) { LL fl=inf; for(int i=t;i!=s;i=e[p[i]].from) fl=min(fl,e[p[i]].cap-e[p[i]].flow); for(int i=t;i!=s;i=e[p[i]].from) { if(p[i]==886||((p[i]^1)==886)) { int debug=1; } e[p[i]].flow=e[p[i]].flow+fl, e[p[i]^1].flow-=fl; } return fl;}LL ISAP(int s,int t) { bfs(s,t); LL res=0; for(int i=1;i<=num;i++) c[d[i]]++,cur[i]=fir[i]; for(int x=s;d[x]
                
                 =eps) { vis[e[i].to]=1; ansnum++; dfs(e[i].to); }}int ee[N][2];int ck(LL mid,int o) { int s=n+1,t=n+2,res=0; num=t; ecnt=1; memset(fir,0,sizeof(fir)); for(int i=1;i<=m;i++) { add(ee[i][0],ee[i][1],1); add(ee[i][1],ee[i][0],1); } for(int i=1;i<=n;i++) { add(s,i,(LL)m); add(i,t,(LL)m+2.0*mid-dd[i]); } if(((LL)n*m-ISAP(s,t))/2.0>=eps) res=1; if(o==1) { memset(vis,0,sizeof(vis)); vis[s]=1; dfs(s); } return res;}int main() { while(scanf("%d%d",&n,&m)==2) { if( m == 0 ) { printf("1\n1\n") ; continue ; } memset(dd,0,sizeof(dd)); for(int i=1;i<=m;i++) { read(ee[i][0]); read(ee[i][1]); dd[ee[i][0]]++; dd[ee[i][1]]++; } LL l=0,r=m; while(l+1e-5<=r) { LL mid=(l+r)/2.0; if(ck(mid,0)) l=mid; else r=mid; } ansnum=0; ck(l,1); printf("%d\n",ansnum); for(int i=1;i<=n;i++) if(vis[i]) printf("%d\n",i); } return 0;}