最大密度子图，推荐读一下2007年国家集训队论文(胡伯涛《最小割模型在信息学竞赛中的应用》)。
恩，还有因为做NOI2006的最大获利/profit，我不得不学了ISAP和Dinic，因为Relabel-to-front过不了！而且HLPP也过不了！所以这里就用ISAP了。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-19
DESCRIPTION:
网络流 乱做
http://acm.pku.edu.cn/JudgeOnline/problem?id=3155
*/
#include <stdio.h>
#include <string.h>
const int oo=(~0u)>>1;
const int MAXV=1102;
const int MAXE=6200;
typedef struct struct_edge* edge;
struct struct_edge{int v,c;edge n,b;};
struct_edge pool[MAXE];
edge top=pool;
int S,T,V;
edge adj[MAXV];
int d[MAXV],dn[MAXV+1];
void add_edge(int u,int v,int c)
{
top->v=v,top->c=c,top->n=adj[u],adj[u]=top++;
top->v=u,top->c=0,top->n=adj[v],adj[v]=top++;
adj[u]->b=adj[v],adj[v]->b=adj[u];
}
int augment(int u,int e)
{
if (u==T) return e;
if (d[S]==V) return 0;
int f=0,mind=V-1;
for (edge i=adj[u];i;i=i->n)
if (i->c)
{
if (d[u]==d[i->v]+1)
{
int df=augment(i->v,e<i->c?e:i->c);
i->c-=df;
i->b->c+=df;
e-=df;
f+=df;
if (e==0) return f;
}
if (mind>d[i->v]) mind=d[i->v];
}
if (f) return f;
else
{
if (!–dn[d[u]]) d[S]=V;
else dn[d[u]=mind+1]++;
return 0;
}
}
int sap()
{
int f=0;
dn[0]=V;
while (d[S]<V) f+=augment(S,oo);
return f;
}
const int MAXN=100,MAXM=1000;
const int XX=MAXN*MAXN*MAXN;
int n,m;
int a[MAXM],b[MAXM];
bool visited[MAXN+MAXM+2];
int total;
void build_network(int rate)
{
memset(adj,0,sizeof(adj));
memset(d,0,sizeof(d));
memset(dn,0,sizeof(dn));
top=pool;
S=n+m,T=m+n+1,V=n+m+2;
for (int i=0;i<n;i++)
add_edge(S,i,rate);
for (int i=0;i<m;i++)
add_edge(a[i]-1,n+i,oo),
add_edge(b[i]-1,n+i,oo),
add_edge(n+i,T,XX);
}
void dfs(int u)
{
visited[u]=true;
for (edge i=adj[u];i;i=i->n)
if (!visited[i->v]&&i->c)
dfs(i->v);
}
void read()
{
scanf(“%d%d”,&n,&m);
for (int i=0;i<m;i++)
scanf(“%d%d”,a+i,b+i);
}
void write()
{
if (!m)
{
printf(“%d\n%d\n”,1,1);
return;
}
int L=0*XX,R=m*XX,best;
do
{
int mid=(L+R)>>1;
build_network(mid);
int g=m*XX-sap();
if (g<=0) R=mid;
else L=mid,best=L;
}
while (L+1!=R);
build_network(best);
sap();
dfs(S);
for (int i=0;i<n;i++)
if (!visited[i]) total++;
printf(“%d\n”,total);
for (int i=0;i<n;i++)
if (!visited[i])
printf(“%d\n”,i+1);
}
int main()
{
read();
write();
}