论文出处：最小割模型在信息学竞赛终的应用
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const double eps = 1e-9; const int inf = 0x3f3f3f3f; const int maxn = 100 + 5; const int maxe = 1000 + 5; struct edge{ int to, next; double w; } ed[maxe*10]; int head[maxn], tot; int n, m, ans; int sp, tp, degree[maxn], d[maxn]; struct E{ int u, v; }p[maxe]; bool vis[maxn]; inline void init(){ memset( head, -1, sizeof(head) ); tot = 1; } inline void add( int u, int v, double w ){ ed[++tot].to = v; ed[tot].w = w; ed[tot].next = head[u]; head[u] = tot; ed[++tot].to = u; ed[tot].w = 0; ed[tot].next = head[v]; head[v] = tot; } inline bool bfs(){ memset( d, 0, sizeof(d) ); queue<int> q; d[sp] = 1; q.push(sp); while( q.size() ){ int x = q.front(); q.pop(); for( int i=head[x]; ~i; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w>=eps && !d[y] ){ d[y] = d[x] + 1; q.push(y); if( y==tp ) return 1; } } } return 0; } inline double dfs( int x, double flow ){ if( x==tp ) return flow; double res = flow, k; for( int i=head[x]; ~i&&res>=eps; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w>=eps && d[y]==d[x]+1 ){ k = dfs( y, min(res, ed[i].w) ); if( k<eps ) d[y] = 0; ed[i].w -= k; ed[i^1].w += k; res -= k; } } return flow-res; } inline double check( double g ){ init(); for( int i=0; i<m; i++ ){ add( p[i].u, p[i].v, 1 ); add( p[i].v, p[i].u, 1 ); } double U = m; for( int i=1; i<=n; i++ ){ add( sp, i, U ); add( i, tp, U+2*g-degree[i] ); } double maxflow=0, flow; while( bfs() ){ while( (flow=dfs(sp, inf))>=eps ) maxflow += flow; } return (U*n-maxflow)*0.5; } inline void find_cut( int x ){ for( int i=head[x]; ~i; i=ed[i].next ){ int y = ed[i].to; if( ed[i].w>=eps && !vis[y] ){ vis[y] = 1; ans ++; find_cut(y); } } } int main(){ // freopen("in.txt", "r", stdin); while(~scanf("%d%d", &n, &m)){ if( !m ){ puts("1 1"); continue; } memset( degree, 0, sizeof(degree) ); memset( vis, 0, sizeof(vis) ); sp = 0; tp = n+1; for( int i=0; i<m; i++ ){ scanf("%d%d", &p[i].u, &p[i].v); degree[p[i].u] ++; degree[p[i].v] ++; } double l = 0, r = m; double tmp = 1.0/n/n; //这里需要设定一个上界啊，不然WA，具体证明请看论文 while( r-l>=tmp ){ double mid = (l+r)*0.5; if( check(mid)<eps ) r = mid; else l = mid; } check(l); //保证精度 vis[sp] = 1; find_cut(sp); printf("%d ", ans); for( int i=1; i<=n; i++ ) if(vis[i]) printf("%d ", i); } return 0; }