题面

Description

ADN公司内部共 n个员工，员工之间可能曾经因为小事有了过节，总是闹矛盾。若员工u和员工 v有矛盾，用边(u, v)表示，共 m个矛盾。最近，ADN公司内部越来越不团结，Amber决定裁员。Amber想得到一个被裁人员的清单，使得被裁人员间的不团结率最高。不团结率定义为被裁人员间的矛盾总数与被裁人员数的比值（不团结率=被裁人员之间的矛盾总数/被裁人员数）。

在上图这个例子中1, 2, 4和5，4个人中都有5对矛盾，则不团结率为\(\frac 45\)。如果我们添加3到这个团队，则不团结率就下降到\(\frac 56\)。

Input

　　输入文件的第一行包含两个整数n和m (1≤n≤100,0≤m≤1000)，n表示公司的总人数(编号从1到n)，m表示矛盾的对数。

　　接下来m行，每行两个整数ai和bi(1≤ai,bi≤n,ai≠bi)，描述一对矛盾，每对矛盾只会出现一次。

Output

　　输出文件的第一行为一个整数k(1≤k≤n)，表示最不团结的团队总人数。

Sample Input

sample input #1

5 6

1 5

5 4

4 2

2 5

1 2

3 1

sample input #2

4 0

Sample Output

sample output #1

4

sample output #2

1

Hint

Note, that in the last example any team has hardness factor of zero, and any non-empty list of people is a valid answer.

题目分析

最大密度子图模板题。

假设答案为\(k\) ，则要求解的问题是：

选出一个合适的点集 \(V\) 和边集 \(E\)，令\((|E|−k∗|V|)\)取得最大值。

所谓“合适”是指满足如下限制：若选择某条边，则必选择其两端点。

建图:

以原图的边作为左侧顶点，权值为\(1\)；

原图的点作为右侧顶点，权值为\(+k\)。

若原图中存在边 \((u,v)\)，则新图中添加两条边 \(([uv]−>u),([uv]−>v)\)，转换为最大权闭合子图。

代码实现

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#define MAXN 0x7fffffff

#define eps 1e-9

typedef long long LL;

const int N=1105;

using namespace std;

inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}

int n,m,S,T,num;

struct node{int next,to,pair;double flow;}g[N<<3];

struct Edge{int x,y;}s[N];

int h[N],cnt;

void AddEdge(int x,int y,double z){

	g[++cnt].to=y,g[cnt].next=h[x],h[x]=cnt,g[cnt].flow=z,g[cnt].pair=cnt+1;

	g[++cnt].to=x,g[cnt].next=h[y],h[y]=cnt,g[cnt].flow=0,g[cnt].pair=cnt-1;

}

int GAP[N],dis[N];

void Init(){

	static int q[N];

	fill(dis,dis+num,0),fill(GAP,GAP+num,0);

	int l=0,r=1;q[++l]=T,++GAP[dis[T]=1];

	while(l<=r){

		int x=q[l++];

		for(int i=h[x];i;i=g[i].next){

			int to=g[i].to;

			if(!dis[to])++GAP[dis[to]=dis[x]+1],q[++r]=to;

		}

	}

}

double Dfs(int x,double Maxf){

	if(x==T||!Maxf)return Maxf;

	double ret=0;

	for(int i=h[x];i;i=g[i].next){

		int to=g[i].to;

		if(g[i].flow&&dis[x]==dis[to]+1){

			double dlt=Dfs(to,min(g[i].flow,Maxf-ret));

			g[i].flow-=dlt;

			g[g[i].pair].flow+=dlt;

			ret+=dlt;

			if(dis[S]==num+1||ret+eps>=Maxf)return ret;

		}

	}

	if(!(--GAP[dis[x]]))dis[S]=num+1;

	else GAP[++dis[x]]++;

	return ret;

}

double SAP(){

	Init();

	double ans=Dfs(S,MAXN);

	while(dis[S]<=num)ans+=Dfs(S,MAXN);

	return ans;

}

bool Check(double mid){

	fill(h,h+num,0),cnt=0;

	for(int i=1;i<=m;i++)AddEdge(S,i,1),AddEdge(i,s[i].x+m,MAXN),AddEdge(i,s[i].y+m,MAXN);

	for(int i=1;i<=n;i++)AddEdge(i+m,T,mid);

	return m-SAP()>0;

}

int ans;bool vis[N];

void Find(int x){

	ans+=(x>m&&x<=m+n);

	vis[x]=1;

	for(int i=h[x];i;i=g[i].next){

		int to=g[i].to;

		if(g[i].flow&&!vis[to])Find(to);

	}

}

int main(){

	n=Getint(),m=Getint(),S=0,T=n+m+1,num=T+1;

	if(!m)cout<<1,exit(0);

	for(int i=1;i<=m;i++)s[i].x=Getint(),s[i].y=Getint();

	double l=0,r=m,Eps=1.0/n/n;

	while(l+Eps<r){

		double mid=(l+r)/2;

		if(Check(mid))l=mid;

		else r=mid;

	}

	Check(l),Find(S);

	cout<<ans;

	return 0;

}

巴特西

【POJ3155】生活的艰辛Hard Life

题面