最小割2
最大权闭合图
定义
最大权闭合图是指在一个有向图里，每一个点有一个对应的权值，可以有负数，然后求一个子图，其中这个子图没有向外的边，但可以存在外面连向子图的边。子图中每一个点不一点相连。求最大权值。
证明
我们首先假设任意的一个子图为v，剩下的子图是v‘，我们首先从S到每一个正点连一条容量为权值的边，从负点连一条容量为绝对值的边，中间全部的容量设为inf。我们定义简单割（最小割处于st边上）。因为v和v’满足最小割的条件，同时它们之间的最大流量为v到t的流量和s到v`的流量，所以最小割也是等于最大流的。然后v的权闭合量为所有的正权点加负权点，于是我们把两者相加可以得出闭合权为所有正权点之和，所以在割取得最小时，闭合权最大，所以最大闭合权等于正权和减去最小割。
code（acwing961）
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=55010,M=4e5+10;
int n,m,S,T;
int head[N],idx=0;
int q[N],cur[N],d[N];
struct Edge{
int next,to,f;
}edge[M];
void add(int a,int b,int c)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,0},head[b]=idx++;
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=head[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
cur[u]=i;
int ver=edge[i].to;
if(d[ver]==d[u]+1&&edge[i].f)
{
int t=find(ver,min(edge[i].f,limit-flow));
if(!t) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
int dinic()
{
int res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
int main()
{
memset(head,-1,sizeof head);
scanf("%d%d",&n,&m);
S=0,T=n+m+1;
for(int i=1;i<=n;i++)
{
int p; scanf("%d",&p);
add(m+i,T,p);
}
int tot=0;
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(S,i,c);
add(i,m+a,inf);
add(i,m+b,inf);
tot+=c;
}
printf("%d\n",tot-dinic());
return 0;
}最大密度子图
定义
选取任意条边，同时要选择每一条边的连点，最小话边权和除以点个数。
证明
code（acwing2324）
#include<iostream>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int N=110,M=(1000+N*2)*2;
int n,m,S,T;
int head[N],idx,ans;
int q[N],cur[N],d[N],deg[N];
bool st[N];
struct Edge{
int next,to;
double f;
}edge[M];
struct Eg{
int a,b;
}edges[M];
void add(int a,int b,double c,double d)
{
edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
edge[idx]=(Edge){head[b],a,d},head[b]=idx++;
}
void build(double g)
{
memset(head,-1,sizeof head); idx=0;
for(int i=0;i<m;i++) add(edges[i].a,edges[i].b,1,1);
for(int i=1;i<=n;i++)
add(S,i,m,0),add(i,T,m+2*g-deg[i],0);
}
bool bfs()
{
int hh=0,tt=0;
memset(d,-1,sizeof d);
q[0]=S,cur[S]=head[S],d[S]=0;
while(hh<=tt)
{
int t=q[hh++];
for(int i=head[t];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(d[ver]==-1&&edge[i].f>0)
{
d[ver]=d[t]+1;
cur[ver]=head[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
double find(int u,double limit)
{
if(u==T) return limit;
double flow=0;
for(int i=cur[u];~i&&flow<limit;i=edge[i].next)
{
int ver=edge[i].to;
cur[u]=i;
if(d[ver]==d[u]+1&&edge[i].f>0)
{
double t=find(ver,min(edge[i].f,limit-flow));
if(t<=0) d[ver]=-1;
edge[i].f-=t,edge[i^1].f+=t,flow+=t;
}
}
return flow;
}
double dinic(double g)
{
build(g);
double res=0,flow;
while(bfs())
while(flow=find(S,inf))
res+=flow;
return res;
}
void dfs(int u)
{
st[u]=true;
if(u!=S) ans++;
for(int i=head[u];~i;i=edge[i].next)
{
int ver=edge[i].to;
if(!st[ver]&&edge[i].f>0)
dfs(ver);
}
}
int main()
{
scanf("%d%d",&n,&m);
S=0,T=n+1;
for(int i=0;i<m;i++)
{
int a,b; scanf("%d%d",&a,&b);
deg[a]++,deg[b]++;
edges[i]=(Eg){a,b};
}
double l=0,r=m;
while(r-l>1e-8)
{
double mid=(l+r)/2;
double t=dinic(mid);
if(m*n-t>0) l=mid;
else r=mid;
}
dinic(l);
dfs(S);
if(!ans) puts("1\n1");
else{
printf("%d\n",ans);
for(int i=1;i<=n;i++)
if(st[i]) printf("%d\n",i);
}
return 0;
}
