程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3155 Hard Life(最大密度子圖，01分數規劃)

poj 3155 Hard Life(最大密度子圖，01分數規劃)

編輯：C++入門知識

大致題意：給出一個無向圖，求出它的一個最大密度子圖，最大密度子圖定義為子圖的邊數與頂點數的比值。

詳見amber論文中關於最大密度子圖

本題要注意的地方：

當m為0時也要輸出內容。

二分的邊界是 1/n/n(high - low >1/n/n) ,這在amber論文引理4.1中有講解

因為h函數的特性，恆有h >=0，即h函數不是一個嚴格遞減的函數，當減小到0時便不再減小。那麼我們要取得的是第一個為0的，所以要二分下界，而不是直接取mid,因為沒有意識到函數特性，WA了N次。

二分完畢後，並不能求出正確的low值，ms也是因為該函數的特性，我們還要再求一遍最大流。

根據殘量網絡求最大密度子圖：從源點dfs,走殘量網絡中流量大於0的邊並標記。

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-8

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 110;
const int maxm = 1010;

struct node
{
	int u,v;
	double w;
	int next,rev;
}p[maxm],edge[maxm*6];

int s,t,n,m,nn;
int cnt,head[maxn];
int d[maxn];
int dist[maxn],vis[maxn];
int ans;

void init()
{
	cnt = 0;
	memset(head,-1,sizeof(head));
}

void add(int u, int v, double w)
{
	edge[cnt] = (struct node){u,v,w,head[u],cnt+1};
	head[u] = cnt++;

	edge[cnt] = (struct node){v,u,0,head[v],cnt-1};
	head[v] = cnt++;
}

void build(double mid)
{
	init();
	for(int i = 1; i <= m; i++)
	{
		add(p[i].u,p[i].v,1.0);
		add(p[i].v,p[i].u,1.0);
	}
	for(int i = 1; i <= nn; i++)
	{
		add(s,i,m);
		add(i,t,m*1.0+2*mid-d[i]*1.0);
	}
}

bool bfs()
{
    queue  que;
    memset(dist, 0, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    while(!que.empty()) que.pop();
    vis[s] = 1;
    que.push(s);
    while(!que.empty())
    {
        int u = que.front();
        que.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(edge[i].w && !vis[v])
            {
                que.push(v);
                vis[v] = 1;
                dist[v] = dist[u]+1;
            }
        }
    }
    if(dist[t] == 0)
		return false;
	return true;
}

double dfs(int u, double delta)
{
    if(u == t) return delta;
    double ret = 0,tmp;

	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].v;
		if(edge[i].w && dist[edge[i].v] == dist[u]+1 && (tmp = dfs(v,min(delta,edge[i].w))))
		{
			edge[i].w -= tmp;
			edge[edge[i].rev].w += tmp;
			return tmp;
		}
	}
	if(!ret) dist[u] = -1;
	return ret;
}

double Dinic()
{
    double ans = 0,res;
    while(bfs())
    {
       while(res = dfs(s,INF))
			ans += res;
    }
    return ans;
}

void dfs_cut(int u)
{
	vis[u] = 1;
	if(u <= nn) ans++;
	for(int i = head[u]; i != -1; i = edge[i].next)
	{
		int v = edge[i].v;
		if(edge[i].w > 0 && !vis[v])
		{
			dfs_cut(v);
		}
	}
}

int main()
{
	while(~scanf(%d %d,&n,&m))
	{
		if(m == 0)
		{
			printf(1
1
);
			continue;
		}
		memset(d,0,sizeof(d));
		for(int i = 1; i <= m; i++)
		{
			scanf(%d %d,&p[i].u,&p[i].v);
			d[p[i].u]++;
			d[p[i].v]++;
		}

		s = n+1;
		t = n+2;
		nn = n;
		n = t;

		double low,high,mid,h;
		low = 0.0;
		high = m;
		while(high - low > 1.0/nn/nn)
		{
			mid = (high + low)/2;
			build(mid);
			h = (m*nn*1.0 - Dinic() )/2;

			if(h > eps)
				low = mid;
			else high = mid;
		}

		build(low);
		Dinic();

		ans = 0;
		memset(vis,0,sizeof(vis));

		dfs_cut(s);

		printf(%d
,ans);
		for(int i = 1; i <= nn; i++)
		{
			if(vis[i])
				printf(%d
,i);
		}
	}
	return 0;
}