POJ Hard Life （最大密度子圖）
Hard Life
做該題前需要先了解一些專有名詞及定理。
希望你可以親自看看2007年胡伯濤的論文！
有向圖的閉合圖（closure）： 閉合圖內任意點的任意後繼也一定還在閉合圖中。
題目：
給出N個人，有些人之間有聯系，而有聯系的兩個人被認為是一個整體。如果，把人看作點，把關系看作邊，則要求你求出 邊 / 點 的比值最大。而這些點邊之間必須是一個閉合圖。
算法分析：
最大密度子圖算法構造：
把原圖中的無向邊轉換成兩條有向邊，容量為1。
設一源點，連接所有點，容量為U（取m）。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+yejSu7vjteOjrMv509C148GsvdO747Xjo6zI3cG/zqogVSYjNDM7MmctZHYgoaM8L3A+CjxwPrb+t9bDtr7Z1+6088Pctshno6zG5NbQZHbOqna1xLbIoaM8L3A+CjxwPsXQts8oVSpuLU1heEZsb3cpLzIuPj0woaM8L3A+CjxwPtfuuvPM+LP2tcRMvs3Kx9futPPD3LbIoaM8L3A+CjxwPsTD1eK49kzU2dbY0MK9qM28o6zH89futPPB96GjPC9wPgo8cD7Iu7rztNNzs/a3omJmc7vy1d9kZnOjrNffstDB9Mjdwb+089PaMLXEsd+jrMv509DE3LW9tO+1xLXjvs3Kx7TwsLihozwvcD4KPHByZSBjbGFzcz0="brush:java;">#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair pii;
const double INF = 1e7;
const double EPS = 1e-7;
const int MAXN = 100 + 10;
struct Edge{
int from,to;
double cap,flow;
Edge(){};
Edge(int _from,int _to,double _cap,double _flow)
:from(_from),to(_to),cap(_cap),flow(_flow){};
};
pii verter[1010];
vector edges;
vector G[MAXN];
int d[MAXN],cur[MAXN];
bool vst[MAXN];
int dv[MAXN];
int V,E,S,T;
int num;
void clr(){
for(int i = 0;i <= T;++i)
G[i].clear();
edges.clear();
}
void addEdge(int f,int t,double w){
edges.push_back(Edge(f,t,w,0.0));
edges.push_back(Edge(t,f,0.0,0.0));
int sz = edges.size();
G[f].push_back(sz - 2);
G[t].push_back(sz - 1);
}
bool BFS(){
memset(vst,0,sizeof(vst));
queue Q;
Q.push(S);
d[S] = 0;
vst[S] = 1;
while(!Q.empty()){
int x = Q.front(); Q.pop();
for(int i = 0;i < (int)G[x].size();++i){
Edge& e = edges[G[x][i]];
if(!vst[e.to] && e.cap > e.flow){
vst[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vst[T];
}
double DFS(int x,double a){
if(x == T||a == 0) return a;
double flow = 0,f;
for(int& i = cur[x];i < (int)G[x].size();++i){
Edge& e = edges[G[x][i]];
if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0){
e.flow += f;
edges[G[x][i]^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
double maxFlow(){
double flow = 0;
while(BFS()){
memset(cur,0,sizeof(cur));
flow += DFS(S,INF);
}
return flow;
}
void build(double g){
clr();
for(int i = 0;i < E;++i){
addEdge(verter[i].first,verter[i].second,1.0);
addEdge(verter[i].second,verter[i].first,1.0);
}
for(int i = 1;i <= V;++i){
addEdge(S,i,E*1.0);
addEdge(i,T,(1.0*E + 2.0 * g - dv[i]));
}
}
//查找割邊
void dfs(int u){
vst[u] = 1;
if(u <= V) num++;
for(int i = 0;i < (int)G[u].size();++i){
Edge& e = edges[G[u][i]];
if(!vst[e.to] && e.cap > e.flow){
dfs(e.to);
}
}
}
void solve(){
double c,lb = 0,ub = E*1.0;
for(int k = 0;k < 100;++k){
double mid = (lb + ub) / 2.0;
build(mid);
c = maxFlow();
c = (E * V * 1.0 - c) / 2.0;
if(c > EPS){
lb = mid;
} else {
ub = mid;
}
}
build(lb);
maxFlow();
memset(vst,0,sizeof(vst));
num = 0;
dfs(S);
printf("%d\n",num);
for(int i = 1;i <= V;++i){
if(vst[i]) printf("%d\n",i);
}
}
int main()
{
// freopen("Input.txt","r",stdin);
// freopen("Output.txt","w",stdout);
while(~scanf("%d%d",&V,&E)){
int a,b;
if(E == 0){
printf("1\n1\n");
continue;
}
S = V + 1; T = V + 2;
memset(dv,0,sizeof(dv));
for(int i = 0;i < E;++i){
scanf("%d%d",&a,&b);
verter[i] = make_pair(a,b);
dv[a]++;
dv[b]++;
}
solve();
}
return 0;
}
