[POJ3155]Hard Life（01分數規劃）

2019-11-08 19:43:54

字體：大中小

來源：轉載

供稿：網友

題目描述

傳送門題意：一張圖，選出一個子圖，滿足邊數/點數最大

題解

最大密度子圖問題… 算法一二分g，然后點權變成-g，邊權變成1，求一個最大的子圖可以發現邊權為正，點權為負，所以說會盡量多選邊，那么我們說選一條邊就一定會選兩個點就沒有什么問題了（按理來說應該是選了兩個點就一定要選某條邊）這就是一個典型的最大權閉合子圖問題了…建圖之后跑最小割就行了算法二（對算法一的改進算法）有的時候算法一的邊和點太多… 設每一個點的度為di $d_i$ ，然后將原問題取相反數了之后變成了求最小假設我們求出了一個點集，需要計算的邊就是所有與這個點集相關的邊-只有一個端點在點集里的邊只有一個端點在點集里的邊實際上就是將點集與其它分開的一個割，所以說這個點集也是一個割集現在可以轉化成這樣一個問題：某一個點不選代價是0，選了代價是2g?di $2g-d_i$ ，然后如果兩個點一個選了一個沒選并且中間有邊的話這條邊需要割掉，也就是花費1的代價，然后選一些點使代價最小這樣就是一個最小割的模型了：原圖中的邊x->y在新圖中連邊x->y,y->x,1，對于原圖中的每一個點s->i,U，i->t,U+2g-di（U是一個大數，保證邊權不為負），然后判斷(U*n-c)/2和0的關系即可（取相反數了之后再反回去）

推薦看看胡伯濤的論文

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define N 10005const double eps=1e-10;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n,m,s,t,x[N],y[N];int tot,point[N],nxt[N],v[N];double remain[N];int deep[N],last[N],cur[N],num[N],ans[N];double d[N],maxflow,ave,U;bool vis[N];queue <int> q;void addedge(int x,int y,double cap){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;}void bfs(int t){ for (int i=1;i<=t;++i) deep[i]=t; deep[t]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; while (!q.empty()) q.pop(); q.push(t); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&dcmp(remain[i^1])) { deep[v[i]]=deep[now]+1; q.push(v[i]); } }}double addflow(int s,int t){ int now=t; double ans=1e10; while (now!=s) { ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s) { remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans;}void isap(int s,int t){ bfs(t); for (int i=1;i<=t;++i) ++num[deep[i]]; int now=s; while (deep[s]<t) { if (now==t) { maxflow+=addflow(s,t); now=s; } bool has_find=0; for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]+1==deep[now]&&dcmp(remain[i])) { has_find=1; cur[now]=i; last[v[i]]=i; now=v[i]; break; } if (!has_find) { int minn=t-1; for (int i=point[now];i!=-1;i=nxt[i]) if (dcmp(remain[i])) minn=min(minn,deep[v[i]]); if (!(--num[deep[now]])) break; ++num[deep[now]=minn+1]; cur[now]=point[now]; if (now!=s) now=v[last[now]^1]; } }}bool check(double g){ tot=-1;memset(point,-1,sizeof(point)); memset(num,0,sizeof(num)); for (int i=1;i<=m;++i) addedge(x[i],y[i],1.0),addedge(y[i],x[i],1.0); for (int i=1;i<=n;++i) addedge(s,i,U),addedge(i,t,U+2*g-d[i]); maxflow=0;isap(s,t); return dcmp(U*(double)n-maxflow)>0;}void find(){ double l=0,r=m+0.0,mid; while (r-l>=1.0/n/n) { mid=(l+r)/2.0; if (check(mid)) ave=l=mid; else r=mid; }}void dfs(int x){ vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (!vis[v[i]]&&dcmp(remain[i])) dfs(v[i]);}int main(){ scanf("%d%d",&n,&m);U=m+0.0; if (m==0) {puts("1/n1/n");return 0;} s=n+1,t=s+1; for (int i=1;i<=m;++i) scanf("%d%d",&x[i],&y[i]),d[x[i]]+=1.0,d[y[i]]+=1.0; find(); check(ave); dfs(s); for (int i=1;i<=n;++i) if (vis[i]) ans[++ans[0]]=i;