时间复杂度分析

设图中节点数为 ( n )，边数为 ( m )。

• 二分查找次数：代码通过二分法确定最大密度 ( g )，精度要求为 ( \frac{1}{n^2} )，二分次数约为 ( O(\log(n^2 \cdot m)) = O(2 \log n + \log m) )，视为常数次。
• 每次最大流计算：使用改进的 ISAP 算法，时间复杂度为 ( O(n^2 m) )（其中 ( n ) 为节点数，此处扩展后的图节点数为 ( n + m + 2 )，边数为 ( 2m + 2n )）。
• 总时间复杂度：( O(\text{二分次数} \times n^2 m) )。由于 ( n \leq 100 )，( m \leq 1000 )，实际运行效率可接受。

解题思路

问题建模

• 将团队选择问题转化为最大密度子图问题。子图的密度定义为边数 ( e ) 与节点数 ( v ) 的比值 ( \frac{e}{v} )，目标是找到密度最大的子图。
• 通过最大流算法求解最大密度子图，利用二分法逼近最优密度 ( g )，并通过最大权闭合图模型验证当前密度的可行性。

关键步骤

1. 二分法确定最大密度 ( g )：

   • 初始区间为 ( [0, m] )，每次取中点 ( \text{mid} ) 作为当前假设的密度 ( g )。
   • 构建流网络验证是否存在密度不小于 ( g ) 的子图。若存在，调整下界；否则调整上界。

2. 流网络构建（针对当前 ( g )）：

   • 源点 ( S )、汇点 ( T )，原图节点 ( 1 \sim n )，边节点 ( n+1 \sim n+m )（每条边对应一个节点）。
   • 边连接：
     • 源点向每条边节点连一条容量为 ( 1 ) 的边，表示选择该边需“支付”1单位代价。
     • 边节点向其连接的两个原图节点连容量为无穷大的边，表示边必须与两个节点同时选中。
     • 每个原图节点向汇点连一条容量为 ( g ) 的边，表示选择该节点需“支付”( g ) 单位代价。

3. 最大流与密度验证：

   • 计算源点到汇点的最大流，若 ( m - \text{maxflow} \geq 0 )，说明存在密度至少为 ( g ) 的子图（其中 ( m ) 为总边数，( \text{maxflow} ) 为最小割容量）。

4. 提取最大密度子图：

   • 在最终确定的密度 ( g ) 下，通过残量网络找到从源点可达的原图节点，这些节点构成最大密度子图。

代码逻辑解析

• 数据结构：使用邻接表存储流网络，Edge 结构体记录边的终点、容量和下一条边。
• ISAP 算法：改进的最短增广路算法，利用层次数组 level 和 gap 数组优化，快速求解最大流。
• 二分法循环：通过不断调整密度 ( g ) 的上下界，逼近最优解，精度控制在 ( \frac{1}{n^2} ) 以内。
• 子图提取：在残量网络中从源点出发进行深度优先搜索（DFS），标记所有可达的原图节点，即为最大密度子图的节点集合。

示例验证（以输入数据 1 为例）

• 原图有5个节点、6条边，目标是找到密度最大的子图。
• 通过二分法确定最大密度为 ( \frac{5}{4} )，对应子图包含节点1、2、4、5（4个节点，5条边）。
• 流网络构建后，最大流计算验证该子图的密度可行性，最终通过残量网络提取节点集合。

算法正确性

• 最大密度子图问题可通过分数规划转化为最大权闭合图问题，利用最大流算法求解。
• 二分法保证收敛到最优密度，残量网络的可达性分析正确提取子图节点。

注意事项

• 当 ( m = 0 ) 时，所有团队密度为0，直接输出任意单节点团队。
• 边节点的引入是为了将边与节点的依赖关系转化为流网络中的容量约束，确保边的选择必须包含其连接的两个节点。

C++代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
LL quickPow(LL a,LL b){ LL ans=1; while(b){if(b&1)ans*=a; a*=a; b>>=1;} return ans; }
LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL ans=0; while(b){if(b&1)ans=(ans+a)%mod; a=(a<<=1)%mod; b>>=1; } return ans%mod;}
LL quickMultPowMod(LL a, LL b,LL mod){ LL ans=1,k=a; while(b){if((b&1))ans=multMod(ans,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return ans%mod;}
LL quickPowMod(LL a,LL b,LL mod){ LL ans=1; while(b){if(b&1)ans=(a*ans)%mod; a=(a*a)%mod; b>>=1; } return ans; }
LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-6;
const int MOD = 1000000000+7;
const int N = 1500+5;
const int dx[] = {0,0,-1,1,1,-1,1,1};
const int dy[] = {1,-1,0,0,-1,1,-1,1};
using namespace std;
 
struct Edge {
    int to, next;
    double cap;
} edge[80 * N]; 
Pair pastEdge[N];//原图边集
int head[N],tot;
int n,m,S,T;
int ans;//层数
int level[N];//记录层次
int gap[N];//记录每组层次标号有几个
int numNode;//最大密度子图中点的个数
bool vis[N];//标记最大密度子图中的点
void addedge(int x, int y, double cap) {
    edge[tot].to = y;
    edge[tot].cap = cap;
    edge[tot].next = head[x];
    head[x] = tot++;
 
    edge[tot].to = x;
    edge[tot].cap = 0;
    edge[tot].next = head[y];
    head[y] = tot++;
}
void makeMap(double g) {
    memset(head,-1,sizeof(head));  
    tot=0;
 
    for(int i=1;i<=n;i++)//原图中的点到汇点 
        addedge(i,T,g); 
    for(int i=0;i<m;i++) {  
        //源点到原图中的每条边
        addedge(S,n+i+1,1.0);
        //原图中的每条边到之间建边
        addedge(n+i+1,pastEdge[i].first,INF);  
        addedge(n+i+1,pastEdge[i].second,INF);  
    }  
}
double dfs(int x, double minflow) {
    if (x == T)
        return minflow;
 
    double flow = 0.0;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        int y = edge[i].to;
        if (edge[i].cap > 0) {
            if (level[y] + 1 == level[x]) {
                double newFlow =
                    edge[i].cap > minflow - flow ? minflow - flow : edge[i].cap;
                newFlow = dfs(y, newFlow);
 
                flow += newFlow;
                edge[i].cap -= newFlow;
                edge[i ^ 1].cap += newFlow;
 
                if (minflow - flow <= EPS)
                    return flow;
                if (level[S] >= ans)
                    return flow;
            }
        }
    }
 
    if (--gap[level[x]] == 0)
        level[S] = ans;
    level[x]++;
    gap[level[x]]++;
    return flow;
}
double ISAP() {
    double maxflow=0.0;    
    memset(gap,0,sizeof(gap));    
    memset(level,0,sizeof(level));  
    gap[0]=ans;    
 
    while(level[S]<ans)
        maxflow+=dfs(S,INF);
 
    return 1.0*m-maxflow;     
}
void findNode(int x) {//寻找残量网络中可到达的点
    vis[x] = true;
    if (x >= 1 && x <= n)
        numNode++;
    for (int i = head[x]; i != -1; i = edge[i].next) {
        int y = edge[i].to;
        if (vis[y] == false && edge[i].cap > 0)
            findNode(y);
    }
}
int main() {
    while (scanf("%d%d", &n, &m) != -1) {
        if (m == 0) {
            printf("1\n1\n");
            continue;
        }
 
        S=0,T=n+m+1;
        ans=T+1;  
        
        for(int i=0;i<m;i++)  
            scanf("%d%d",&pastEdge[i].first,&pastEdge[i].second);
 
        double left = 0, right = m;
        while (right - left >= 1.0 / (n*n)) { //论文给出了证明,不同解之间误差的精度不超过1/(n*n）
            double mid = (left + right) / 2;
            makeMap(mid); //根据mid值重新建图
 
            if (ISAP() < EPS) //如果小于0，g值太大，调整上界
                right = mid;
            else
                left = mid;
        }
        // printf("%lf",left);//最大密度
 
        makeMap(left); //根据最大密度建图
        ISAP();        //求最大权闭合图
 
        //寻找最大密度子图中的点
        numNode = 0;
        memset(vis, false, sizeof(vis));
        findNode(S);
        printf("%d\n", numNode);
        for (int i = 1; i <= n; i++)
            if (vis[i])
                printf("%d ", i);
        printf("\n");
    }  
    return 0;  
}