思路
只能说是个结论,但是我不想推,也不想知道这么推导的,先记下吧。
大致就是二分枚举密度g,然后建图,已经有的关系为建立(1,1)
然后add(S,i,m,0),add(i,T,m+2g-in[i],0)
然后跑最小割,验证nm-dinic(mid),大于0就变大,小于0就变小,因该是和01分数规划差不多的东i
代码
#include <bits/stdc++.h>
using namespace std;
const int N=110,M=1e5+5,inf=1e9;
int h[N],ne[M],e[M],tot=1;
double w[M];
void add(int from,int to,double w1,double w2) {
e[++tot]=to; w[tot]=w1; ne[tot]=h[from]; h[from]=tot;
e[++tot]=from;w[tot]=w2; ne[tot]=h[to]; h[to]=tot;
}
int cur[N],dep[N],S=N-2,T=N-1;
bool bfs() {
memset(dep,0,sizeof(dep));
memcpy(cur,h,sizeof(h));
queue<int>q;
q.push(S);
dep[S]=1;
while(!q.empty()) {
int now=q.front();
q.pop();
for(int i=h[now];i;i=ne[i]) {
int to=e[i];
if(dep[to]==0&&w[i]>0)
dep[to]=dep[now]+1,q.push(to);
}
}
return dep[T];
}
double dfs(int now,double sum) {
if(now==T)return sum;
double ans=0;
for(int i=cur[now];i&∑i=ne[i]) {
cur[now]=i;
int to=e[i];
if(dep[now]+1==dep[to]&&w[i]>0) {
double k=dfs(to,min(sum,w[i]));
if(k==0)dep[to]=0;
w[i]-=k;
w[i^1]+=k;
sum-=k;
ans+=k;
}
}
return ans;
}
int n,m;
int x[M],y[M],in[M];
double dinic(double g) {
memset(h,0,sizeof(h));
tot=1;
for(int i=1;i<=m;i++)add(x[i],y[i],1,1);
for(int i=1;i<=n;i++)
add(S,i,m,0),add(i,T,m+2*g-in[i],0);
double ans=0;
while(bfs())ans+=dfs(S,inf);
return ans;
}
int main() {
cin>>n>>m;
for(int i=1;i<=m;i++) {
cin>>x[i]>>y[i];
in[x[i]]++;
in[y[i]]++;
}
double l=0,r=m;
while(r-l>1e-6) {
double mid=(l+r)/2;
if(m*n-dinic(mid)>1e-6)l=mid;
else r=mid;
}
dinic(l);
vector<int>v;
for(int i=1;i<=n;i++)
if(dep[i])v.push_back(i);
if(v.size()==0)cout<<"1\n1";
else {
cout<<v.size()<<endl;
for(auto x:v)cout<<x<<endl;
}
return 0;
}
标签:生活,int,艰辛,ne,tot,dep,double,now
From: https://www.cnblogs.com/basicecho/p/16993004.html