这是一道网络流中难度很大的题目,今天终于把它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;
}
分享到:
相关推荐
POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析POJ 1006 源代码——中国剩余定理分析
POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度POj 1001源代码——高精度乘单精度
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj2516代码最小费用最大流
很经典的图论,网络流入门的题目,值得一看啊~~其中有简单的解析
poj 3294 Life Forms.md
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这题是道神题,神就神在,它既能让你搞懂网络流及其优化,还给了你很大的优化空间。
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem....
最短增广路算法的实现 并加上了gap优化和当前弧优化 代码为POJ3469(dual core)的源码
晒代码之二——多重背包(POJ1276)
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
c表示有多少种珍珠 ai 表示第i种珍珠所需的数量 pi 表示第i种珍珠的价钱 每买一种珍珠都需要付额外的10 * pi的钱,便宜的珍珠可以用贵的珍珠来代替,求最少的钱的总数。
北京大学数据结构与算法课程作业代码,供广大学习c++的同学参考与学习
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
数据结构中的各算法,初级,中级,高级。如集合,图的规划,数据等
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ 是“北京大学程序在线评测系统”(Peking University Online Judge)的缩写,是个提供编程题目的网站,兼容Pascal、C、C++、Java、Fortran、Python等多种语言。可以按照分类,在POJ上做题。