大数据分析课程第三次作业(最大密度子图)

​ 参考：《胡伯涛: 最小割模型在信息学竞赛中的应用》

一、作业题：

二、答案：

5. 测试数据集：bio-CE-GT.txt，数据集来源：https://networkrepository.com/bio-CE-GT.php

6. 运行结果如下：

7. 可运行代码如下(点击可打开)：

   #include<iostream>
   #include<cstring>
   #include<cmath>
   #include<algorithm>
   #include<cstdio>
   #include<iomanip>
   #include<cstdlib>
   #include<fstream>
   #include<vector> 
   #define MAXN 0x7ffff
   #define eps 1e-9
    
   typedef long long LL;
   const int N=1100005;
   using namespace std;
   inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
   int n,m,S,T,num;
   bool flag_final=0;
   struct node{int next,to,pair;double flow;}g[N<<3];
   struct Edge{int x,y;}s[N];
   int h[N],cnt;
   void AddEdge(int x,int y,double z){
   	g[++cnt].to=y,g[cnt].next=h[x],h[x]=cnt,g[cnt].flow=z,g[cnt].pair=cnt+1;
   	g[++cnt].to=x,g[cnt].next=h[y],h[y]=cnt,g[cnt].flow=0,g[cnt].pair=cnt-1;
   }
   int GAP[N],dis[N];
   void Init(){
   	static int q[N];
   	fill(dis,dis+num,0),fill(GAP,GAP+num,0);
   	int l=0,r=1;q[++l]=T,++GAP[dis[T]=1];
   	while(l<=r){
   		int x=q[l++];
   		for(int i=h[x];i;i=g[i].next){
   			int to=g[i].to;
   			if(!dis[to])++GAP[dis[to]=dis[x]+1],q[++r]=to; 
   		}
   	}
   }
   double Dfs(int x,double Maxf){
   	if(x==T||!Maxf)return Maxf;
   	double ret=0;
   	for(int i=h[x];i;i=g[i].next){
   		int to=g[i].to;
   		if(g[i].flow&&dis[x]==dis[to]+1){
   			double dlt=Dfs(to,min(g[i].flow,Maxf-ret));
   			g[i].flow-=dlt;
   			g[g[i].pair].flow+=dlt;
   			ret+=dlt;
   			if(dis[S]==num+1||ret+eps>=Maxf)return ret;
   		}
   	}
   	if(!(--GAP[dis[x]]))dis[S]=num+1;
   	else GAP[++dis[x]]++;
   	return ret;
   }
   double SAP(){
   	Init();
   	double ans=Dfs(S,MAXN);
   	while(dis[S]<=num)ans+=Dfs(S,MAXN);
   //	printf("SOA:%f\n",ans);
   	return ans;
   }
   double Check(double mid){
   	fill(h,h+num,0),cnt=0;
   	for(int i=1;i<=m;i++)AddEdge(S,i,1),AddEdge(i,s[i].x+m,MAXN),AddEdge(i,s[i].y+m,MAXN);
   	for(int i=1;i<=n;i++)AddEdge(i+m,T,mid);
   	if(flag_final){
   		double temp=SAP();
   //		printf("SAP:%f",temp);
   		return temp;
   	}
   	else{
   		return m-SAP()>0;
   	}
   }
   
   int ans;bool vis[N];
   vector<int> ans_v;
   void Find(int x){
   	if(x>m&&x<=m+n){
   		ans++;
   		ans_v.push_back(x);
   	}
   	vis[x]=1;
   	for(int i=h[x];i;i=g[i].next){
   		int to=g[i].to;
   		if(g[i].flow&&!vis[to]) Find(to);
   	}
   }
   void reading(){
   	double input_v;  //临时输入变量 
   	ifstream data("bio-CE-GT.txt");
   	int temp_cnt=1;  //遍历计数 
   	int item_cnt=1;  //总条数 
   	int gra_n=-1;    //一共多少个点
   	 
   	while (data >> input_v){
   		gra_n=max(gra_n,(int)input_v+1);
   		
   		if(temp_cnt%3==1) s[item_cnt].x = (int)input_v+1,printf("%d ",(int)input_v); 
   		if(temp_cnt%3==2) s[item_cnt].y = (int)input_v+1,printf("%d\n",(int)input_v); 
   		if(temp_cnt%3==0) item_cnt++;
   		temp_cnt++;
   //		printf("gra:%d\n",gra_n);
   	}
   	n=gra_n,m=item_cnt-1,S=0,T=n+m+1,num=T+1;
   	printf("*******************************************************\n");
   	printf("1.一共节点数:%d\n",n);
   	printf("2.一共边数:%d\n",m);
   	printf("*******************************************************\n");
   	if(!m)cout<<1,exit(0);
   	
   }
   void print_v(){
   	sort(ans_v.begin(),ans_v.end());
   	printf("6.最大密度子图集合为：\n");
   //    printf("size:%d\n",ans_v.size());
       for(int i=0;i<ans_v.size();i++){
   		printf("%d ",ans_v[i]-1);
   	}
   } 
   int main(){
   	reading();
   	printf("*******************************************************\n");
   	printf("3.数据集读取完毕\n");
   	printf("*******************************************************\n");
   	double l=0,r=m,Eps=1.0/n/n;
   	while(l+Eps<r){
   		double mid=(l+r)/2;
   		if(Check(mid))l=mid;
   		else r=mid;
   	}
   	flag_final=1;
   	double ans_dense=Check(l);
   	Find(S);
   	printf("*******************************************************\n");
   	cout<<"4.最大密度子图个数为："<<ans<<endl;
   	cout<<"5.子图最大密度为："<<ans_dense/ans<<endl;
   	printf("*******************************************************\n");
   	print_v();
   	return 0;
   }