Time Limit:?10 Sec??Memory Limit:?162 MB
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

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 }

?

轉載于:https://www.cnblogs.com/SilverNebula/p/6902820.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的Bzoj1312 / POJ3155 Neerc2006 Hard Life的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。