思路：
这个还是看的胡伯涛的论文《最小割在信息学竞赛中的应用》。是将最大密度子图问题转化为了01分数规划和最小割问题。
直接上代码：
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #define Maxn 6010 #define Maxm 200000 #define LL double #define inf 100000000 #define Abs(a) (a)>0?(a):(-a) using namespace std; struct Edge{ int from,to,next; LL val; }edge[Maxm]; const double eps=1e-5; LL value[Maxn]; int head[Maxn],work[Maxn],dis[Maxn],q[Maxn],e,vi[Maxn]; inline void addedge(int from,int to,LL val)//有向边 { edge[e].from=from; edge[e].to=to; edge[e].val=val; edge[e].next=head[from]; head[from]=e++; edge[e].from=to; edge[e].to=from; edge[e].val=0; edge[e].next=head[to]; head[to]=e++; } inline double min(double a,double b) { return a>b?b:a; } void init() { e=0; memset(head,-1,sizeof(head)); } void add(int u,int v,LL c) { edge[e].to=v;edge[e].val=c;edge[e].next=head[u];head[u]=e++; edge[e].to=u;edge[e].val=0;edge[e].next=head[v];head[v]=e++; } int bfs(int S,int T) { int rear=0; memset(dis,-1,sizeof(dis)); dis[S]=0;q[rear++]=S; for(int i=0;i<rear;i++) { for(int j=head[q[i]];j!=-1;j=edge[j].next) { if(edge[j].val>0&&dis[edge[j].to]==-1) { dis[edge[j].to]=dis[q[i]]+1; q[rear++]=edge[j].to; if(edge[j].to==T) return 1; } } } return 0; } LL dfs(int cur,LL a,int T) { if(cur==T) return a; for(int i=work[cur];i!=-1;i=edge[i].next) { if(edge[i].val>0&&dis[edge[i].to]==dis[cur]+1) { LL t=dfs(edge[i].to,min(a,edge[i].val),T); if(t>0) { edge[i].val-=t; edge[i^1].val+=t; return t; } } } return 0; } LL Dinic(int S,int T) { LL ans=0; while(bfs(S,T)) { memcpy(work,head,sizeof(head)); LL t=dfs(S,inf,T); while(t>0) { ans+=t; t=dfs(S,inf,T); } } return ans; } int main() { int n,m,i,j,a[Maxn],b[Maxn]; int degree[Maxn]; memset(degree,0,sizeof(degree)); while(scanf("%d%d",&n,&m)!=EOF) { if(m==0) { printf("1 1 "); return 0; } init(); for(i=1;i<=m;i++) { scanf("%d%d",a+i,b+i); degree[a[i]]++; degree[b[i]]++; } double l=0,r=m,mid; double eps2=1.0/n/n; while(r-l>eps2) { mid=(l+r)/2; init(); for(i=1;i<=m;i++) { add(a[i],b[i],1); add(b[i],a[i],1); } for(i=1;i<=n;i++) { add(0,i,m); add(i,n+1,m * 1.0 + 2 * mid - degree[i] * 1.0); } double tt=Dinic(0,n+1); double temp=(m*n*1.0-tt)/2.0; //cout<<tt<<endl; if(temp>eps) l=mid; else r=mid; } init(); for(i=1;i<=m;i++) { add(a[i],b[i],1); add(b[i],a[i],1); } for(i=1;i<=n;i++) { add(0,i,m); add(i,n+1,m*1.0+2*l-degree[i]*1.0); //cout<<m<<" "<<mid<<" "<<degree[i]<<" "<<m+2*mid-degree[i]<<endl; } //for(i=0;i<e;i++) //cout<<edge[i].to<<" "<<edge[i].next<<" "<<edge[i].val<<endl; Dinic(0,n+1); vector<int> ans; memset(vi,0,sizeof(vi)); for(i=1;i<=n;i++) if(dis[i]>=0) ans.push_back(i); int num=ans.size(); printf("%d ",num); for(i=0;i<num;i++) printf("%d ",ans[i]); } return 0; }