首页 > 代码库 > Bzoj1312 / POJ3155 Neerc2006 Hard Life
Bzoj1312 / POJ3155 Neerc2006 Hard Life
Submit: 459 Solved: 114
Description
在一家公司中，人事部经理与业务部经理不和。一次，总经理要求人事部从公司的职员中挑选出一些来帮助业务部经理完成一项任务。人事部经理发现，在公司的所有职员中，有一些人相处得很不好。如果把他们同时放在一个工作小组中，他们将会给主管带来不小的麻烦。人事部经理还知道，在一个工作小组中，主管人员的麻烦程度可以认为是(带来麻烦的人的对数/总人数) 。于是，人事部经理决定选取这样的一些人，使得业务部经理的麻烦度最大。你的任务是帮助人事部经理达到他的目的。 在这样的一个公司中，保证公司的人数小于100 人，带来麻烦的员工不会多于1000 对。
Input
第一行给出N,M代表共有N个人,M对人之间有怨念 下面M行，每行两个数，代表这两个人有怨念
Output
输出最多能找出多少个人，人数>=1
Sample Input
5 6
1 5
5 4
4 2
2 5
1 2
3 1
1 5
5 4
4 2
2 5
1 2
3 1
Sample Output
4
HINT
Source
图论 最大密度子图 01分数规划 网络流
将人抽象成点，关系抽象成边，则“带来麻烦的人的对数/总人数”就是一个子图中边数/点数，这玩意儿叫做图的密度。
原题POJ3155 要求输出密度最大时的任一方案
这里要求输出密度最大时最多能选出多少个人。
设密度r=边数/点数，显然是一个01分数规划问题。
解法1：
将每条边看做一个点，对于原图中的一条无向边<u,v>，从代表<u,v>的点向点u和点v各连一条边，容量为INF；
从S向<u,v>连边，容量为1
从u和v向T连边，容量为r
↑原问题转化成了最大权闭合子图问题。
解法2：
证明见胡伯涛《最小割模型在信息学竞赛中的应用》
U=m
从S向u连边，容量为U
从v向T连边，容量为U+2*r-deg[v]
对于边<u,v>从u向v连边，容量为1
若$(m*n-maxflow)/2>0$说明r可以扩大
这样就求出了最大的r
再用这个r建一遍图，跑最大流，在残量网络上DFS就可以找出所有可选的点。
就可以过POJ3155
把输出方案去掉就可以过Bzoj1312
但是博主傻傻不能理解为什么这样贪心一定能选出最多的人
1 /*by SilverN*/ 2 #include<iostream> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cmath> 6 #include<cstring> 7 #include<queue> 8 #define LL long long 9 using namespace std; 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 const int mxn=1005; 13 int read(){ 14 int x=0,f=1;char ch=getchar(); 15 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 16 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 17 return x*f; 18 } 19 struct EG{ 20 int x,y; 21 }eg[mxn<<4]; 22 int deg[mxn]; 23 // 24 struct edge{ 25 int v,nxt; 26 double f; 27 }e[mxn<<4]; 28 int hd[mxn],mct=1; 29 inline void add_edge(int u,int v,double f){ 30 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return; 31 } 32 void insert(int u,int v,double f){ 33 add_edge(u,v,f); add_edge(v,u,0); 34 return; 35 } 36 // 37 int n,m,S,T,U; 38 int d[mxn]; 39 bool BFS(){ 40 memset(d,0,sizeof d); 41 queue<int>q; 42 d[S]=1; 43 q.push(S); 44 while(!q.empty()){ 45 int u=q.front();q.pop(); 46 for(int i=hd[u];i;i=e[i].nxt){ 47 int v=e[i].v; 48 if(!d[v] && e[i].f>0){ 49 d[v]=d[u]+1; 50 q.push(v); 51 } 52 } 53 } 54 return d[T]; 55 } 56 double DFS(int u,double lim){ 57 if(u==T)return lim; 58 double f=0,tmp; 59 for(int i=hd[u];i;i=e[i].nxt){ 60 int v=e[i].v; 61 if(d[v]==d[u]+1 && e[i].f>eps && (tmp=DFS(v,min(lim,e[i].f)))){ 62 e[i].f-=tmp; 63 e[i^1].f+=tmp; 64 lim-=tmp; 65 f+=tmp; 66 if(fabs(lim)<eps)return f; 67 } 68 } 69 d[u]=0; 70 return f; 71 } 72 double Dinic(){ 73 double res=0; 74 while(BFS())res+=DFS(S,INF); 75 return res; 76 } 77 void Build(double r){ 78 memset(hd,0,sizeof hd);mct=1; 79 S=0;T=n+1;int i; 80 for(i=1;i<=n;i++){ 81 insert(S,i,U); 82 insert(i,T,U+2*r-deg[i]); 83 } 84 for(i=1;i<=m;i++){ 85 add_edge(eg[i].x,eg[i].y,1); 86 add_edge(eg[i].y,eg[i].x,1); 87 } 88 return; 89 } 90 bool use[mxn];int cnt=0; 91 void DFS(int u){ 92 use[u]=1;++cnt; 93 for(int i=hd[u];i;i=e[i].nxt){ 94 if(!use[e[i].v] && e[i].f>eps){DFS(e[i].v);} 95 } 96 return; 97 } 98 void solve(){ 99 double l=0,r=m; U=m;100 double X=1.0/n/n;101 while(r-l>X){102 double mid=(l+r)/2;103 Build(mid);104 // printf("mid:%.3f\n",mid);105 if((m*n-Dinic())/2>=eps){106 l=mid;107 }else r=mid;108 }109 Build(l);Dinic();110 return;111 }112 void init(){113 memset(hd,0,sizeof hd);mct=1;114 memset(use,0,sizeof use);cnt=0;115 return;116 }117 int main(){118 while(scanf("%d%d",&n,&m)!=EOF){119 if(!m){printf("1\n1\n");continue;}120 init();121 for(int i=1;i<=m;i++){122 eg[i].x=read();eg[i].y=read();123 ++deg[eg[i].x];124 ++deg[eg[i].y];125 }126 solve();127 DFS(S);128 printf("%d\n",cnt-1);129 for(int i=1;i<=n;i++)if(use[i])printf("%d\n",i);130 break;131 }132 return 0;133 }
Bzoj1312 / POJ3155 Neerc2006 Hard Life
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。