poj 3155 Hard Life 网络流——最大密度子图

这是一道网络流中难度很大的题目，今天终于把它a掉了，但是想想还是觉得这题很难，建图难就算了，主要是会卡精度！！！我对精度一窍不通，只知道它很坑爹！！wa了11次，确实被坑了。。希望区域赛不会有这种题目

方法：

二分搜索hardnessfactorf ，构造函数 E - f *V（E是导出子图中的边数，V是其中的点数），计算它的最大值，如果大于 0 则增加 f 的下限，小于 0 减少 f 的上限。

建图方法有两种，

第一种是转化为最大权闭合图的模型，好理解但复杂度高；

第二种是s连接每个点，容量是X，X足够大，每个点连接t，容量是X -2.0*f - d[i]；（d[i]是第 i 个点的度数）；

网络的最小割的相反数就是E - f *V 的值，最后就是控制精度

ps:我觉得这题的测试数据应该有点问题，因为把下面代码的dac的值改成1e-10就wa了！！1e-10的话应该会更精确啊！刚实验了好久，一直wa！！改低的话wa了我能理解，但是改高了怎么可能wa啊，怎么可能！！！ f 的下界 l 是绝对可以达到的，最多tle啊！！我想也许是标程的精度不够高吧。。。坑爹啊！！

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
typedef i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
typedef i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a)        for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define SZ(a)           ((int)a.size())
#define PP(n,m,a)		puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 1e-15;
const double dac = 1e-7;
const double pi = acos(-1.0);
const int maxn=111;
const int maxc=1111;
const int end=110;

struct zz
{                     
    int from;
    int to;
    double c;
    int id;
}zx,tz;

vector<zz>g[maxn];
vector<int>v;
queue<int>q;
int cen[maxn];
int d[maxn];
bool vis[maxn];
int n,m,tx[maxc],ty[maxc];

void build(double f) 
{   
    FF(i,maxn)
    {
        g[i].clear();
    }
    FOR(i,1,m)
    {
        zx.from = tx[i];
        zx.to = ty[i];
        zx.c = 1.0;
        zx.id = g[ty[i]].size();
        g[tx[i]].pb(zx);
        swap(zx.from , zx.to);
        zx.id = g[tx[i]].size() - 1; 
        g[ty[i]].pb(zx); 
    }        
    FOR(i,1,n)
    {
        zx.from = 0;
        zx.to = i;
        zx.c = 2*m + 1;
        zx.id = g[i].size();
        g[0].pb(zx);
        swap(zx.from,zx.to);
        zx.id = g[0].size() - 1;
        zx.c = 0.0;
        g[i].pb(zx);
        zx.from = i;
        zx.to = end;
        zx.c = 2*m + 1 + 2.0*f - d[i];
        zx.id = g[end].size();
        g[i].pb(zx);
        swap(zx.from,zx.to);
        zx.c = 0.0;
        zx.id = g[i].size() - 1;
        g[end].pb(zx);   
    }  
    return ;   
}

bool bfs()
{
    MM(cen,-1);
    CL(q);
    q.push(0);
    cen[0] = 0; 
    int now,to;
    while(!q.empty()) 
    {
        now = q.front();
        q.pop();
        FF(i,g[now].size())
        {
            to = g[now][i].to;
            if( g[now][i].c > eps && cen[to] == -1 )
            {
                cen[to] = cen[now] + 1;
                q.push(to);
            }        
        }
    }      
    return cen[end] != -1;  
}

double dfs(double flow = oo , int now = 0)
{
    if(now == end)
    {       
        return flow;
    } 
    double temp,sum=0.0;
    int to;
    FF(i,g[now].size())
    {
        to = g[now][i].to;          
        if( g[now][i].c > eps && flow - sum > eps && cen[to] - cen[now] == 1 ) 
        {
            temp = dfs ( min( flow - sum , g[now][i].c ) , to );
            sum += temp;
            g[now][i].c -= temp;
            g[to][g[now][i].id].c += temp;         
        }    
    }    
    if(sum < eps) cen[now] = -1; 
    return sum; 
}

bool dinic()
{
    double ans = 0.0;
    while(bfs())
    {
        ans += dfs();
    }   
    ans -= (2*m+1)*n;
    if(ans < 0.0)
    {
        return true;
    }
    else    
    {   
        return false;
    }
}

void bfs2()
{
    v.clear();
    MM(vis,false);
    CL(q);
    vis[0] = true;
    q.push(0);
    int now,to;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        FF(i,g[now].size())
        {
            to = g[now][i].to;
            if(g[now][i].c > eps && !vis[to] )
            {
                vis[to] = true;
                q.push(to);
                v.pb(to);
            }
        }
    }   
    sort(v.begin(),v.end());           
    if(v.empty())
    {
        cout<<"1"<<endl;
        cout<<"1"<<endl;
    }
    else
    {
        cout<<v.size()<<endl;
        FF(i,v.size())
        {
            cout<<v[i]<<endl;
        } 
    }   
    return ;
}

void bin()
{
    double l = 0.0;
    double r = n;    
    double mid;
    int temp;
    while( r - l > dac )
    {
        mid = (l+r) / 2.0; 
        build(mid);
        if(dinic())
        {
            l = mid;
        }   
        else
        {
            r = mid;
        }
    }    
    build(l);
    dinic();
    bfs2();
    return ;
} 

int main()
{
    cin>>n>>m;
    FOR(i,1,m)  
    {
        cin>>tx[i]>>ty[i];
        zx.from = tx[i];
        zx.to = ty[i];
        zx.c = 1.0;
        zx.id = g[ty[i]].size();
        g[tx[i]].pb(zx);
        swap(zx.from , zx.to);
        zx.id = g[tx[i]].size() - 1; 
        g[ty[i]].pb(zx); 
    }    
    FOR(i,1,n)
    {
        d[i] = g[i].size();
    }       
    bin();
    return 0;   
}