专项测试2
A. 收藏家
网络流,把每个人都拆点每个时间拆成一个，之间连 \(a_i\) 容量的边,保证每个之间最多有 \(a_i\) 个物品
再从 \(S\) 向每个人连 \(1\) 的边,因为最后要求的是不一样的物品数量,每有一个流量就代表有一个不同的物品
第一个人再向 \(T\) 连 \(a_1\) 的边
每个时间都有把交换的两个人互相连 \(1\) 的边权,因为有方向限制,所以时间靠后的不会影响前面的
最后发现没用的点很多,于是只把有用的点建出来跑网络流就行
Code
#include
//#define int long long
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int tests;
int n,m,T,S,cnt;
int a[3010],lst;
int pre[3010];
int head[6010],HD[6010],ver[40010],to[40010],edge[40010],tot;
int q[6010],h,t,dis[6010];
inline void add(int x,int y,int z){
ver[++tot]=y;edge[tot]=z;to[tot]=head[x];head[x]=tot;
ver[++tot]=x;edge[tot]=0;to[tot]=head[y];head[y]=tot;
}
inline bool bfs(){
for(int i=1;i<=cnt;i++) dis[i]=inf;
q[h=t=1]=S,dis[S]=0;memcpy(head,HD,sizeof(head));
while(h<=t){
int x=q[h++];
for(int i=head[x];i;i=to[i]) if(edge[i]){
int y=ver[i];
if(dis[y]>dis[x]+1) dis[y]=dis[x]+1,q[++t]=y;
}
if(x==T) return true;
}
return false;
}
int dfs(int x,int in){
if(x==T) return in;
int res=in,go;
for(int i=head[x];i;head[x]=i=to[i]) if(edge[i]){
int y=ver[i];
if(dis[y]==dis[x]+1){
go=dfs(y,min(res,edge[i]));
if(go) edge[i]-=go,edge[i^1]+=go,res-=go;
else dis[y]=0;
}
if(!res) break;
}
return in-res;
}
inline void solve(){
int res=0;lst=0;cnt=2;S=1,T=2;
n=read(),m=read();tot=1;
memset(head,0,sizeof(head));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1,x,y;i<=m;i++){
x=read(),y=read();
if(pre[x]){add(pre[x],++cnt,a[x]);pre[x]=cnt;}
else{add(S,++cnt,1);pre[x]=cnt;}
if(pre[y]){add(pre[y],++cnt,a[y]);pre[y]=cnt;}
else{add(S,++cnt,1);pre[y]=cnt;}
add(pre[x],pre[y],1);
add(pre[y],pre[x],1);
}
add(pre[1],T,a[1]);
memcpy(HD,head,sizeof(head));
while(bfs()) res+=dfs(S,inf);
printf("%d\n",res);
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
tests=read();while(tests--) solve();
return 0;
}
B. 旅行
朴素的 \(dp\) 方程时 \(f_u=\frac{\sum f_v}{deg_u}+1\) ,要最大化取值
前面的部分可以用 01分数规划二分来做
设当前的二分答案为 \(mid\)
\[\frac{\sum f_v}{deg_u}>mid \]\[\sum f_v>mid\times deg_u \]\[\sum f_v-mid\times deg_u>0 \]那么每个选择的边贡献 \(f_v-mid\)
删边的限制为删 \(y\) 必须删 \(x\) 的限制可以变成选择 \(x\) 则必须选 \(y\)
可以用网络流跑最大权闭合子图来解决
Code
#include
//#define int long long
#define eps 1e-4
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,m,k,S,T;
int head[510],HD[510],ver[10010],to[10010],tot;
double edge[10010];
int dis[510],q[510],h,t;
int deg[60];
double f[60];
vectorg[60],gg[60];
queueque;
struct E{int x,y;}e[510],ee[2010];
inline void add(int x,int y,double z){
//printf("%lld -> %lld : %.10lf\n",x,y,z);
ver[++tot]=y;edge[tot]=z;to[tot]=head[x];head[x]=tot;
ver[++tot]=x;edge[tot]=0;to[tot]=head[y];head[y]=tot;
}
inline void build(){
memset(head,0,sizeof(head));tot=1;
for(int i=1;i<=k;i++) if(ee[i].x!=ee[i].y) add(ee[i].x,ee[i].y,inf);
}
inline bool bfs(){
for(int i=1;i<=T;i++) dis[i]=inf;
q[h=t=1]=S,dis[S]=0;memcpy(head,HD,sizeof(head));
while(h<=t){
int x=q[h++];
for(int i=head[x];i;i=to[i]) if(edge[i]>eps){
int y=ver[i];
if(dis[y]>dis[x]+1) dis[y]=dis[x]+1,q[++t]=y;
}
if(x==T) return true;
}
return false;
}
double dfs(int x,double in){
if(x==T) return in;
double res=in,go;
for(int i=head[x];i;head[x]=i=to[i]) if(edge[i]>eps){
int y=ver[i];
if(dis[y]==dis[x]+1){
go=dfs(y,min(res,edge[i]));
if(go) edge[i]-=go,edge[i^1]+=go,res-=go;
else dis[y]=0;
}
if(!res) break;
}
return in-res;
}
inline bool check(int x,double mid){
double sum=0,res;
build();
for(int i=1;i<=m;i++) if(e[i].x==x){
res=f[e[i].y]-mid;
if(res>eps) sum+=res,add(S,i,res);
else if(reseps;
}
inline double calc(int x){
double l=0,r=100;
while(r-l>eps){
double mid=(l+r)/2.0;
if(check(x,mid)) l=mid;
else r=mid;
}
return l;
}
signed main(){
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read(),m=read(),k=read();S=m+1,T=m+2;
for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read();
for(int i=1;i<=k;i++) ee[i].x=read(),ee[i].y=read();
for(int i=1;i<=m;i++){
g[e[i].y].emplace_back(e[i].x);
gg[e[i].x].emplace_back(ee[i].y);
deg[e[i].x]++;
}
for(int i=1;i<=n;i++) if(!deg[i]) que.push(i);
while(!que.empty()){
int x=que.front();que.pop();
if(gg[x].size()) f[x]=calc(x)+1;
else f[x]=0;
for(auto y:g[x]){
deg[y]--;
if(!deg[y]) que.push(y);
}
}
printf("%.10lf\n",f[1]);
return 0;
}