题目概述

有 $n$ 个员工 $m$ 条矛盾，现在要炒若干个员工的鱿鱼，一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。

解题报告

最大密度子图模板题。双倍经验BZOJ1312，没权限号就在POJ做了。

精度略有毒，我之前的二分写法一直卡不过去，看来以后还是换成这次这种二分写法吧QAQ。

示例程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long double DB;
const int maxn=100,maxm=1000,maxe=maxn+maxm<<2;

int n,m,x[maxm+5],y[maxm+5],D[maxn+5],ans;
int E,lnk[maxn+5],nxt[maxe+5],son[maxe+5];
int cur[maxn+5],que[maxn+5],ti,vis[maxn+5],dis[maxn+5];
pair<DB,DB> e[maxe+5];

inline int fcmp(DB a,DB b) {if (fabs(a-b)<1e-8) return 0;if (a<b) return -1;return 1;}
inline void Add(int x,int y,DB z){
    son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&fcmp(e[j].fr,e[j].sc)<0) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
    return vis[t]==ti;
}
DB Dfs(int x,int gl,DB MIN=1e100){
    if (x==gl||!fcmp(MIN,0)) return MIN;DB f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&fcmp(now=Dfs(son[j],gl,min(MIN,e[j].sc-e[j].fr)),0)){
            f+=now;e[j].fr+=now;e[j^1].fr-=now;
            if (!fcmp(MIN-=now,0)) break;
        }
    return f;
}
inline bool check(DB mid){
    E=0;memset(lnk,255,sizeof(lnk));DB ans=0;
    for (int i=1;i<=n;i++) Add(0,i,m),Add(i,n+1,m+2*mid-D[i]);
    for (int i=1;i<=m;i++) Add(x[i],y[i],1),Add(y[i],x[i],1);
    while (Bfs(0,n+1)) memcpy(cur,lnk,sizeof(lnk)),ans+=Dfs(0,n+1);
    return fcmp((DB)m*n,ans)>0;
}
void Dfs(int x){
    for (int j=(vis[x]=ti,lnk[x]);~j;j=nxt[j])
        if (fcmp(e[j].fr,e[j].sc)<0)
            if (vis[son[j]]<ti) ans++,Dfs(son[j]);
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]),D[x[i]]++,D[y[i]]++;
    if (!m) return puts("1"),puts("1"),0;DB L=(DB)1/n,R=m;
    for (DB mid=(L+R)/2;fcmp(1e-5,R-L)<0;mid=(L+R)/2) check(mid)?L=mid:R=mid;
    E=0;memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=n;i++) Add(0,i,m),Add(i,n+1,m+2*L-D[i]);
    for (int i=1;i<=m;i++) Add(x[i],y[i],1),Add(y[i],x[i],1);
    while (Bfs(0,n+1)) memcpy(cur,lnk,sizeof(lnk)),Dfs(0,n+1);
    ti++;Dfs(0);printf("%d\n",ans);for (int i=1;i<=n;i++) if (vis[i]==ti) printf("%d\n",i);
    return 0;
}