UVA1389 Hard Life[二分答案+最小割]

我真菜啊←地址

求最大密度子图方案。密度=边数/点数


假设E,V为最大密度子图的边数点数。则$\forall \rho$有$\rho \leqslant \frac{E}{V}$即$E- \rho V \geqslant 0$,也就是说密度最大时不等式去等号,密度要是小一些的话就应大于0,那可以二分密度寻找最大的密度,判断是否合法的方法:要看左边的等式有没有大于0,那可以把点看成权值是$-\rho$的点,边抽象成权值为$1$的点,且其向连接两端的点连有向边。然后做最大权闭合子图,保证边选上就得把点也给选上。这样得到的最大权大于零说明密度枚举小了,而为零表示枚举值大于等于最大密度。那就通过二分找到那个刚好突变的数就是最大密度,这是停止二分把残量网络跑一遍,得所选点。

UVA1389 Hard Life[二分答案+最小割]

这题稍微卡精度,或者说我没怎么写过浮点数二分答案,反正稍有些费劲,记住就是了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 typedef double db;
 9 #define dbg(x) cerr<<#x<<" = "<<x<<endl
10 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
11 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
12 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
13 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
14 template<typename T>inline void inc(T&A,T B){A+=B;}
15 inline int read(int&x){
16     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
17     while(isdigit(c))x=x*10+c-'0',c=getchar();if(c=='\n')return -1;return f?-x:x;
18 }
19 const int N=1100+9,M=3200+7;const db eps=1e-5,INF=99999999.0;
20 int Head[N],cur[N],Next[M<<1],v[M<<1],dis[N],vis[N],tot,n,m,s,t;
21 db w[M<<1];
22 inline void Addedge(int x,int y,db z){
23     v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
24     v[++tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=0;
25 }
26 #define y v[j]
27 inline int bfs(){
28     queue<int> q;memset(dis,0,sizeof dis),dis[s]=1,q.push(s);
29     for(register int i=1;i<=(n+m)+2;++i)cur[i]=Head[i];
30     while(!q.empty()){
31         int x=q.front();q.pop();
32         for(register int j=Head[x];j;j=Next[j])if(w[j]>0&&!dis[y]){
33             dis[y]=dis[x]+1,q.push(y);
34             if(y==t)return 1;
35         }
36     }
37     return 0;
38 }
39 db dinic(int x,db flow){
40     if(flow<eps||x==t)return flow;
41     db rest=flow,k;
42     for(register int j=cur[x];j&&rest;cur[x]=j,j=Next[j])if(w[j]>0&&dis[y]==dis[x]+1){
43         if((k=dinic(y,_min(rest,w[j])))<eps)dis[y]=0;
44         rest-=k,w[j]-=k,w[j^1]+=k;
45     }
46     return flow-rest;
47 }
48 #undef y
49 int flag,edge[1005][2],cnt;
50 db L,R,mid,res,maxflow,ans;
51 
52 inline db check(db rho){//dbg(rho);
53     memset(Head,0,sizeof Head);maxflow=ans=0;tot=1;
54     for(register int i=1;i<=m;++i)ans+=1.0,Addedge(s,i,1.0),Addedge(i,edge[i][0]+m,INF),Addedge(i,edge[i][1]+m,INF);
55     for(register int i=1;i<=n;++i)Addedge(i+m,t,rho);
56     while(bfs())maxflow+=dinic(s,INF);
57     ans-=maxflow;//dbg(maxflow);dbg(ans);
58     return ans;
59 }
60 void dfs(int x){//cerr<<x<<endl;
61     vis[x]=1;for(register int j=Head[x];j;j=Next[j]){
62 //        dbg(v[j]),dbg(w[j]);
63         if(w[j]>0&&!vis[v[j]])dfs(v[j]);
64     }
65 }
66 
67 int main(){//freopen("tmp.in","r",stdin);//freopen("tmp.out","w",stdout);
68     while(~scanf("%d%d",&n,&m)){
69         if(flag)puts("");else flag=1;
70         if(m==0){printf("1\n1\n");continue;}
71         for(register int i=1;i<=m;++i)read(edge[i][0]),read(edge[i][1]);
72         L=0,R=m/2.0;s=n+m+1,t=s+1;
73         while(R-L>eps){//dbg(L),dbg(R);
74             mid=(L+R)/2.0;db res=check(mid);
75             if(res<eps)R=mid-eps;
76             else L=mid;
77         }
78         check(L),memset(vis,0,sizeof vis),dfs(s);cnt=0;
79         for(register int i=1;i<=n;++i)if(vis[i+m])++cnt;
80         printf("%d\n",cnt);
81         for(register int i=1;i<=n;++i)if(vis[i+m])printf("%d\n",i);
82     }
83     return 0;
84 }

 

上一篇:2021-07-29


下一篇:学习笔记4: HATEOAS