POJ 3155 Hard Life(最小割-最大密集子图)-白红宇

POJ 3155 Hard Life(最小割-最大密集子图)

阅读量：6071 次

发布时间：2019-06-20

本文共 3063 字，大约阅读时间需要 10 分钟。

题目链接:http://poj.org/problem?id=3155

题意：给定一个n个点m条边的无向图。输出最大密集子图中的顶点个数和各个顶点编号。

思路：二分答案g，原图中的边(u,v)连边<u,v,1>和<v,u,1>。s和每个点连边<s,i,m>,每个点和汇点连边<i,t,m+2*g-d[i]>。d[i]为每个点的度。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define EPS 1e-9#define FOR0(i,x) for(i=0;i
                
                 =0;i--)#define FORL1(i,a) for(i=a;i>=1;i--)#define FORL(i,a,b)for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(int &x,int &y,int &z,int &t){scanf("%d%d%d%d",&x,&y,&z,&t);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(int x,int y) {printf("%d %d\n",x,y);}void PR(i64 x) {printf("%lld\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(double x) {printf("%.5lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<
                 
                  <
                  
                   edges[curedge[i]].cap) k=i,d=edges[curedge[i]].cap; for(i=s;i!=t;i=edges[curedge[i]].v) { x=curedge[i]; edges[x].cap-=d; edges[x].flow+=d; edges[x^1].cap+=d; edges[x^1].flow-=d; } maxflow+=d;u=k; } for(i=curedge[u];i!=-1;i=edges[i].next)if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) break; if(i!=-1) { curedge[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(0==--num[h[u]]) break; curedge[u]=head[u]; for(x=n,i=head[u];i!=-1;i=edges[i].next) if(edges[i].cap>0) x=min(x,h[edges[i].v]); h[u]=x+1;num[h[u]]++; if(u!=s) u=pre[u]; } } return maxflow;}void DFS(int u){ int i; visit[u]=1; if(u!=s) ans[++ans[0]]=u; for(i=head[u];i!=-1;i=edges[i].next) { if(edges[i].cap>1e-8&&!visit[edges[i].v]) { DFS(edges[i].v); } }}double calMaxDensity(int s,int t){ double low,high,mid,flow; low=0.0;high=1.0*m; while(high-low>=1.0/n/n) { mid=(low+high)/2; init(mid); flow=Maxflow(s,t); flow=(1.0*m*n-flow)/2; if(flow>1e-8) low=mid; else high=mid; } init(low); Maxflow(s,t);clr(visit,0); ans[0]=0;DFS(s); sort(ans+1,ans+ans[0]+1); return low;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { int i; clr(d,0); FOR1(i,m) { RD(a[i],b[i]); d[a[i]]++; d[b[i]]++; } if(!m) { puts("1"); puts("1"); continue; } s=0;t=n+1; calMaxDensity(s,t); PR(ans[0]); FOR1(i,ans[0]) PR(ans[i]); } return 0;}