最大密度子图,论文题目。
这题构造出来的g(k) = max{∑E-k∑V},g(k)是一个下界为0的单调递减函数,即存在x1, g(x1) = 0,
对于所有x > x1, g(x)≡0。按照论文上的证明方法的话我们只要发现一个g(k) = 0,就可以认为是最
优解了,但是此题要二分到函数值为0的左端点才可以,为什么是这样呢?
其实我们不难发现对于所有的x > x1, 我们采取的最优决策是一个都不选,这就会导致∑V为0,而我
们证明其最优性时的前提是∑V不为0,所以这种情况我们得到的并不是最优解。
还有一个问题就是我们求最大闭合权图的算法会导致一种情况,当全部收益值与耗费值相等时,我们
使用dfs求决策时,会导致什么不选择任何决策,如果单纯的求最大闭合权图,这种做法没有问题,
但是对于这题要求V不能为∅,所以我们可以选择一个x2 < x1,且x1-x2 < 1/(n*n),对x2再求一次决策,
根据论文上的证明x2也会得到最优解,并且不会导致V为∅的情况。
测试数据:
input:
3 3
1 2
2 3
1 3
output:
3
1
2
3
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> #include <bitset> #include <iomanip> //#pragma comment(linker, "/STACK:102400000,102400000") using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::stringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; using std::multimap; using std::deque; using std::unique; using std::lower_bound; using std::random_shuffle; using std::bitset; using std::upper_bound; using std::multiset; using std::ios; using std::make_heap; using std::push_heap; using std::pop_heap; typedef long long LL; typedef unsigned long long ULL; typedef unsigned UN; typedef pair<ULL, ULL> PAIR; typedef multimap<int, int> MMAP; typedef long double LF; const int MAXN(1510); const int MAXM(40010); const int MAXE(10010); const int MAXK(6); const int HSIZE(13131); const int SIGMA_SIZE(26+11); const int MAXH(18); const int INFI((INT_MAX-1) >> 1); const ULL BASE(31); const LL LIM(1e13); const int INV(-10000); const int MOD(1000000007); const double EPS(1e-7); const LF PI(acos(-1.0)); template<typename T> inline bool checkmax(T &a, T b){if(b > a) { a = b; return true;} return false;} template<typename T> inline bool checkmin(T &a, T b){if(b < a) { a = b; return true;} return false;} template<typename T> inline T ABS(const T &a){return a < 0? -a: a;} inline bool EZ(double a){return ABS(a) < EPS;} struct EDGE { int u, v, next; double lf; EDGE(){} EDGE(int u_, int v_, double l_, int n_): u(u_), v(v_), lf(l_), next(n_){} } edge[MAXE]; int first[MAXN], rear; void init(int n) { memset(first, -1, sizeof(first[0])*(n+1)); rear = 0; } void insert(int u, int v, double lf) { edge[rear] = EDGE(u, v, lf, first[u]); first[u] = rear++; edge[rear] = EDGE(v, u, 0, first[v]); first[v] = rear++; } int S, E, N; int que[MAXN], front, back; int level[MAXN]; bool bfs() { memset(level, -1, sizeof(level[0])*(N+1)); front = back = 0; que[back++] = S; level[S] = 0; while(front < back) { int u = que[front++], v; for(int i = first[u]; ~i; i = edge[i].next) if(!EZ(edge[i].lf) && level[v = edge[i].v] == -1) { level[v] = level[u]+1; if(v == E) return true; que[back++] = v; } } return false; } int sta[MAXN], tfi[MAXN], ted[MAXN]; int top; double aug() { double ret = 0; for(int i = 0; i <= N; ++i) tfi[i] = first[i]; top = 0; sta[top++] = S; while(top) { int u = sta[top-1]; if(u != E) { int ti; for(; ~(ti = tfi[u]); tfi[u] = edge[ti].next) if(!EZ(edge[ti].lf) && level[edge[ti].v] == level[u]+1) break; if(~ti) { sta[top] = edge[ti].v; ted[top++] = ti; } else { level[u] = -1; --top; } } else { double mf = INFI; for(int i = top-1; i >= 1; --i) checkmin(mf, edge[ted[i]].lf); for(int i = top-1; i >= 1; --i) { edge[ted[i]].lf -= mf; edge[ted[i]^1].lf += mf; if(EZ(edge[ted[i]].lf)) top = i-1; } ret += mf; } } return ret; } double dinic() { double ret = 0; while(bfs()) ret += aug(); return ret; } int rec[1010][2]; double cal(double val, int n, int m) { N = n+m+2; S = N-2; E = N-1; init(N); double ret = m; for(int i = 0; i < m; ++i) { insert(S, i, 1); insert(i, rec[i][0]+m, INFI); insert(i, rec[i][1]+m, INFI); } for(int i = 0; i < n; ++i) insert(i+m, E, val); return ret-dinic(); } bool vis[MAXN]; void dfs(int u) { vis[u] = true; for(int i = first[u]; ~i; i = edge[i].next) if(!EZ(edge[i].lf) && !vis[edge[i].v]) dfs(edge[i].v); } int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < m; ++i) { scanf("%d%d", rec[i], rec[i]+1); --rec[i][0]; --rec[i][1]; } double l = 0, r = n, lim = 1./n/n; while(r-l >= lim) { double mid = (l+r)/2; if(cal(mid, n, m) > 0) l = mid; else r = mid; } cal(l, n, m); //mid-l < 1/(n*n) memset(vis, 0, sizeof(vis)); dfs(S); int ans = 0; for(int i = 0; i < n; ++i) if(vis[i+m]) ++ans; if(!EZ(l)) { printf("%d\n", ans); for(int i = 0; i < n; ++i) if(vis[i+m]) printf("%d\n", i+1); } else printf("1\n1\n"); } return 0; }