已知图中点数n，边数m
1.统计每个点的度数d(i)
2.枚举参数g的区间[0,m]
3.参数精度要求1/(n^2)
4.每次枚举参数的建图：
源点为S，汇点为T，addedge(from,to,cap)
(1)对每条边(x,y) addedge(x,y,1) addedge(y,x,1)
(2)对每个点i addedge(S,i,m) addedge(i,T,m+2*g-d(i))
(3)做一次最大流，h=maxflow(S,T)
5.若h/2>eps l = mid,否则，r = mid
6.用求得的low跑一次最大流，从S点dfs所有没有满流的边，给所有非S,T的点标记，这些点就是最后所求得的点。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define maxn 110 8 #define eps 1e-5 9 #define INF 1<<30 10 using namespace std; 11 12 struct Edge{ 13 int from,to; 14 double cap,flow; 15 }; 16 struct ISAP { 17 int n, m, s, t; 18 vector edges; 19 vector G[maxn]; 20 bool vis[maxn]; 21 int d[maxn]; 22 int cur[maxn]; 23 int p[maxn]; 24 int num[maxn]; 25 26 void AddEdge(int from, int to, double cap) { 27 edges.push_back((Edge){ from, to, cap, 0}); 28 edges.push_back((Edge){to, from, 0, 0}); 29 m = edges.size(); 30 G[from].push_back(m-2); 31 G[to].push_back(m-1); 32 } 33 34 bool BFS() { 35 memset(vis, 0, sizeof(vis)); 36 queue Q; 37 Q.push(t); 38 vis[t] = 1; 39 d[t] = 0; 40 while(!Q.empty()) { 41 int x = Q.front(); Q.pop(); 42 for(int i = 0; i < G[x].size(); i++) { 43 Edge& e = edges[G[x][i]^1]; 44 if(!vis[e.from] && e.cap > e.flow) { 45 vis[e.from] = 1; 46 d[e.from] = d[x] + 1; 47 Q.push(e.from); 48 } 49 } 50 } 51 return vis[s]; 52 } 53 54 void ClearAll(int n) { 55 this->n = n; 56 for(int i = 0; i < n; i++) G[i].clear(); 57 edges.clear(); 58 } 59 60 double Augment() { 61 int x = t; 62 double a = INF; 63 while(x != s) { 64 Edge& e = edges[p[x]]; 65 a = min(a, e.cap-e.flow); 66 x = edges[p[x]].from; 67 } 68 x = t; 69 while(x != s) { 70 edges[p[x]].flow += a; 71 edges[p[x]^1].flow -= a; 72 x = edges[p[x]].from; 73 } 74 return a; 75 } 76 77 double Maxflow(int s, int t) { 78 this->s = s; this->t = t; 79 double flow = 0; 80 BFS(); 81 memset(num, 0, sizeof(num)); 82 for(int i = 0; i < n; i++) num[d[i]]++; 83 int x = s; 84 memset(cur, 0, sizeof(cur)); 85 while(d[s] < n) { 86 if(x == t) { 87 flow += Augment(); 88 x = s; 89 } 90 int ok = 0; 91 for(int i = cur[x]; i < G[x].size(); i++) { 92 Edge& e = edges[G[x][i]]; 93 if(e.cap > e.flow && d[x] == d[e.to] + 1) { //Advance 94 ok = 1; 95 p[e.to] = G[x][i]; 96 cur[x] = i; 97 x = e.to; 98 break; 99 }100 }101 if(!ok) { // Retreat102 int m = n-1;103 for(int i = 0; i < G[x].size(); i++) {104 Edge& e = edges[G[x][i]];105 if(e.cap > e.flow) m = min(m, d[e.to]);106 }107 if(--num[d[x]] == 0) break;108 num[d[x] = m+1]++;109 cur[x] = 0;110 if(x != s) x = edges[p[x]].from;111 }112 }113 return flow;114 }115 };116 117 int n,m;118 ISAP isap;119 int xx[maxn*10],yy[maxn*10],d[maxn];120 bool used[maxn];121 122 bool test(double mid){123 isap.ClearAll(n+2);124 int S = 0,T = n+1;125 for(int i = 1;i <= m;i++){126 isap.AddEdge(xx[i],yy[i],1.0);127 isap.AddEdge(yy[i],xx[i],1.0);128 }129 for(int i = 1;i <= n;i++){130 isap.AddEdge(S,i,m*1.0);131 isap.AddEdge(i,T,m+2*mid-d[i]+0.0);132 }133 double h = (m*n*1.0 - isap.Maxflow(S,T)) * 0.5;134 if(h > 0) return true;135 return false;136 }137 138 int ans;139 void dfs(int u){140 used[u] = true;141 if(u >=1 && u <= n) ans++;142 for(int i = 0;i < isap.G[u].size();i++){143 Edge& e = isap.edges[isap.G[u][i]];144 if(e.cap > e.flow && !used[e.to])145 dfs(e.to);146 }147 }148 149 int main(){150 while(scanf("%d%d", &n, &m) != EOF){151 if(m == 0){152 printf("1\n1\n");153 continue;154 }155 memset(d,0,sizeof(d));156 for(int i = 1;i <= m;i++){157 scanf("%d%d",&xx[i],&yy[i]);158 d[xx[i]]++;159 d[yy[i]]++;160 }161 double l = 0,r = m * 1.0;162 while(r - l > 1.0/n/n){163 double mid = (l+r) * 0.5;164 if(test(mid)) l = mid;165 else r = mid;166 }167 //printf("%.3f\n",l);168 test(l);169 memset(used,0,sizeof(used));170 ans = 0;171 dfs(0);172 printf("%d\n",ans);173 for(int i = 1;i <= n;i++){174 if(used[i]) printf("%d\n",i);175 }176 }177 return 0;178 }